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.
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 identical 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.
Questions people ask
Does set preserve order? No. Use dict.fromkeys when order matters.
Which is fastest? set() is fastest, dict.fromkeys is close, and both are O(n). The quadratic list version is the one to avoid.
Why is a set unhashable itself? It is mutable. frozenset is the hashable version and can be a set member.
How do I deduplicate by one field? A seen set of that field's values, appending the full object when the field is new.
Is a set always better than a list for membership? Above about ten elements, yes. Below that, a scan wins on constant factors.
How do I deduplicate a huge stream? A set if it fits; a Bloom filter or HyperLogLog if approximate counting is acceptable.
Recap in one screen
list(set(x)) loses order; list(dict.fromkeys(x)) preserves it; both are O(n).- Deduplicating by scanning a growing list is O(n²) — keep a
seen set alongside the output list. - Elements must be hashable; convert lists to tuples and dicts to sorted item tuples.
- Set operations (
&, |, -, ^) replace nested loops and run in C. - Normalise case, whitespace and Unicode before deduplicating, and never assume a set is sorted.