哪个更快，为什么？集合还是列表？

Question

假设我有一个图（可以理解为一个由点和线组成的结构），我想检查一下某个点b是否在点的邻居中，也就是看b是否和直接相连。那下面这两种方法，哪种更快呢？为什么呢？

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

或者

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

这显然是个简单化的例子，但想象一下，如果这个图变得非常复杂，连接的点很多，那情况就会不一样了。

Answer 1

集合（我指的是像 HashSet 这样的基于哈希的集合）在查找一个值时比列表要快得多。列表需要一个一个地顺序查找，才能确定这个值是否存在。而 HashSet 可以直接跳到特定的位置，几乎可以在固定的时间内找到这个值。

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

不过，正如之前提到的，当你在处理大数据集时，使用集合会有好处，特别是在进行搜索的时候。根据你的例子，很难判断你在哪个点上会发现这种好处。

我建议你两种方法都试一下，看看哪种在你的具体情况下更快。

Answer 3

在一个集合中检查某个元素是否存在，速度非常快，尤其是当集合很大的时候。这是因为集合使用了一种叫做哈希函数的东西，把元素映射到一个桶里。由于Python的实现会自动调整这个哈希表的大小，所以无论集合有多大，速度都可以保持在一个固定的水平（O(1)），前提是哈希函数的效果足够好。

而相比之下，如果要判断一个元素是否在列表中，Python就得一个一个地比较每个元素，看它们是否相等，也就是说这个过程的复杂度是O(n)。