Luke Lee

Software Engineer

Web + Desktop + Science

Fork me on Github

Speed up list searches

Need a way to speed up searching Python lists, give sets a try.

    >>> x = set(range(100))
    >>> y = range(100)
    >>> %timeit 100 in x
    10000000 loops, best of 3: 50 ns per loop
    >>> %timeit 100 in y
    1000000 loops, best of 3: 1.78 us per loop

Why the dramatic speed up? Remember sets are un-ordered and don't allow duplicates. Thus, they are actually implemented using dictionaries.

The set documentation explains this very well if you need a refresher:

The set classes are implemented using dictionaries. Accordingly, the requirements for set elements are the same as those for dictionary keys; namely, that the element defines both eq() and hash(). As a result, sets cannot contain mutable elements such as lists or dictionaries. However, they can contain immutable collections such as tuples or instances of ImmutableSet. For convenience in implementing sets of sets, inner sets are automatically converted to immutable form, for example, Set([Set(['dog'])]) is transformed to Set([ImmutableSet(['dog'])]).

Published: 03-01-2013 17:34:00

lukelee.net