CODEWITHSUNDEEP
pythonlist
Pranav Raj
Pranav Raj

Reputation: 873

search algorithm in python's list

How efficient is checking whether a element is present in the list or not?

Suppose I have a list L = [1,2,3,4,5] and I execute the following command:

5 in L
>>> True
12 in L
>>> False

How much time either of this will take. To be precise, what kind of search algorithm does python's list employ ?

Upvotes: 0

Views: 88

Answers (1)

unutbu
unutbu

Reputation: 879321

Checking membership in a list is a O(n) operation. Each item in the list will be checked in order for equality. If an item is found to be equal, True is returned. Thus the time it takes to check membership depends on the length of the list, and the position of the item in the list (if it is there at all):

In [1]: L = list(range(10**6))

In [2]: %timeit 0 in L
10000000 loops, best of 3: 43.2 ns per loop

In [3]: %timeit 999999 in L
100 loops, best of 3: 16.1 ms per loop

In [4]: %timeit 1000001 in L
100 loops, best of 3: 16.1 ms per loop

In contrast, checking membership in a set or dict is a O(1) operation.

In [103]: s = set(xrange(10**6))

In [104]: %timeit 0 in s
10000000 loops, best of 3: 48 ns per loop

In [105]: %timeit 999999 in s
10000000 loops, best of 3: 65.3 ns per loop

In [106]: %timeit 1000001 in s
10000000 loops, best of 3: 45.7 ns per loop

Here is a wiki page summarizing the complexity of operations on Python builtin types.

Upvotes: 4

Related Questions