Skip to content

Which duplicate survives

Level: 201 · for Python programmers

One line: "Remove duplicates" is two decisions every idiom makes silently, which copy stands for the group and what order the survivors come out in, and {key(x): x for x in items} makes the one combination nobody would choose: the last copy, in the first copy's place.

Two decisions, not one

A list has duplicates when some of its items are equal. Keeping one of each forces two choices that the phrase "remove duplicates" hides:

  1. Which copy represents the group. Equal is not identical: 'Pear' and 'PEAR' are equal ignoring case, and 1.0, 1 and True are equal outright. The survivor is one particular object, with its own spelling and type.
  2. What order the survivors come in. First-seen order, sorted order, or whatever order a hash table happens to hold them in.

Every idiom answers both, usually without saying so:

Idiom Survivor Order
list(set(items)) first seen hash order, which for strings changes between runs
sorted(set(items)) first seen sorted
list(dict.fromkeys(items)) first seen first-seen
{key(x): x for x in items}.values() last seen first-seen position
d.setdefault(key(x), x) in a loop first seen first-seen
sort by key, then groupby, first of each run first seen (sort is stable) sorted
[k for k, _ in groupby(items)] first of each run original, adjacent repeats only

The output

Verified output of which_duplicate_survives_py.py — regenerated by tools/run_examples.py, never hand-typed.

1. THE LIST, AND WHAT 'THE SAME' MEANS
   words = ['Pear', 'fig', 'pear', 'Fig', 'apple', 'PEAR']
   Exact duplicates: none. Duplicates ignoring case: pear x3, fig x2.

2. EXACT DUPLICATES: FIVE IDIOMS, FOUR ORDERS
   nums = [3, 1, 3, 2, 1, 3]
   list(set(nums))                [1, 2, 3]          hash order: here it looks sorted, by luck
   sorted(set(nums))              [1, 2, 3]          sorted, on purpose
   list(dict.fromkeys(nums))      [3, 1, 2]          first-seen order
   seen-set loop                  [3, 1, 2]          first-seen order, the long way
   [k for k, _ in groupby(nums)]  [3, 1, 3, 2, 1, 3] adjacent repeats only
   groupby, like Rust's dedup and ABAP's DELETE ADJACENT DUPLICATES,
   only merges neighbours: sort first, or it removes nothing useful.

3. DUPLICATES BY A KEY: WHICH SPELLING SURVIVES?
   {w.lower(): w for w in words}.values()   ['PEAR', 'Fig', 'apple']
     keys keep their FIRST position, values are overwritten by the LAST:
     'PEAR' sits where 'Pear' was. Nobody chose that combination.
   d.setdefault(w.lower(), w)               ['Pear', 'fig', 'apple']
     setdefault never overwrites, so the first spelling wins, in first place.
   sort by key, then groupby, take first     ['apple', 'fig', 'Pear']
     sorted order, and the first of each run: sorted() is stable, so that
     is also the first seen. ABAP's SORT ... STABLE + DELETE ADJACENT
     DUPLICATES COMPARING and Rust's sort_by_key + dedup_by_key do the same.

4. EQUAL IS NOT IDENTICAL: THE SURVIVOR KEEPS ITS TYPE
   set(mixed)                             {1.0, 2}
   list(dict.fromkeys(mixed))             [1.0, 2]
   list(dict.fromkeys(reversed(mixed)))   [2, True]
   mixed = [1.0, 1, True, 2]: 1.0, 1 and True are equal and hash alike, so they are
   one member, and whichever arrives first is the one you keep.

5. UNHASHABLE ITEMS
   set([[1, 2], [3], [1, 2]]) -> TypeError
   list(dict.fromkeys(map(tuple, rows)))  -> [(1, 2), (3,)]   hash a frozen copy
   'if r not in out: out.append(r)'        -> [[1, 2], [3]]   works on anything, but
   each 'in' scans the list: fine for ten items, quadratic for a million.

What the run shows

Section 2 is the exact-duplicate case. list(set(nums)) happens to come out sorted for small integers, because an integer's hash is itself; with strings it does not, and the order changes from run to run (see hash() is not stable across runs). dict.fromkeys is the idiom for "remove duplicates, keep the order": a dict's keys are a set that remembers insertion order. groupby merges only neighbours, which is the rule Rust's dedup and ABAP's DELETE ADJACENT DUPLICATES share.

