Sets and Choosing the Right Container

Sets: uniqueness for free

"Have I seen this before?" is one of the most common questions in code: has this email already been invited, has this page been visited, which distinct error codes occurred today. The set is the container built to answer it.

A set keeps each value at most once, with no positions at all. Build one with braces or by converting: set([1, 2, 2, 3]) is {1, 2, 3}. Careful: {} makes an empty dict, an empty set is set().

Two jobs sets do better than any other container, for concrete reasons:

• Deduplication: a set stores each value at most once by definition, so set(words) drops every repeat in one step.
• Fast membership: a set locates a value directly from the value itself instead of scanning item by item, so x in my_set stays fast even with millions of members. The same in on a list must walk the list front to back.

Sets also do math-style combinations: a & b keeps the common items, a | b merges both.

One string helper you will need here and in the projects: sentence.split() cuts a string into a list of words wherever there is whitespace:

"the cat sat".split()   # ['the', 'cat', 'sat']

Deduplicating, and combining sets

Sets have no reliable printing order, so the examples below report lengths and sorted versions rather than printing the sets directly.

nums = [1, 2, 2, 3, 3, 3]
unique = set(nums)
print(len(nums))
print(len(unique))
a = {1, 2, 3}
b = {3, 4}
print(sorted(a & b))
print(sorted(a | b))

Output

6
3
[3]
[1, 2, 3, 4]

The conversion to a set collapsed six values into three, dropping every repeat in a single step with no loop and no comparisons written by hand. The & kept only the value present in both sets, and the | merged them while still storing each value once, which is why 3 appears only once in the union. Wrapping both results in sorted turns them into lists with a predictable order, which is what makes them safe to print in a lesson or a test.

Writing s = {} actually creates an empty dictionary, not an empty set.

Dictionaries claimed the brace syntax first, so bare braces mean a dict and an empty set has to be written set().

The trap is convincing because braces containing plain items, such as {1, 2, 3}, really do build a set. Python can tell those apart by looking for colons, and with nothing inside there is nothing to distinguish, so the dict interpretation wins. A quick type(s) check settles it whenever the code is behaving strangely.

Which container do I reach for?

Two questions settle almost every case: do I look things up by position, by key, or not at all? and does the collection need to change after it is built? Position and change point to a list, position without change points to a tuple, lookup by name points to a dict, and neither points to a set.

When in doubt, start with a list. It is the most forgiving choice, and switching later is cheap once one of the patterns in the table becomes obvious. The switch that matters most for performance is list to set, because a membership test on a list gets slower as the list grows while a set stays fast.

For tracking which email addresses have already been invited, the right container is a set.

The requirements match it exactly. Uniqueness is inherent, since an address either has been invited or has not and storing it twice means nothing. The only question ever asked is a membership test, which is the operation sets perform fastest. No order is needed, and no extra data hangs off each address.

The alternatives fall short in specific ways. A dict would be the right answer if each address carried information, such as the date it was invited. A list would work correctly but its in check scans item by item, so it degrades as the invitation count grows into the thousands.

Comparing a total against a distinct total is a two-line job once split and set are combined.

sentence = "the cat and the dog and the bird"
words = sentence.split()
print(len(words))
print(len(set(words)))

Output

8
5

split cuts the sentence at each run of whitespace and returns a list of eight words, which len counts directly. Wrapping that same list in set discards the repeats, leaving the, cat, and, dog, and bird, so the second count is 5.

Nothing is lost in the process, since words still holds the full list and can be counted or looped over afterwards. Comparing the two numbers is a common first look at any text, because a large gap between them signals heavy repetition.