Sets and Frozensets

Unordered collections of unique items

A set is a hash table of keys without values: membership tests, insertion and removal are O(1) on average, and duplicates are impossible. Sets are the right tool for de-duplication (set(items)), fast membership checks against a collection used repeatedly, and set algebra: union |, intersection &, difference - and symmetric difference ^, plus issubset (<=) and isdisjoint. Elements must be hashable. Sets are unordered: iteration order is arbitrary and may change between runs for strings, so do not rely on it (to de-duplicate while keeping order, use dict.fromkeys(items)). frozenset is an immutable, hashable set, usable as a dictionary key or as an element of another set (for example, to represent an unordered pair or a combination of tags). Set comprehensions ({x.lower() for x in words}) build sets directly. The cost of building a set is O(n), so converting a list to a set pays off only when you will perform several lookups.

Set algebra for permissions and recommendations

Unions, intersections, differences and frozensets.

required = {"orders:read", "orders:write"}
asha_perms = {"orders:read", "orders:write", "reports:read"}
ravi_perms = {"orders:read"}

print(required <= asha_perms)               # True: subset check
print(required - ravi_perms)                # {'orders:write'}: what Ravi is missing

bought_by_asha = {"pen", "ink", "pad"}
bought_by_meera = {"pen", "stapler"}
print(bought_by_asha & bought_by_meera)     # {'pen'}
print(bought_by_meera - bought_by_asha)     # {'stapler'}: recommend to Asha
print(bought_by_asha ^ bought_by_meera)     # items bought by exactly one of them

emails = ["A@x.com", "b@x.com", "a@x.com", "c@x.com", "B@x.com"]
unique_ordered = list(dict.fromkeys(e.lower() for e in emails))
print(unique_ordered)                       # ['a@x.com', 'b@x.com', 'c@x.com']

# frozenset as a key: unordered pairs of products bought together
pair_counts = {}
for basket in [{"pen", "ink"}, {"ink", "pen", "pad"}, {"pad", "pen"}]:
    items = sorted(basket)
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            pair = frozenset((items[i], items[j]))
            pair_counts[pair] = pair_counts.get(pair, 0) + 1
print(pair_counts[frozenset({"pen", "ink"})])   # 2

A guest list at the door

A set is the bouncer's guest list: checking whether a name is on it is instant, nobody can be on it twice, and two lists can be merged or compared in one step. It does not care in which order guests were added.

Quick check: What is the most efficient way to remove duplicates from a list while preserving the original order?

• set(items)
• sorted(items)
• items.sort()
• list(dict.fromkeys(items))