Section 3 is the trap. Deduplicating by a key with a dict comprehension, {w.lower(): w for w in words}, looks like dict.fromkeys with a key, but a dict keeps a key's first position and overwrites its value every time. So the result has 'PEAR', the last spelling, sitting where 'Pear', the first, used to be. setdefault never overwrites, so it keeps the first spelling in the first place. Sorting by the key and taking the first of each run gives sorted order with the first-seen spelling, because sorted() is stable.

Section 4 shows that the survivor keeps its type. 1.0, 1 and True are one member of a set, since they are equal and hash alike, and whichever arrives first is the object you keep: [1.0, 2] one way round, [2, True] the other. The equality rule is the one in A set is a hash table.

Section 5 is the unhashable case. A list of lists cannot go into a set or be a dict key; deduplicate a hashable copy (map(tuple, rows)), or fall back to if r not in out, which works on anything and is quadratic.

The Rust view

Rust makes both choices visible. Vec::dedup and dedup_by_key remove adjacent repeats and keep the first of each run, so the idiom is sort (or sort_by_key, which is stable) and then dedup. To keep first-seen order, filter with a HashSet: seen.insert(x) returns true only the first time. There is no equivalent of Python's 1 == 1.0 collapse, because a Vec<i32> cannot hold a float. See the Rust library's set operations ↗, whose last section compares the two answers.

If you are coming from ABAP

SORT and DELETE ADJACENT DUPLICATES FROM itab COMPARING … are one operation in two statements, exactly like Python's sort-then-groupby: the delete compares neighbours only and keeps the first row of each run, so the table must be sorted by the same fields first, and SORT … STABLE makes "first" mean first-seen. The alternative is to insert rows into a table with a UNIQUE KEY, where the first row wins and every later duplicate just sets sy-subrc = 4, the setdefault behaviour. ABAP never produces the last-copy-in-first-place mix of section 3. See the ABAP library's SORT and DELETE ADJACENT DUPLICATES ↗ and sets in ABAP ↗. (Not machine-checked — CI cannot run ABAP.)

Try it

  1. Search your code for list(set( and check whether anything downstream depends on the order it returns. Run it twice with PYTHONHASHSEED=1 and PYTHONHASHSEED=2 on real data to see.
  2. Find a place that deduplicates records by a field with a dict comprehension, {r['id']: r for r in rows}, and decide whether you meant the last record per id or the first. If the first, rewrite it with setdefault.
  3. Deduplicate a column of names from one of your files case-insensitively, and print which spelling each method kept.
  4. Take a list of lists from your code and time if r not in out against dict.fromkeys(map(tuple, rows)) at its real size.

Practice

Eight lines, and the one that keeps the last spelling. Write down what each prints. names = ['ann', 'Bob', 'ANN', 'bob', 'cy', 'Ann'].

  1. sorted(set(names))
  2. list(dict.fromkeys(names))
  3. list(dict.fromkeys(n.lower() for n in names))
  4. list({n.lower(): n for n in names}.values())
  5. [k for k, _ in groupby(['b', 'a', 'a', 'b', 'b'])]
  6. list(dict.fromkeys([1, 1.0, True]))
  7. list(dict.fromkeys([True, 1.0, 1]))
  8. len(set([0, 0.0, False, '', None]))

Then: say why line 1 puts 'ANN' before 'ann', and rewrite line 4 so it keeps the first spelling of each name.

Answers

Verified output of which_duplicate_survives_kata_py.py — regenerated by tools/run_examples.py, never hand-typed.

1. sorted(set(names))                               ['ANN', 'Ann', 'Bob', 'ann', 'bob', 'cy']
2. list(dict.fromkeys(names))                       ['ann', 'Bob', 'ANN', 'bob', 'cy', 'Ann']
3. list(dict.fromkeys(n.lower() for n in names))    ['ann', 'bob', 'cy']
4. list({n.lower(): n for n in names}.values())     ['Ann', 'bob', 'cy']
5. [k for k, _ in groupby(['b', 'a', 'a', 'b', 'b'])] ['b', 'a', 'b']
6. list(dict.fromkeys([1, 1.0, True]))              [1]
7. list(dict.fromkeys([True, 1.0, 1]))              [True]
8. len(set([0, 0.0, False, '', None]))              3

Line 1 sorts by code point, and every uppercase ASCII letter comes before every lowercase one. Line 4 keeps 'Ann' because the comprehension overwrites the value each time the key recurs; d = {} then d.setdefault(n.lower(), n) for each name keeps 'ann'. Line 8 is 3: 0, 0.0 and False are one member, and '' and None are two more.

See also