Optimising "if number in list" in python

Question

I have a big (~10⁶) list of floats in python, to which I make repeated calls if number in list. The list does not change. Is there any way to speed this process up, say by sorting the list, and taking advantage of its being sorted?

turn the list into a set – inspectorG4dget Oct 19 '15 at 16:31 — inspectorG4dget, Oct 19 '15 at 16:31

score 0 · Answer 1 · answered Oct 19 '15 at 16:33

0

You should change your list to set (or frozenset if set is constant).

Example:

l = [1, 2, 3]
s = set(l)  # frozenset(l)
obj in l  # O(n) lookup
obj in s  # O(1) lookup

answered Oct 19 '15 at 16:33

Łukasz Rogalski

22,092
8
59
93

You'd probably say something about the efficiency of `set(big_list_with_1000000_elements)`. – vaultah Oct 19 '15 at 16:35

score 0 · Answer 2 · answered Oct 19 '15 at 16:35

Turn the list into a set in order to remove duplicates and optimize membership tests.
Ensure the set is loaded only once into RAM
Use the array bisection algorithm if needing to work with a sorted list (i.e. you don't want to eliminate duplicates, need to make inserts, etc.).

If attempting to calculate the time complexity of both option, see this handy reference.

score 0 · Answer 3 · answered Oct 19 '15 at 16:36

You can turn the list into a set, which can take a lot of memory and computation times for creation (and which will remove duplicates).

Alternatively or you can use the module bisect to take advantage of the fact that your list is sorted. The first has search time of O(1) and the second of O(log(n)).

Optimising "if number in list" in python

3 Answers3