是什么让集合比列表更快? [英] 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屋！