哪个更快,为什么？设置还是列出？

Question

让我们说我有一个图表,想看看是否b in N[a].哪个更快实现,为什么？

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

要么

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

这显然过于简单,但想象图表变得非常密集.

Answer 1

集合中的成员资格测试速度要快得多,特别是对于大型集合.这是因为该集使用散列函数映射到存储桶.由于Python实现自动调整该哈希表O(1)的大小,因此无论集合的大小如何(假设哈希函数足够好),速度都可以是常量().

相反,为了评估对象是否是列表的成员,Python必须比较每个成员的相等性,即测试是O(n).

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

但是,由于此处已提及的原因,在搜索大型集时,您将从使用集中受益.你的例子不可能告诉你哪个拐点适合你,以及你是否会看到这个好处.

我建议你两种方式进行测试,然后根据具体用例选择更快的方式.