The The Slow Lookup
Stardate 55158.6 · UES Magnanimous
Briefing
Lt. Skree wants every entry id in our log that also appears in the other ship's log, in our order. Both logs have about two hundred thousand entries. The current routine checks each of ours against every one of theirs, which is forty billion comparisons, and Skree has calculated it will finish "on Thursday, of a different week".
The fix is not a faster loop. It is a different data structure: put theirs into a set, where membership is a hash lookup rather than a scan, and the same job takes a fraction of a second. ARCHIE will check the small cases first, then a medium one with a stopwatch, and only if that is fast will it attempt the full two hundred thousand. Do not, Commander Raghunathan says, make it attempt the full two hundred thousand the slow way.
Mission objectives
ARCHIE checks all five every time you run diagnostics.
- •Common ids on a small case, in our order
- •No overlap gives nothing
- •Ids in theirs but not ours are not included
- •A medium case is fast (a set, not a scan)
- •The full two hundred thousand, if the medium case was fast
Objective
Write common_ids(ours, theirs): return the ids from ours
that also appear in theirs, in the order they appear in ours.
Both inputs are lists of integers with no duplicates. It must be fast for two hundred
thousand entries each.
Press Run Diagnostics and I will tell you which objectives you actually met.
Objective
Write common_ids(ours: &[u32], theirs: &[u32]) -> Vec<u32>:
the ids from ours that also appear in theirs, in the order
they appear in ours. Both inputs have no duplicates. It must be fast for
two hundred thousand entries each.
Press Run Diagnostics and I will tell you which objectives you actually met.
Ask Commander Raghunathan for a hint
Build a set from theirs once, then keep each of ours that is in the set. That is O(n) instead of O(n²). Rust: HashSet; Python: set().
Debrief
Sixty-six thousand shared entries in a tenth of a second. Every one of them is from before the gap. After the gap, nothing matches, until tomorrow's stardate, which is in both. Skree has stopped writing and started reading what Skree has written.