哪个更快，为什么？设置还是列表？

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

但是，由于此处已经提到的原因，当您“搜索”大型集合时，您可以从使用集合中受益。通过你的例子不可能告诉你拐点在哪里以及你是否会看到好处。 我建议您对这两种方法进行测试，并选择适合您的特定用例的更快的方法。

Answer 3

Answer 4

{}

而不是

set([])

初始化集合，在 python 3 中没有显着差异。

import timeit

def use_sets(a, b):
    return [{b}, {a, b}]

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

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

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

六组中有一次甚至更快：

use_lists() 0.07633562502451241
use_sets() 0.0888096671551466

use_lists() 0.0833125829230994
use_sets() 0.08494833391159773

use_lists() 0.08396612480282784
use_sets() 0.08459279080852866

use_lists() 0.0729287089779973
use_sets() 0.08553649997338653

use_lists() 0.08407187508419156
use_sets() 0.08565612509846687

use_lists() 0.08485491713508964
use_sets() 0.08444362506270409