Does Python's `in` keyword perform a linear search? [duplicate]

Question

How does Python checks if a given value exists in an iterable using in keyword. Does it perform a linear search? Like :

def naive(iterable, val):
    for i in range(len(l)):
        if iterable[i]==val:
            return True
    return False

? Or it has got a different way of doing that. Other than linear search?

Answer 1

Python's in operator calls the __contains__ magic function on the container. That is implemented in different ways for different containers.

For strings, lists and tuples, it's a linear search (O(N)), though since it's implemented in C it will probably be faster than the pure-python one you have in your question.

For a sets and dicts, it's a hash-table lookup, which is much faster (O(1) average case).

Other containers will have different performance characteristics. I don't think there are any in the standard library, but a balanced tree data structure would probably be O(log N).

Answer 2

The in keyword depends on the implementation of the __contains__ method in the object's class you are calling. That means for anything that isn't hashable (list, string) it performs a linear search but for a hashable data structures (dict, set) it would be amortized constant time.