Python: How does "IN" (for lists) works?

I have this code

list = ['a','b','c']

if 'b' in list:
   return "found it"
return "not found"

Now, how does this work? Does it traverse the whole list comparing the element? D开发者_Python百科oes it use some kind of hash function?

Also, is it the same for this code?

list.index('b')

in uses the method __contains__. Each container type implements it differently. For a list, it uses linear search. For a dict, it uses a hash lookup.

Python Wiki states that val in list has O(n) average time complexity. This implies linear search. I expect list.index(val) to be the same.

After all, list is, well, a list. If you want hash tables, consider using set or dict.

The comparison is evaluated once for every item in the list.

See http://effbot.org/zone/python-list.htm for more information on Python lists (and list comprehensions as you have posted).

Both in and list.index() loop over all elements and have therefore a linear runtime. In addition to the intuitive logic (it has to be this way since a list is just a dynamic array), you can verify that by looking at the C implementation of list_contains (in) and listindex.

For example, the __contains__ routine is implemented as simple as:

static int
list_contains(PyListObject *a, PyObject *el)
{
    Py_ssize_t i;
    int cmp;

    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
        cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
                                           Py_EQ);
    return cmp;
}

Here is the disassembly:

>>> from dis import dis
>>> def foo():
...     a = ['a', 'b', 'c']
...     if 'b' in a:
...             print "Found it!"
... 
>>> dis(foo)
  2           0 LOAD_CONST               1 ('a')
              3 LOAD_CONST               2 ('b')
              6 LOAD_CONST               3 ('c')
              9 BUILD_LIST               3
             12 STORE_FAST               0 (a)

  3          15 LOAD_CONST               2 ('b')
             18 LOAD_FAST                0 (a)
             21 COMPARE_OP               6 (in)
             24 POP_JUMP_IF_FALSE       35

  4          27 LOAD_CONST               4 ('Found it!')
             30 PRINT_ITEM          
             31 PRINT_NEWLINE       
             32 JUMP_FORWARD             0 (to 35)
        >>   35 LOAD_CONST               0 (None)
             38 RETURN_VALUE  

The in-operator calls __contains__ in the COMPARE_OP instruction. You can see it in action here:

class X(object):
    def __init__(self, elements):
        self.elements = elements
    def __contains__(self, element):
        print "Called __contains__"
        return element in self.elements

x = X(['a', 'b', 'c'])
if 'b' in x:
    print "Found it!"

You get this output:

...
>>> x = X(['a', 'b', 'c'])
>>> if 'b' in x:
...     print "Found it!"
... 
Called __contains__
Found it!