在python中使用in运算符搜索列表时使用什么算法?

本文介绍了在python中使用in运算符搜索列表时使用什么算法?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

使用"in"运算符搜索列表中的项目时，例如

When using the 'in' operator to search for an item in a list e.g.

if item in list:
  print item

使用什么算法搜索该项目.是从头到尾直接搜索列表还是使用二进制搜索之类的方法?

What algorithm is used to search for this item. Is it a straight search of the list from beginning to end or does it use something like binary search?

推荐答案

list不能被假定为排序顺序(或根本没有任何顺序)，因此二进制搜索将不起作用.密钥也不能被假定为可散列的，因此与dict或set不同的是，哈希表查找不能用于加速搜索

lists can't be assumed to be in sorted order (or any order at all), so binary search won't work. Nor can the keys be assumed to be hashable, so unlike a dict or set a hash-table lookup can't be used to accelerate the search

猜测是从头到尾对每个元素的直接检查.

At a guess it's a straight-through check of every element from first to last.

我将尝试挖掘相关的Python源代码.

I'll try and dig up the relevant Python source code.

在in运算符的Python list.__contains__()函数. rel ="noreferrer"> listobject.c :

The Python list.__contains__() function, which implements the in operator, is defined in listobject.c:

   393 static int
   394 list_contains(PyListObject *a, PyObject *el)
   395 {
   396     Py_ssize_t i;
   397     int cmp;
   398 
   399     for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
   400         cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
   401                                            Py_EQ);
   402     return cmp;
   403 }

迭代列表中的每个元素，从第一个元素到最后一个元素(或直到找到匹配项.)这里没有捷径.

It iterates over every element in the list, from the first element to the last element (or until it finds a match.) No shortcuts here.

情节变厚.如果Python检测到您正在测试常量 list或set中元素的成员资格，例如:

Edit 2: The plot thickens. If Python detects that you're testing for membership of an element in a constant list or set, like:

if letter in ['a','e','i','o','u']:    # list version
if letter in {'a','e','i','o','u'}:    # set version

编辑3 [@JohnMachin]:

Edit 3 [@JohnMachin]:

常量列表已在2.5-2.7和3.1-3.3中优化为常量元组.
常量集在3.3中被优化为一个(常量)冻结集.

The constant list is optimised to a constant tuple in 2.5-2.7 and 3.1-3.3.
The constant set is optimised to a (constant) frozenset in 3.3.

另请参阅@CoryCarson的答案.