Sets and Dictionaries at Work
The dictionaries and sets your language already has, how to use your own objects as keys without a hidden bug, and hash tables at work: caches, counting and removing duplicates.
Updated
In Your Language
- The Front Desk Finds You in One Scan: Dictionaries (Apprentice): Find any of a gym's 2,000 members in one step, 600 times an hour, with the dictionary your language already has: add, read, update and remove entries, read a missing key safely, and know when not to count on its order.
- Have I Seen This Before? Sets (Apprentice): Count the different members who came to the gym today, and know at each scan whether it's someone's first visit: why counting scans, a list and a dictionary of "true" each fall short, and how your language's set answers "have I seen this before?" in one step.
Using Them Well
- Why Can't the Dictionary Find Card 1042? Good Keys (Journeyman): Find a member's locker from the card scanned this morning, when both of the gym's branches have a member 1042: why the card object, the member number alone and equality on its own each fail, and how to make your own type a key that works in your language.
- When a Loop Inside a Loop Is Too Slow: Hash Tables at Work (Journeyman): Turn the gym's slow year-end reports into one pass: count each member's visits, find the first member to come back, and stop asking a slow server the same question twice. Then choose a list, a set or a dictionary for a job, and say why.
Exercise: The Word Counter
- Exercise: The Word Counter (Apprentice): A year of the gym's member comments, 300,000 words, and a report that has to finish in under 2 seconds: count every word, list the ten members use most, and find the words used only once. The tests check it on a short story and on a full year.