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 ?
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.
1000001 in range(10**6) will only take nano seconds to finish.