Gavin Wiggins

Use Sets and Dictionaries for Fast Lookup

Published on January 28, 2026

In Python, a set is implemented as a hash table which enables O(1) lookup even for very large sets. The same goes for dictionaries too. Contrast this to lists which have an O(n) lookup. Basically, if you need to quickly determine if "a is in b" then b should be a set or dictionary. Keep this in mind for other programming languages too, such as Swift which has sets, arrays, and dictionaries.

The example below compares the lookup speed for a set and list. Results are given after the example code. Notice how much faster the set lookup is compared to the list, especially when looking up a larger value. The script to run this example is available in the pythonic repo on GitHub.

# set_lookup.py

import time
import textwrap


def list_lookup(n: int, x: int) -> float:
    """Run list lookup example."""
    big_list = list(range(n))

    tic = time.perf_counter()
    print(x in big_list)
    toc = time.perf_counter()

    return toc - tic


def set_lookup(n: int, x: int) -> float:
    """Run set lookup example."""
    big_list = list(range(n))
    big_set = set(big_list)

    tic = time.perf_counter()
    print(x in big_set)
    toc = time.perf_counter()

    return toc - tic


def main():
    """Run examples."""

    n = 2_000_000  # size of set or list
    x = 999        # value to lookup

    t_list = list_lookup(n, x)
    t_set = set_lookup(n, x)

    results = f"""
    n = {n:,}
    x = {x:,}
    List lookup: {t_list:.8f} s
    Set lookup:  {t_set:.8f} s
    Set speedup: {t_list / t_set:.1f}x
    """
    print(textwrap.dedent(results))


if __name__ == "__main__":
    main()

n = 2,000,000
x = 999
List lookup: 0.00002254 s
Set lookup:  0.00001654 s
Set speedup: 1.4x

n = 2,000,000
x = 999,999
List lookup: 0.00471483 s
Set lookup:  0.00002492 s
Set speedup: 189.2x