Run it
The three deduplication idioms and what each does to order, the set operators against their loop equivalents. And the membership timing that motivates all of it.
Building on the same setup, the next block shows the remaining cases.
Why the set is fast
A list must scan to know whether it already contains something — O(n) per check, so O(n²) to deduplicate by repeated scanning.
A set hashes the value and looks in one place — O(1) on average, so O(n) overall.
Both versions preserve order. The first is quadratic and is what people write before they think about it, and on 100,000 items it takes minutes rather than milliseconds.
Keeping the list and a set alongside it is the standard pattern: the list holds the ordered output, the set answers the membership question.
The requirement: hashable elements
Sets and dictionaries need hashable elements, so deduplication by value fails on mutable ones:
For unhashable items, convert to a hashable canonical form:
| Item type | Canonical key |
|---|
list | tuple(x) |
set | frozenset(x) |
dict | tuple(sorted(x.items())) |
| Nested structure | json.dumps(x, sort_keys=True) |
| Custom object | A tuple of its identifying fields |
The JSON option works and is slow, and it is sensitive to types — 1 and 1.0 serialise differently. Prefer an explicit tuple of the fields that define identity.
What you gain and what you give up
Gain: membership in O(1) rather than O(n), and uniqueness enforced for free.
Give up: order, duplicates, indexing (s[0] is a TypeError), and the ability to hold unhashable elements. You cannot put a list in a set, though you can put a tuple.
Converting costs O(n), so a single membership test on a small list is not worth it. More than a couple of tests, or a large collection, and it is.
Deduplicating three ways
set(seq) — fastest, order destroyed.
sorted(set(seq)) — deduplicated and in sorted order, which is not the same as original order and is often what people accidentally ship.
list(dict.fromkeys(seq)) — deduplicated in first-seen order, one pass, and the one to remember. Dicts have preserved insertion order since 3.7, so this is a guarantee rather than a trick.
The operators that replace loops
a & b intersection, a | b union, a - b difference, a ^ b symmetric difference, a <= b subset. Each replaces a loop with a membership test inside it — which is to say, each replaces an accidental O(n·m) with an O(n + m).
"Which users are in A but not B" is a - b. Writing that as a comprehension over a list is the most common form of the quadratic trap.
Choosing between the containers
| | list | set | dict |
|---|
| Ordered | Yes | No | Yes (insertion) |
| Duplicates | Yes | No | Keys unique |
in | O(n) | O(1) | O(1) on keys |
| Indexing | Yes | No | By key |
| Elements must be hashable | No | Yes | Keys only |
| Memory | Lowest | Higher | Highest |
The decision is usually straightforward:
Need order and duplicates → list. Need membership testing only → set. Need associated data → dict. Need order without duplicates → dict.fromkeys, or a list plus a set.
And the sets themselves support the operations that make them worth reaching for beyond deduplication:
Those replace loops. "Which users are in both groups?" is a & b, not a nested loop. And it runs in C at O(min(len(a), len(b))).
Where deduplication goes wrong
Assuming a set is sorted. set([3, 1, 2]) may print as {1, 2, 3} for small integers because of how they hash. Add a string or a larger number and the illusion vanishes. Never rely on it.
Deduplicating floats. 0.1 + 0.2 and 0.3 are different values, so they do not deduplicate. Round to a fixed precision first if that is the intent.
1 == True and 1.0 == 1. These are equal and hash equally, so {1, True, 1.0} is {1}. Surprising and correct.
Case and whitespace. "Alice" and "alice " are distinct. Normalise before deduplicating — strip, casefold, and NFC-normalise Unicode.
Deduplicating objects by identity. Two distinct objects with the same field values are different set members unless __eq__ and __hash__ are defined.
Memory on large inputs. Deduplicating a hundred million items builds a set of them all. For a stream where approximate counting suffices, a Bloom filter or HyperLogLog uses a tiny fraction of the memory.
For the underlying ideas, see sets, hash tables and lists.