Learn the concept
Algorithmic complexity describes how work grows with input size. A nested comparison of every pair grows differently from one pass using a lookup. Practical performance also depends on constants, input shape, I/O, and memory allocation.
Measure before optimizing. Use a representative input and compare outputs as well as execution time. A faster implementation that changes duplicate handling is a behavior change, not merely an optimization. Separate CPU time from time spent waiting on dependencies.
Avoid repeatedly copying a growing list or concatenating large immutable strings in a loop when a collection-and-join approach is appropriate. Streaming reduces peak memory only if later stages also preserve incremental processing. Sorting the entire stream still requires collecting data.
Run and inspect
def unique_in_order(items):
seen = set()
output = []
for item in items:
if item not in seen:
seen.add(item)
output.append(item)
return output
assert unique_in_order(["b", "a", "b"]) == ["b", "a"]
Your exercise
Compare list-membership deduplication with set-backed deduplication on increasing input sizes. Preserve the order of first occurrence.
Check your understanding
The results match and the report explains expected growth without claiming a universal timing from one machine.
Guided workshop: remove repeated work deliberately
A duplicate detector that scans every earlier record for each new record performs roughly n(n-1)/2 comparisons in the all-distinct case. A set-based detector usually gives much faster membership checks at the cost of retaining identifiers. Measure the actual workload before claiming a speedup.
# academy-check
from functools import wraps
def count_calls(function):
calls = {"count": 0}
@wraps(function)
def wrapped(*args, **kwargs):
calls["count"] += 1
return function(*args, **kwargs)
wrapped.calls = calls
return wrapped
@count_calls
def unique_ids(records):
return {record["id"] for record in records}
assert unique_ids([{"id": "a"}, {"id": "a"}]) == {"a"}
assert unique_ids.calls["count"] == 1
assert unique_ids.__name__ == "unique_ids"
The decorator returns a closure that remembers calls and the original function. wraps preserves metadata useful to logs and debugging. This example counts function invocations, not internal comparisons; choose measurements that answer the question you are investigating.
Exercise: implement both duplicate detectors, generate 1,000 and 2,000 distinct IDs, and compare elapsed time using time.perf_counter(). Run several repetitions and report environment, input size, and median time. Do not assert an exact time in a unit test: unrelated machine load changes timing.
Worked interpretation: doubling the input size tends to increase a quadratic comparison count by about four, while set membership usually scales closer to linearly overall. Small timings may be dominated by setup and measurement noise. A set also uses additional memory, and hash operations have their own costs; complexity describes growth, not a universal latency guarantee.
Checkpoint: a callback is a function passed as a value; a closure remembers an enclosing binding; a decorator transforms a callable. Explain each using this example. For a source too large to keep all IDs in memory, move uniqueness into an indexed database rather than claiming a generator alone solves the problem.