什么使集合比列表更快？

Question

python wiki说:"使用集合和字典进行成员资格测试比搜索序列O(n)要快得多.当测试"a in b"时,b应该是一个集合或字典而不是列表或元组".

每当速度在我的代码中很重要时,我一直在使用集合代替列表,但最近我一直在想为什么集合比列表快得多.任何人都可以解释,或指向一个可以解释的消息来源,在python中幕后发生了什么,以便更快地制作集合？

Answer 1

list:想象一下,你在衣柜里寻找你的袜子,但你不知道你的袜子在哪个抽屉里,所以你必须逐个抽屉搜索,直到你找到它们(或者你可能永远不会).这就是我们所说的O(n),因为在最糟糕的情况下,你会看到所有抽屉(抽屉n的数量).

set:现在,想象一下你还在衣柜里寻找你的袜子,但是现在你知道袜子在哪个抽屉里,比如说在第3个抽屉里.因此,您只需在第三个抽屉中搜索,而不是在所有抽屉中搜索.这就是我们所说的O(1),因为在最糟糕的情况下,你只会看到一个抽屉.

Answer 2

使用哈希表实现集合.无论何时向对象添加对象,都会使用要添加的对象set的哈希来确定对象内存中的位置.在测试成员资格时,所有需要完成的工作基本上是查看对象是否位于由其哈希确定的位置,因此此操作的速度不依赖于集合的大小.相反,对于列表,需要搜索整个列表,随着列表的增长,列表将变慢.

这也是集合不保留您添加的对象顺序的原因.

请注意,集合通常不比列表快 - 对于集合,成员资格测试更快,因此删除元素也是如此.只要您不需要这些操作,列表通常会更快.

Answer 3

我认为你需要好好看一本关于数据结构的书.基本上,Python列表实现为动态数组,而集合实现为哈希表.

这些数据结构的实现赋予它们完全不同的特征.例如,哈希表的查找时间非常快,但无法保留插入顺序.

Answer 4

虽然到目前为止我还没有测量过 python 中的任何相关性能，但我仍然想指出列表通常更快。

是的，您的时间复杂度为 O(1) 与 O(n)。但请永远记住，这仅提供有关某物渐近行为的信息。这意味着如果你的 n 非常高，O(1) 理论上总是会更快。然而在实践中，n 通常需要比通常的数据集大得多。

因此，集合本身并不比列表快，但前提是您必须处理大量元素。