Task 4: Discussion of the Sets

Write your answers in DISCUSSION.md, under the heading for each part, as in the previous section.

Part III: Searching the sets

Run SetDriver with:

scripts/run.sh set.SetDriver

It reads the first 1,000 values of random.data. For each set, it first builds the set by adding the values in the order they appear in the file (the build rows). Then it runs three query patterns on a newly built set: sequences of 10,000 calls to contains (the third pattern is yours, for Part IV). For each run, the report shows the accesses, the mutations, the time of the first run, and the time of the fastest of five runs.

  • In the uniform pattern, every value is searched for equally often, in the order the values were added.
  • In the skewed pattern, nine searches in ten are for one of the last nine values added.
  1. In the uniform pattern, MeasuredMoveToFrontArraySet makes more accesses than MeasuredArraySet. In the skewed pattern, it makes far fewer, while MeasuredTransposeArraySet barely helps. Explain both.
  2. MeasuredTransposeArraySet removes an item by moving the last item into the gap. How does that work against the heuristic? Give a short sequence of add, contains, and remove calls that shows the problem. Why does MeasuredMoveToFrontArraySet keep the order when it removes?

Part IV: Your search experiment

Write your own query pattern in the experimentQueries method of SetDriver. Do not change anything else in the driver.

Design a pattern in which MeasuredTransposeArraySet makes fewer accesses than both MeasuredArraySet and MeasuredMoveToFrontArraySet. Describe the pattern, why you expected it to work, and the numbers you got. Then look at the two time columns. Is the first run slower than the fastest? Explain why the first run of a Java program can be slower than later runs of the same code.