groupby and Sorted Input

## The algorithm, stated exactly `itertools.groupby(iterable, key=None)` returns an iterator that yields `(computed_key, group)` pairs. Its whole algorithm is: 1. pull one item from the source iterator; 2. compute `key(item)` (with no key function, the item itself is the key); 3. if that computed key is equal to the previous one, the item belongs to the current group; 4. otherwise, close the current group and open a new pair. Equality is tested with `==` on the **computed keys**, not on the items. There is no sorting step, no buffering of earlier items, and no lookahead beyond the one item groupby is holding. It is a *run detector*: it finds maximal runs of adjacent items that share a key. So "grouping" here does not mean what it means in a set-oriented world, where all records with a given key end up in one bucket regardless of position. In groupby, position is everything. ```python from itertools import groupby rows = [("a", 1), ("b", 2), ("a", 3)] print([(k, len(list(g))) for k, g in groupby(rows, key=lambda r: r[0])]) # [('a', 1), ('b', 1), ('a', 1)] -- 'a' appears twice rows.sort(key=lambda r: r[0]) print([(k, [v for _, v in g]) for k, g in groupby(rows, key=lambda r: r[0])]) # [('a', [1, 3]), ('b', [2])] ``` The first line is the bug people actually ship: no exception, no warning, just a report where one recipient, one customer or one error code shows up under several headings and every downstream count is wrong. ## Why it is built that way The single-pass design buys two things. First, **streaming**: groupby holds one item and one key, so it can run over a file being read line by line, or over an endless feed, and emit each group the moment it is complete. A dictionary-based grouping cannot do that — it must see the last record before it can promise that any bucket is final. Second, **adjacency as semantics**: some problems are genuinely about runs, not about sets, and for those, unsorted input is not a bug but the point. The price is the precondition. If you want set-style grouping, you owe groupby the invariant that equal keys are adjacent, and sorting by the same key is the ordinary way to establish it. ## Sorting by the same key Two rules matter. **Same key function.** Sorting by `created_at` and grouping by `user_id` produces silently fragmented groups, because the sort establishes adjacency for the wrong attribute. If you need groups by user and chronological order inside each group, sort by the composite `(user_id, created_at)` and group by `user_id` alone — the sort is stable and the secondary component orders within each run. **Sorted is not the only way.** Any source that already guarantees adjacency works: an export file written in key order, a query result already ordered by the group column, or several sorted streams merged with `heapq.merge`. That is exactly when groupby earns its keep, because you pay nothing to get the ordering. `sorted()` returns a new list, so it materializes the entire input; an in-place list sort avoids the copy but still needs the whole sequence in memory. Either way, once you have sorted, you have already given up the streaming property that motivated groupby — which is why a plain dictionary accumulation is often the better tool for unsorted data. ## When you *want* unsorted input Feeding groupby unordered data is correct whenever the question is about consecutive runs: - collapsing consecutive duplicates, or run-length encoding a sequence; - splitting a log by contiguous stretches of the same severity; - cutting a sequence of events into blocks that share a flag, in arrival order. ```python from itertools import groupby s = "aaabbbbcca" print([(ch, sum(1 for _ in run)) for ch, run in groupby(s)]) # [('a', 3), ('b', 4), ('c', 2), ('a', 1)] ``` Here the trailing `('a', 1)` is the answer, not a defect. ## Smaller traps in the same family - The yielded key is the **computed** key, not the original item; with no key function they coincide. - The key function is called once per item, in order; it must be pure and cheap, and it must return values that compare equal for items you consider the same. A key returning a fresh object each call makes every item its own group. - Keys are compared with `==`, so a key type with an unusual `__eq__` (or a float `nan`, which is never equal to itself) will fragment groups even in sorted input. - Keys must be *comparable* for the sort, but they need not be hashable — the mirror image of a dictionary-based grouping, which needs hashable keys and no ordering at all.