是什么使集合比列表更快? [英] What makes sets faster than lists?

问题描述

python Wiki说:用集合和字典进行成员资格测试比搜索序列O(n)更快，O(1).当测试"a in b"时，b应该是集合或字典，而不是列表或元组."

The python wiki says: "Membership testing with sets and dictionaries is much faster, O(1), than searching sequences, O(n). When testing "a in b", b should be a set or dictionary instead of a list or tuple."

每当速度在我的代码中很重要时，我就一直使用集代替列表，但是最近我一直在想为什么集比列表快得多.任何人都可以解释一下，或者让我指向可以解释这一点的消息源，这是为了在python中更快地进行设置而在幕后究竟发生了什么?

I've been using sets in place of lists whenever speed is important in my code, but lately I've been wondering why sets are so much faster than lists. Could anyone explain, or point me to a source that would explain, what exactly is going on behind the scenes in python to make sets faster?

推荐答案

集合是使用哈希表实现的.每当将对象添加到集合中时，set对象在内存中的位置都是使用要添加的对象的哈希值确定的.在测试成员资格时，基本上需要做的只是看对象是否在其哈希确定的位置上，因此此操作的速度不取决于集合的大小.相比之下，对于列表，则需要搜索整个列表，随着列表的增长，列表的搜索速度会变慢.

Sets are implemented using hash tables. Whenever you add an object to a set, the position within the memory of the set object is determined using the hash of the object to be added. When testing for membership, all that needs to be done is basically to look if the object is at the position determined by its hash, so the speed of this operation does not depend on the size of the set. For lists, in contrast, the whole list needs to be searched, which will become slower as the list grows.

这也是设置不保留添加对象顺序的原因.

This is also the reason that sets do not preserve the order of the objects you add.

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

Note that sets aren't faster than lists in general -- membership test is faster for sets, and so is removing an element. As long as you don't need these operations, lists are often faster.

这篇关于是什么使集合比列表更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！