Dictionaries and sets 0/1

Lesson 14 of 21

Dictionaries and sets

Look values up by key, count things and remember what you have already seen.

Part 1 of 8 Finding by value

Looking up a value instead of a position

A list finds its elements by position: nums[3] is the element at index 3. Many questions are about the values instead: whether a name has appeared before, how many times a word appeared, or which price goes with a fruit. A list can answer them only by searching, comparing the wanted value with each element in turn until one matches or the list runs out.

Here is a question of that kind. A website writes the name of each visitor to a log, one name per line, and you want to know how many different people visited. If the log reads ana, bo, ana, cy, the answer is 3: ana visited twice, but she is one person.

The cost of searching a long list

A list search slows down as the list grows. Suppose the log has N=2×105N = 2 \times 10^5 names, a size judge problems often allow, and almost all of them are different. Then seen keeps growing, and the search for the ii-th name compares it with all i−1i - 1 names stored before it. Over NN names the comparisons add up to

0+1+⋯+(N−1)=N(N−1)2≈(2×105)22=2×10100 + 1 + \cdots + (N - 1) = \frac{N(N-1)}{2} \approx \frac{(2 \times 10^5)^2}{2} = 2 \times 10^{10}

Python manages about 10710^7 simple steps a second, so that is 2×1010/107=2,0002 \times 10^{10} / 10^7 = 2{,}000 seconds, where a judge usually allows 2.

A list keeps no record of where a value might be, so a search for a value that is not there has to check every element. A long log needs a container that answers "is this value here?" without looking at everything it holds.