19

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

if item in list:
  print item

使用什么算法搜索此项目。它是从头到尾直接搜索列表还是使用二进制搜索之类的东西？

4

2 回答 2

21

lists 不能被假定为按排序顺序（或任何顺序），因此二进制搜索不起作用。也不能假定键是可散列的，因此与 adict或set散列表查找不同，不能用于加速搜索

猜测是从头到尾对每个元素进行直接检查。

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

--

编辑：list.__contains__()实现in运算符的 Python 函数在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 }

它遍历列表中的每个元素，从第一个元素到最后一个元素（或直到找到匹配项）。这里没有捷径。

--

编辑2：情节变厚了。如果 Python 检测到您正在测试常量 listor中某个元素的成员资格set，例如：

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

编辑 3 [@JohnMachin]：

常量列表在 2.5-2.7 和 3.1-3.3 中优化为常量元组。
常量集在 3.3 中优化为（常量）frozenset。

另请参阅@CoryCarson 的回答。

于 2012-05-06T05:56:52.973 回答
6

如果list是文字列表，Python 3.2+ 将采用更快的方法：http ://docs.python.org/dev/whatsnew/3.2.html#optimizations

于 2012-05-06T06:12:59.470 回答