Class 12 — Monday, October 5
Quiz 5 opens the class and closes it. Sections 1, 3 and 5 run on the projector — keyboards down. Sections 2, 4 and 6 are in pairs; 4 and 6 each start with the core, then hold tasks for pairs that are done.
- Two ideas from Wednesday
- What searching everything costs — guess first
- A stack and a queue — predict first
- A stack and a queue at work: brackets and the potato; then reversed and two stacks
- A priority queue — predict first
- A priority queue at work: shortest first; then get it out anyway and a point that files itself again
The cores are the class. The “then” tasks go past anything you have been asked for — take them in order if you get there.
Wednesday is the Midterm, Wednesday, October 7. The end of today’s class is for your questions about it.
1. Two ideas from Wednesday
Keyboards down.
On Wednesday a map lost a key it was still holding, because the point moved. Two ideas for a way out came up in the Journal.
Check the hash code again every time the point moves.
I think we said that if the hash code was re-checked every time it is moved, it would not be lost but it would cost memory. I think it would be a good tradeoff so that you don’t lose the key.
Search every bucket for a key that is not where its number says.
I would make Point check every bucket to find the lost key. It would cost more memory to use but I think it is a good trade off because if using a big list and want to change multiple elements, we’d have to remove it, change it, then add it back.
What would each one really cost, and who would do the work?
Nothing tells the set that the point moved. A point does not know which sets are holding it. For the set to check again, the point would have to carry its sets around and file itself again in each one. Section 8 builds that, and finds where it breaks.
Searching every bucket works, and turns the hash set into a list. Section 2 measures what that costs.
The fix that costs nothing while the program runs is the one today’s reading is about: a key that cannot change.
2. What searching everything costs
Keyboards up. Pairs. A new file, SearchCost.java, in any project you have open. The room dictates, the projector types, and every pair types along.
A list has no buckets. Its contains asks equals of every element until it finds one, which is what searching every bucket would turn a hash set into. Measure it: the same 100,000 numbers, the same 10,000 questions, half of them about numbers that are not there, and three collections to ask.
The sizes are constants at the top of the class, named in capitals because they never change:
static final int SIZE = 100_000; // numbers in each collection
static final int QUESTIONS = 10_000; // contains calls each is asked
static final int STEP = 2 * SIZE / QUESTIONS; // so half the questions are past the endTwo methods, so each loop is written once:
static void fill(Collection<Integer> c)
static void timeLookups(String label, Collection<Integer> c)fill puts 0 to SIZE - 1 into c. timeLookups starts a clock with System.nanoTime(), asks c.contains(i * STEP) QUESTIONS times, counts how many were found, and prints the label, the microseconds and the count. Only the lookups are inside the clock. Collection is the interface that List and Set both extend; add and contains are its, which is why one method serves all three. import java.util.*; brings in all of them.
main makes a list, fills it and times it. Before that first run, write your guess in a comment: when SIZE doubles, which of the three times doubles, which stays where it is, and which grows only a little?
Then a HashSet and a TreeSet: make each, fill all three before timing any, and time each with its label. Then double SIZE and run again. Done when both runs print found 5000 three times, and you can say which line grew with the size. Your times will not be ours; the found counts will.
import java.util.*;
public class SearchCost {
static final int SIZE = 100_000; // numbers in each collection
static final int QUESTIONS = 10_000; // contains calls each is asked
static final int STEP = 2 * SIZE / QUESTIONS; // so half the questions are past the end
// puts 0 to SIZE - 1 into c
static void fill(Collection<Integer> c) {
for (int i = 0; i < SIZE; i++) {
c.add(i);
}
}
// asks c QUESTIONS contains questions, then prints how many microseconds
// they took and how many were found
static void timeLookups(String label, Collection<Integer> c) {
long start = System.nanoTime();
int found = 0;
for (int i = 0; i < QUESTIONS; i++) {
if (c.contains(i * STEP)) found++;
}
long micros = (System.nanoTime() - start) / 1_000;
System.out.println(label + " " + micros + " microseconds, found " + found);
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
Set<Integer> hashed = new HashSet<>();
Set<Integer> sorted = new TreeSet<>();
fill(list);
fill(hashed);
fill(sorted);
timeLookups("list ", list);
timeLookups("hash set", hashed);
timeLookups("tree set", sorted);
}
}At 100,000 then 200,000: the list took about 290,000 microseconds, then about 900,000; the hash set under a millisecond both times; the tree set about 4 milliseconds, then about 5. The same clock over more sizes, by Growth.java, six seconds to run:
So “how many times slower” has a different answer at every size, and the question to ask is what doubling the size does. The answer is how many questions each collection asks per lookup. Counted, by a number that counts its own equals, hashCode and compareTo calls (Steps.java), as the size doubles from 25,000 to 800,000:
Both sets of pictures are Java’s: Growth and Steps draw their own tables through Chart.java, sixty lines that build an SVG file — a text file naming shapes — the way a toString builds a string, and a browser draws it. Not today’s topic; there to show that a useful picture is a program’s output too.
- A list calls
equalson element after element until it finds one, so twice the elements is twice the questions. (Above, it tripled rather than doubled: a list that big also stops fitting in the processor’s fast memory, a second cost on top of the questions.) - A hash set calls
hashCodeonce andequalsin the one bucket it lands in, however big the set: the same one or two questions at any size. - A tree set calls
compareToonce per level on its way down, and doubling the size adds a level or two. That walk is also why a tree set loses a changed element only when the change moves it past a neighbour: there, the walk turns the wrong way.
3. A stack and a queue
Keyboards down. Predict each line before it runs.
An ArrayDeque can be either. As a stack, push and pop work at the same end, so the last thing in is the first out. As a queue, offer adds at the back and poll takes from the front.
Deque<String> stack = new ArrayDeque<>();
stack.push("red");
stack.push("green");
stack.push("blue");
System.out.println(stack.pop() + " " + stack.pop() + " " + stack.peek());
Queue<String> line = new ArrayDeque<>();
line.offer("red");
line.offer("green");
line.offer("blue");
System.out.println(line.poll() + " " + line.poll() + " " + line.peek());
Queue<String> empty = new ArrayDeque<>();
System.out.println(empty.poll());
System.out.println(empty.remove());blue green red
red green blue
null
and then it stops with java.util.NoSuchElementException.
peek looks without taking. And each job has two methods: one throws when there is nothing to take (remove, pop), and one answers null (poll) — the same null a map’s get gives for a missing key.
4. A stack and a queue at work
Keyboards up. Pairs. 4.1 and 4.2 are the core; 4.3 and 4.4 are for pairs that are done.
4.1 Brackets that match
A new file.
Write balanced, which says whether every (, [ and { in a string is closed by its own partner, the innermost first. Every other character is ignored.
Use a Deque<Character> as a stack. push each opening bracket. At a closing one, pop the last one opened and check that the two are partners. Whatever is still open at the end is a failure too. A closing bracket with nothing open is the case to think about: pop on an empty deque throws.
Done when this
for (String s : List.of("f(x[1])", "{[}]", "((", ")(", "")) {
System.out.println(balanced(s) + " " + s);
}prints
true f(x[1])
false {[}]
false ((
false )(
true
4.2 Pass the potato
Same pair, a new file.
The names stand in a line, and the one at the front holds the potato. It is passed passes times, and each pass takes the name at the front and puts it at the back. Whoever holds it then leaves the line, and the game goes on until nobody is left.
Write order, which returns the names in the order they leave. A Queue<String> made with new ArrayDeque<>(names) is the line: poll takes from the front and offer puts at the back. Leave the list you were given as it was.
Done when order(List.of("ann", "bob", "cat", "dan"), 1) is [bob, dan, cat, ann], and the same names with 3 passes give [dan, ann, cat, bob].
4.3 Reversed
For pairs that are done.
Write reversed, which returns a string’s characters in the opposite order. Use a Deque<Character> as a stack: push every character, then pop until it is empty, building the answer as you go.
Done when reversed("stack") is kcats and reversed("") is the empty string.
4.4 A queue made of two stacks
The bigger one.
Build a queue out of two ArrayDeques used only as stacks: push, pop and isEmpty, nothing else. offer pushes onto the first stack. poll pops from the second, and when the second is empty, it first moves everything from the first onto it, one pop and push at a time. poll answers null when there is nothing at all.
Done when offering a, b and c, polling once, offering d, and then polling four times prints a b c d null.
Then say in a comment why the order comes out right, though a stack turns its order round.
5. A priority queue
Keyboards down. Prediction before it runs.
A priority queue hands back the smallest first, whatever order things went in.
PriorityQueue<Integer> queue = new PriorityQueue<>(List.of(7, 3, 9, 1, 5));
System.out.println(queue);
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}Write your answer in the Journal before it runs. Two lines, and a guess counts as a line.
What do the two lines print?
[1, 3, 9, 7, 5]
1 3 5 7 9
Only poll hands them out in order. Printing the queue, or walking it with a for-each loop, shows the queue’s own order, which is not sorted. The smallest is always at the front.
6. A priority queue at work
Keyboards up. Pairs. 6.1 is the core; 6.2 and 6.3 are for pairs that are done.
6.1 Shortest first
A new file.
Write shortest, which returns the n shortest words, shortest first, or all of them if there are fewer than n. Two words of the same length come out alphabetically.
Put the words into a PriorityQueue<String> made with a comparator of your own: length first, and the words themselves when the lengths are equal. Then poll it n times.
Done when the words kiwi, fig, banana, pear, apple and plum give [fig, kiwi, pear] for 3, and all six, [fig, kiwi, pear, plum, apple, banana], for 10.
6.2 Get it out anyway
For pairs that are done.
Use Wednesday’s Point, the one that can move. Put a point into a HashSet, move it, and try remove: it answers false, because it looks in the bucket for the new number. An iterator walks every bucket, so it can still reach the point.
Take the point out with an iterator’s own remove, then add it back, and ask contains.
Done when you print false 0 true: the failed remove, the size after the iterator took the point out, and contains after it went back in.
6.3 A point that files itself again
The bigger one.
The first idea from section 1, made to work. A TrackedPoint knows the one set holding it: its constructor takes the set and adds itself to it. Its moveTo takes itself out of the set, changes x and y, and puts itself back in, so the set files it under its new number.
Done when a tracked point that has moved is still found by its set.
Then put the same point into a second HashSet with an ordinary add, move it again, and ask both sets. Explain the two answers in a comment before opening the box.
true false. The point files itself again in the one set it knows, and the second set has lost it. Every set a point is in would have to be on its list, and nothing can make an ordinary add tell the point.