Sets, Maps and Choosing the Right Container

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

a | b        # union         {1,2,3,4,5,6}   A
a & b        # intersection  {3,4}           B
a - b        # difference    {1,2}           C
a ^ b        # symmetric diff{1,2,5,6}       D

a <= b       # subset?
a.isdisjoint(b)   # no overlap at all?

# Each of these is O(len of the smaller set) and runs in C.
# The hand-written equivalent is a nested loop in Python.

# The loop most people write first — O(n × m)
result = []
for u in group_a:
    if u not in group_b:        # O(m) scan of a list
        result.append(u)

# The same thing, O(n + m), and it says what it means
result = set(group_a) - set(group_b)

from collections import Counter

# What everyone writes first:
counts = {}
for w in words:
    if w not in counts:
        counts[w] = 0
    counts[w] += 1

# The same thing:
counts = Counter(words)

counts.most_common(3)      # the three most frequent, already sorted
counts["missing"]          # 0, not a KeyError
counts + other             # element-wise addition of two Counters
counts - other             # element-wise subtraction (drops non-positives)

from collections import defaultdict

# The boilerplate:
groups = {}
for word in words:
    key = word[0]
    if key not in groups:
        groups[key] = []
    groups[key].append(word)

# With defaultdict — the missing key materialises as an empty list:
groups = defaultdict(list)
for word in words:
    groups[word[0]].append(word)

# Or, without importing anything:
groups = {}
for word in words:
    groups.setdefault(word[0], []).append(word)

for user in all_users:              # n
    if user in banned_list:        # m  →  O(n × m)
        ...
# FIX: banned = set(banned_list) once, outside the loop. O(n).

while queue:
    job = queue.pop(0)             # O(n) each  →  O(n²)
# FIX: collections.deque, then popleft(). O(1).

while tasks:
    nxt = min(tasks)               # O(n)
    tasks.remove(nxt)              # O(n) again  →  O(n²)
# FIX: a heap. heapq.heappop(tasks) is O(log n). Chapter 17.

out = ""
for line in lines:
    out += line                    # strings are immutable — this COPIES
                                   # the whole accumulated string each time
# FIX: collect into a list and B.join(parts) at the end. O(n).

# Roughly where the crossover falls in CPython, for membership testing:
#
#   under ~10 items    list scan is usually faster (no hashing cost)
#   10 to ~100         about even; it depends on the data
#   over ~100          the set wins, and the gap grows without limit
#
# So: build the set once and reuse it, and the set is nearly always right.
# Building a set inside a loop to test 5 items is worse than the scan.

# The mistake:
for row in rows:
    if row.id in set(valid_ids):    # rebuilds the set EVERY iteration
        ...

# The fix — hoist it:
valid = set(valid_ids)
for row in rows:
    if row.id in valid:
        ...

# A structure with O(1) insert, delete AND random choice — which no
# single built-in container gives you. Two containers, glued by an index.

import random

class RandomSet:
    def __init__(self):
        self._items = []       # for O(1) random choice by position
        self._index = {}       # value -> its position in _items

    def add(self, x):
        if x in self._index:
            return False
        self._index[x] = len(self._items)
        self._items.append(x)
        return True

    def remove(self, x):
        if x not in self._index:
            return False
        i = self._index.pop(x)
        last = self._items.pop()          # O(1) — always remove the END
        if i < len(self._items):
            self._items[i] = last         # move the last item into the hole
            self._index[last] = i         # and fix its recorded position
        return True

    def random(self):
        return random.choice(self._items)

# The trick in remove(): never delete from the middle of the list — swap
# the last element into the hole instead. Order is not promised, so this
# is free, and it keeps every operation O(1).