Python 究竟是如何检查列表的？

Question

我正在为 python 在 codeacademy 上做一门课程练习，我有几个问题似乎找不到答案：

对于这个代码块，python 究竟是如何检查某个东西是 "in" 还是 "not in" 列表的？它运行是检查列表中的每个项目还是使用更快的过程？

此外，如果此代码是运行大量数字列表（数千或数百万），将如何受到影响？它会随着列表大小的增加而变慢吗？还有更好的选择吗？

numbers = [1, 1, 2, 3, 5, 8, 13]

def remove_duplicates(list):
  new_list = []
  for i in list: 
    if i not in new_list:
      new_list.append(i)
  return new_list

remove_duplicates(numbers)

谢谢！

P.S。为什么这段代码的功能不同？

numbers = [1, 1, 2, 3, 5, 8, 13]

def remove_duplicates(list):
  new_list = []
  new_list.append(i for i in list if i not in new_list)
  return new_list

Answer 1

为了执行i not in new_list Python 必须对列表进行线性扫描。一旦测试结果已知，扫描循环就会中断，但如果 i 实际上不在列表中，则必须扫描整个列表以确定它。它以 C 速度执行此操作，因此它比执行 Python 循环来显式检查每个项目更快。偶尔做 in some_list 测试是可以的，但是如果你需要做很多这样的成员测试，最好使用 set.

平均而言，对于随机数据，测试成员资格必须扫描一半的列表项，并且通常执行扫描所花费的时间与列表的长度成正比。在通常的表示法中，列表的大小用n表示，这个任务的时间复杂度写为O(n)。

相比之下，确定set（或dict）的成员资格可以（平均）在恒定时间内完成，因此其时间复杂度为O(1)。请参阅 Python Wiki 中的 TimeComplexity 了解有关此主题的更多详细信息。谢谢 Serge link.

当然，如果您使用 set，那么您可以免费获得重复数据删除，因为不可能将重复项添加到集合中。

集合的一个问题是它们通常不保持顺序。但是您可以使用集合作为辅助集合来加速重复数据删除。这是对列表或其他有序集合进行重复数据删除的一种常用技术的说明，它确实保留了顺序。我将使用字符串作为数据源，因为我懒得输入列表。 ;)

new_list = []
seen = set()
for c in "this is a test":
    if c not in seen:
        new_list.append(c)
        seen.add(c)
print(new_list)

输出

['t', 'h', 'i', 's', ' ', 'a', 'e']

请参阅 How do you remove duplicates from a list whilst preserving order? 了解更多示例。感谢 Jean-François Fabre 的 link.

至于您的 PS，该代码将单个生成器对象附加到 new_list，它不会附加生成器将产生的内容。

我假设您已经尝试过使用列表理解来做到这一点：

new_list = [i for i in list if i not in new_list]

那是行不通的，因为 new_list 在列表 comp 完成运行之前不存在，所以 in new_list 会引发 NameError。即使你在 list comp 之前做了 new_list = []，它也不会被 list comp 修改，list comp 的结果只会用一个新的对象替换那个空的 list 对象。

顺便说一句，请不要使用 list 作为变量名（即使在示例代码中也是如此），因为这会掩盖内置的 list 类型，这会导致神秘的错误消息。

Answer 2

你问的是这个函数的算法复杂度。要找到你需要看到每一步发生了什么。

您一次扫描一个列表，这需要 1 个工作单位。这是因为从列表中检索内容是 O(1)。如果您知道索引，则可以在 1 个操作中检索它。

您要添加的列表在最坏的情况下一次增加 1 个。因此，在任何时间点，unique 项目列表的大小都将是 n。

现在，要将您选择的项目添加到 unique 项目列表中，在最坏的情况下需要 n 个工作。因为我们必须扫描每个项目才能决定。

所以如果你总结每个步骤的总工作量，那就是 1 + 2 + 3 + 4 + 5 + ... n 即 n (n + 1) / 2。所以如果你有一百万个项目，你可以通过在公式中应用 n = million 来找到它。

由于 list 的工作原理，这并不完全正确。但从理论上讲，以这种方式可视化会有所帮助。

Answer 3

回答标题中的问题：python有更高效的数据类型但是list() object只是一个普通数组，如果你想要一个更有效的搜索方式您可以使用 dict() 的值，它使用存储的 object 的散列将其插入到树中，我假设这就是您提到 "a quicker process".

时的想法

关于第二个代码片段： list().append() 将你给它的任何值插入到列表的末尾，i for i in list if i not in new_list 是一个生成器 object 并将该生成器作为 object 插入到数组中，list().extend() 做你想做的事：它接收一个可迭代对象并将其所有元素附加到列表中

Answer 4

您提出了多个问题，其中一个问题询问您是否可以更有效地做到这一点。我会回答的。

好吧，假设您有数千或数百万个数字。具体从哪里来？假设它们存储在某种 txt 文件中，那么您可能想要使用 numpy（如果您坚持使用 Python 的话）。示例：

import numpy as np

numbers = np.array([1, 1, 2, 3, 5, 8, 13], dtype=np.int32)
numbers = np.unique(numbers).tolist()

这将比使用 python 读取它并执行列表（set..）

更有效（最重要的是与内存效率相比）

numbers = [1, 1, 2, 3, 5, 8, 13]
numbers = list(set(numbers))

Python 究竟是如何检查列表的？

How exactly does Python check through a list?

python

list

python-3.x

notin