Geek Answers Handbook

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

I have this code

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

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

Now how does it work? Does it go through the whole list comparing an item? Does it use any hash function?

Also, is it the same for this code?

list.index('b')
+5
source share
5 answers

inuses a method __contains__. Each type of container implements it differently. A linear search is used for the list. For dict, it uses hash search.

+16
source

The Python Wiki indicates that it val in listhas medium time complexity O(n). This implies a linear search. I expect it to list.index(val)be the same.

, list - , , . -, set dict.

+7

in list.index() . ( , - ), , , C- list_contains (in) listindex.

, __contains__ , :

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;
}
+1

:

>>> 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

__contains__ COMPARE_OP. :

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!"

:

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

More articles:


All Articles