哪个更快，为什么？Set 还是 List？

Question

假设我有一个图，并想要查看b是否在N[a]中。哪种实现方式更快，为什么？

a, b = range(2)
N = [set([b]), set([a,b])]

或者

N= [[b],[a,b]]

这显然是过于简化了，但想象一下图表变得非常密集。

- locoboy

Answer 1

对于大型集合，使用集合的成员测试速度更快得多。这是因为该集合使用哈希函数来映射到一个桶(bucket)。由于Python实现会自动调整哈希表的大小，所以速度可以保持恒定(O(1))，不管集合大小如何（假设哈希函数足够好）。

相比之下，为了确定一个对象是否为列表的成员，Python必须比较每个成员的相等性，即测试时间为O(n)。

- phihag

---

抢我一步了。另外值得指出的是，原帖中第一个示例是列表的列表，而第二个示例是集合的列表。由于两种情况下的外部容器都是列表，因此在两种情况下搜索的时间复杂度均为O(n)。 - g.d.d.c

Python的集合是动态调整大小的哈希表，因此您可以获得摊销O(1)，无论项目数量如何。@g.d.d.c OP询问列表N中单个项目b的成员资格测试(b in N[a])，因此无论如何都不是O(n)。 - user395760

@delnan 你是对的，O(1)（+注释）比O(log n)（-注释）更好的描述。 - phihag

@phihag O(1) 不仅比 O(log n) 更好：O(1) 是正确的，而 O(log n) 不是。 - Ned Batchelder

@NedBatchelder：实际上，如果你查阅数学定义，你会发现只要O(1)是常数，那么O(log N)就是正确的——如果它是常数，那么它也受log N的限制。因此，O(1) 确实比O(log N)更好。 - Petr Viktorin

Answer 2

这完全取决于你想要实现什么。以你的示例为例，使用列表更快，因为你不需要创建集合所需的额外开销：

import timeit

def use_sets(a, b):
    return [set([b]), set([a, b])]

def use_lists(a, b):
    return [[b], [a, b]]

t=timeit.Timer("use_sets(a, b)", """from __main__ import use_sets
a, b = range(2)""")
print "use_sets()", t.timeit(number=1000000)

t=timeit.Timer("use_lists(a, b)", """from __main__ import use_lists
a, b = range(2)""")
print "use_lists()", t.timeit(number=1000000)

生成：

use_sets() 1.57522511482
use_lists() 0.783344984055

然而，正如此前提到的那样，当你在搜索大数据集时，使用集合会带来好处。根据你的示例无法确定你的转折点在哪里以及你是否会获益。

我建议你两种方式都测试并选择对于你特定用例更快的方法。

- Austin Marshall

Answer 3

集合（指使用哈希实现的集合，例如HashSet）比列表更快地查找值。列表必须按顺序查找以确定值是否存在。HashSet可以直接跳转并定位桶，在几乎恒定的时间内查找值。

- java_mouse