Python list.append if not in list vs set.add performance [duplicate]

Question

Which is more performant, and what is asymptotic complexity (or are they equivalent) in Python?

set.add(12)

if 12 not in somelist:
    somelist.append(12)

Answer 1

The set is far faster, in general. Testing for membership in a list is O(n), linear in the size of the list. Adding to a set is O(1), independent of the number of the items in the list. Aside from that, the list code makes two function calls: one to check if 12 is in the list, another to add it, while the set operation makes just one call.

Note that the list solution can be fast, though, when the item doesn't need to be added to the list because it was found early in the list.

# Add item to set
$ python -m timeit -s 's = set(range(100))' 's.add(101)'
10000000 loops, best of 3: 0.0619 usec per loop

# Add item not found in list
$ python -m timeit -s 'l = list(range(100))' 'if 101 not in l: l.append(101)'
1000000 loops, best of 3: 1.23 usec per loop

# "Add" item found early in list
$ python -m timeit -s 'l = list(range(100))' 'if 0 not in l: l.append(0)'
10000000 loops, best of 3: 0.0214 usec per loop

# "Add" item found at the end of the list
$ python -m timeit -s 'l = list(range(102))' 'if 101 not in l: l.append(101)'
1000000 loops, best of 3: 1.24 usec per loop