Python membership tests: list scans versus set lookups

Problem. Repeated membership tests over a Python list compare candidate elements in order, so a miss examines every element in this workload.^[6]

Baseline. Python’s CPython complexity table lists x in l as O(n), while x in s is O(1) on average and can degrade when hash collisions are severe.^[1]

Solution. Build a set once, then reuse x in values_set for the repeated checks. CPython v3.13.5 computes an initial set probe from the key’s hash and table size.^[4]

Measured result. At n = 32,768, 1,000 absent queries took a median 1,404.417 ms with a list and 0.061351 ms with a set, a 22,891.52× ratio between those medians on this host.

Reproduce the result

Complete code

from __future__ import annotations
import gc
import platform
import statistics
import sys
import time
from collections.abc import Callable, Iterable
SEED = 20261021
SIZES = (64, 512, 4096, 32768)
SCENARIOS = ("hit_front", "hit_middle", "hit_end", "miss")
QUERY_COUNT = 1_000
WARMUPS = 1
TRIALS = 5
def values_for(size: int) -> list[int]:
    return [SEED + index * 1_000_003 for index in range(size)]
def queries_for(values: list[int], scenario: str) -> list[int]:
    if scenario == "hit_front":
        target = values[0]
    elif scenario == "hit_middle":
        target = values[len(values) // 2]
    elif scenario == "hit_end":
        target = values[-1]
    elif scenario == "miss":
        target = SEED - 1
    else:
        raise ValueError(f"unknown scenario: {scenario}")
    return [target] * QUERY_COUNT
def count_list_hits(collection: list[int], queries: Iterable[int]) -> int:
    hits = 0
    for query in queries:
        if query in collection:
            hits += 1
    return hits
def count_set_hits(collection: set[int], queries: Iterable[int]) -> int:
    hits = 0
    for query in queries:
        if query in collection:
            hits += 1
    return hits
def measure(
    collection: list[int] | set[int],
    queries: list[int],
    contains: Callable[[list[int] | set[int], Iterable[int]], int],
) -> tuple[list[float], int]:
    samples: list[float] = []
    result: int | None = None
    for trial in range(WARMUPS + TRIALS):
        started = time.perf_counter_ns()
        current = contains(collection, queries)
        elapsed_ms = (time.perf_counter_ns() - started) / 1_000_000
        if result is None:
            result = current
        elif current != result:
            raise AssertionError(f"hit count changed between trials: {result} != {current}")
        if trial >= WARMUPS:
            samples.append(elapsed_ms)
    assert result is not None
    return samples, result
def main() -> None:
    gc_was_enabled = gc.isenabled()
    gc.disable()
    try:
        results: dict[tuple[str, str, int], tuple[list[float], int]] = {}
        for size in SIZES:
            values = values_for(size)
            list_collection = list(values)
            set_collection = set(values)
            for scenario in SCENARIOS:
                queries = queries_for(values, scenario)
                list_outcomes = [query in list_collection for query in queries]
                set_outcomes = [query in set_collection for query in queries]
                if list_outcomes != set_outcomes:
                    raise AssertionError(f"membership outcomes differ for n={size} scenario={scenario}")
                results[("list", scenario, size)] = measure(list_collection, queries, count_list_hits)
                results[("set", scenario, size)] = measure(set_collection, queries, count_set_hits)
    finally:
        if gc_was_enabled:
            gc.enable()
    print(f"python={sys.version.split()[0]}")
    print(f"implementation={platform.python_implementation()}")
    print(f"platform={platform.system()} {platform.release()}")
    print(f"machine={platform.machine()}")
    print(f"seed={SEED}")
    print(f"sizes={','.join(str(size) for size in SIZES)}")
    print(f"scenarios={','.join(SCENARIOS)}")
    print(f"query_count={QUERY_COUNT}")
    print(f"warmups={WARMUPS}")
    print(f"trials={TRIALS}")
    print("timer=time.perf_counter_ns; collection_build_outside_timing=True; gc_disabled_during_timing=True")
    print("correctness=all_query_outcomes_match")
    print("method,scenario,size,expected_hits,median_ms,per_query_us,samples_ms,hits")
    expected_hits = {scenario: QUERY_COUNT if scenario != "miss" else 0 for scenario in SCENARIOS}
    for method in ("list", "set"):
        for scenario in SCENARIOS:
            for size in SIZES:
                samples, hits = results[(method, scenario, size)]
                if hits != expected_hits[scenario]:
                    raise AssertionError(f"unexpected hit count for {method} {scenario} n={size}")
                median_ms = statistics.median(samples)
                per_query_us = median_ms * 1_000 / QUERY_COUNT
                sample_text = ",".join(f"{sample:.6f}" for sample in samples)
                print(
                    f"{method},{scenario},{size},{expected_hits[scenario]},{median_ms:.6f},"
                    f"{per_query_us:.6f},{sample_text},{hits}"
                )
    size = SIZES[-1]
    list_median = statistics.median(results[("list", "miss", size)][0])
    set_median = statistics.median(results[("set", "miss", size)][0])
    print(f"headline_size={size}")
    print(f"headline_scenario=miss")
    print(f"headline_speedup={list_median / set_median:.2f}x")
if __name__ == "__main__":
    main()

Command

$ python3 membership_benchmark.py

Output

python=3.13.5
implementation=CPython
platform=Linux 6.12.47+rpt-rpi-v8
machine=aarch64
seed=20261021
sizes=64,512,4096,32768
scenarios=hit_front,hit_middle,hit_end,miss
query_count=1000
warmups=1
trials=5
timer=time.perf_counter_ns; collection_build_outside_timing=True; gc_disabled_during_timing=True
correctness=all_query_outcomes_match
method,scenario,size,expected_hits,median_ms,per_query_us,samples_ms,hits
list,hit_front,64,1000,0.110202,0.110202,0.112666,0.110999,0.109980,0.110202,0.110073,1000
list,hit_front,512,1000,0.115111,0.115111,0.115111,0.113739,0.113481,0.115221,0.115444,1000
list,hit_front,4096,1000,0.110221,0.110221,0.110221,0.110333,0.110259,0.110036,0.109962,1000
list,hit_front,32768,1000,0.109480,0.109480,0.109906,0.109814,0.109480,0.109425,0.109314,1000
list,hit_middle,64,1000,0.806550,0.806550,0.816679,0.806550,0.806475,0.806420,0.824105,1000
list,hit_middle,512,1000,6.057509,6.057509,6.043305,6.051787,6.058472,6.057509,6.224674,1000
list,hit_middle,4096,1000,49.831487,49.831487,50.202132,49.690507,49.752895,49.831487,50.150633,1000
list,hit_middle,32768,1000,551.365725,551.365725,573.366426,551.365725,550.351215,547.877994,577.106269,1000
list,hit_end,64,1000,1.465803,1.465803,1.483322,1.465803,1.474044,1.465581,1.465360,1000
list,hit_end,512,1000,11.801243,11.801243,11.801243,11.781169,11.770669,13.330545,12.182425,1000
list,hit_end,4096,1000,110.442781,110.442781,116.837120,146.718446,110.442781,98.773055,98.328688,1000
list,hit_end,32768,1000,1152.719627,1152.719627,1252.630099,1151.290711,1201.644622,1152.719627,1139.926412,1000
list,miss,64,0,1.420026,1.420026,1.431100,1.419211,1.418749,1.435248,1.420026,0
list,miss,512,0,11.689040,11.689040,11.689040,11.677855,11.713373,11.746280,11.664965,0
list,miss,4096,0,89.526886,89.526886,89.292610,89.250073,90.366917,90.130214,89.526886,0
list,miss,32768,0,1404.417440,1404.417440,1415.528872,1404.417440,1409.059832,1361.327792,1124.903441,0
set,hit_front,64,1000,0.115036,0.115036,0.117517,0.115481,0.115036,0.114907,0.115018,1000
set,hit_front,512,1000,0.130592,0.130592,0.130721,0.148184,0.128092,0.130592,0.127537,1000
set,hit_front,4096,1000,0.115943,0.115943,0.115981,0.115943,0.115703,0.116777,0.115647,1000
set,hit_front,32768,1000,0.115999,0.115999,0.115869,0.115721,0.179258,0.116592,0.115999,1000
set,hit_middle,64,1000,0.116054,0.116054,0.118573,0.116240,0.116036,0.115999,0.116054,1000
set,hit_middle,512,1000,0.118258,0.118258,0.118684,0.114648,0.163647,0.118258,0.117333,1000
set,hit_middle,4096,1000,0.122203,0.122203,0.122165,0.122259,0.121888,0.122203,0.122351,1000
set,hit_middle,32768,1000,0.121888,0.121888,0.121888,0.122017,0.121666,0.122259,0.121536,1000
set,hit_end,64,1000,0.116647,0.116647,0.118350,0.116740,0.116647,0.116573,0.116647,1000
set,hit_end,512,1000,0.117702,0.117702,0.117888,0.117888,0.117611,0.117647,0.117702,1000
set,hit_end,4096,1000,0.122092,0.122092,0.122314,0.122351,0.122073,0.122092,0.122073,1000
set,hit_end,32768,1000,0.123462,0.123462,0.123592,0.123462,0.154370,0.122480,0.122592,1000
set,miss,64,0,0.066814,0.066814,0.067036,0.066814,0.066833,0.066703,0.066722,0
set,miss,512,0,0.073629,0.073629,0.073629,0.078684,0.073685,0.073444,0.073295,0
set,miss,4096,0,0.061314,0.061314,0.061518,0.061573,0.061314,0.061277,0.061241,0
set,miss,32768,0,0.061351,0.061351,0.061611,0.061407,0.061351,0.061240,0.061203,0
headline_size=32768
headline_scenario=miss
headline_speedup=22891.52x

Environment

The run used CPython 3.13.5 on Linux 6.12.47+rpt-rpi-v8 with an aarch64 processor. The benchmark uses only the Python standard library. It times the membership loop with time.perf_counter_ns(), which returns nanoseconds and avoids the precision loss of floating-point seconds.^[3]

Methodology

The script checks every boolean outcome from the list and set for each scenario before collecting timings. It tests collections of 64, 512, 4,096 and 32,768 integers with four deliberate query positions: a hit at the front, a hit in the middle, a hit at the end and an absent value. Each case runs 1,000 identical queries, one untimed warm-up and five timed trials. The list and set are built before the timer starts. Garbage collection is disabled during the timed calls and restored afterwards. The output keeps all five samples and reports their median.

Original Read0nly infographic for an absent-membership benchmark. It shows the benchmark's list path comparing all 32,768 positions and the set path using an average-case hash lookup; the captured medians for 1,000 queries were 1,404.417 ms and 0.061351 ms on CPython 3.13.5. — For 1,000 absent queries against 32,768 integers, the captured median was 1,404.417 ms for the benchmark’s list path and 0.061351 ms for its set path, a 22,891.52× ratio between those medians. The set complexity claim is average case; the timings belong to this host and method.

The problem

A membership test asks whether a value occurs in a collection. In the CPython v3.13.5 list implementation used for this discussion, the containment loop checks items in order and returns when comparison succeeds or when it reaches the end.^[6] An absent query therefore has no early exit in that loop.

That makes a short expression such as if record_id in records sensitive to the collection’s size and to where a match appears. The code is tidy. The scan underneath may be doing rather more walking than the line suggests.

Baseline complexity

The measured list cases make the exit position visible. At n = 32,768, a front hit took 0.109480 ms for 1,000 queries, a middle hit took 551.365725 ms, an end hit took 1,152.719627 ms and a miss took 1,404.417440 ms. The output reports the median values from the five trials.

The complexity page describes x in l as O(n) and x in s as O(1) for the average case. It also states that set operations can become O(n) in the worst case when collisions are severe.^[1] Those are growth descriptions, not timing predictions for this Raspberry Pi.

The solution

A set trades sequence order for membership-oriented storage. Python’s tutorial lists membership testing among its basic uses and notes that a set contains distinct elements.^[2] The set must be built before the repeated lookup loop, and its elements must be hashable.^[5]

The CPython v3.13.5 implementation begins a lookup from the key’s hash modulo the table size, then probes according to its collision-handling rules.^[4] The benchmark measures only the repeated in operations. Set construction and the memory it occupies are outside the timer, so the result answers a narrow question: what happens when an already-built collection receives many membership checks?

What the measurement shows

The list and set returned identical boolean outcomes for every query in all four scenarios. List time stayed almost flat for a front hit because the first comparison succeeds. Middle, end and absent queries became more expensive as the collection grew. Set medians stayed close together across sizes in this run, including the absent-query case.

The headline ratio is large because the workload combines a 32,768-item scan with 1,000 misses, while the set is already built. It is a useful boundary result for that workload, not a conversion factor for every membership test.

Practical applications

A parser that repeatedly checks whether an identifier has already been seen can keep those identifiers in a set. The lookup mechanism matches the question, while the original input list can remain separate when order matters. This benchmark measures the membership operation, not parsing or input conversion.

A graph traversal commonly keeps a visited set so each discovered vertex can be checked before it is queued again. The set avoids rescanning the visited collection on every edge, but the article does not measure graph construction, adjacency storage or traversal order.

An allowlist or blocklist can use a set when the values are hashable and the list is rebuilt infrequently relative to the number of checks. Rebuilding the set for every single query would move its construction cost into the workload and change the decision.

A batch filter can first build a set of accepted IDs, then test incoming rows with item_id in accepted. If the result must preserve the allowlist’s order or support slicing, retain a list as well because sets do not provide sequence indexing.^[5]

Where it stops helping

This experiment uses integers, one process and repeated identical queries. It does not measure set construction, memory usage, custom objects, adversarial hash collisions, concurrent access or a mixed hit distribution. The host runs one CPython build, and the official complexity page warns that other Python implementations can have different performance characteristics.^[1]

The practical choice depends on the full workload. Keep a list when order, duplicates, indexing or slicing are part of the data model. Build a set when repeated membership checks dominate and the extra storage and hashability requirement fit the program.