为什么 set() 构造函数比 list() 慢

Question

我计时set()和list()构造函数。set()明显慢于list(). 我使用不存在重复项的值对它们进行了基准测试。我知道 set use hashtables 是它变慢的原因吗？

在撰写本文时（3 月8^日），我正在使用 Python 3.7.5 [MSC v.1916 64 位 (AMD64)]、Windows 10。

#No significant changed observed.
timeit set(range(10))
517 ns ± 4.91 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
timeit list(range(10))
404 ns ± 4.71 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

当大小增加set()变得非常慢时list()

# When size is 100
timeit set(range(100))
2.13 µs ± 12.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
timeit list(range(100))
934 ns ± 10.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

# when size is ten thousand.
timeit set(range(10000))
325 µs ± 2.37 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
timeit list(range(10000))
240 µs ± 2.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# When size is one million.
timeit set(range(1000000))
86.9 ms ± 1.78 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
timeit list(range(1000000))
37.7 ms ± 396 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

他们都采取O(n)渐近。当没有重复项时，不应set(...)近似等于list(...)。

令我惊讶的是，集合理解和列表理解并没有像set()和list()显示的那样显示出那些巨大的偏差。

# When size is 100. 
timeit {i for i in range(100)}
3.96 µs ± 858 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
timeit [i for i in range(100)]
3.01 µs ± 265 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

# When size is ten thousand.
timeit {i for i in range(10000)}
434 µs ± 5.11 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
timeit [i for i in range(10000)]
395 µs ± 13.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# When size is one million.
timeit {i for i in range(1000000)}
95.1 ms ± 2.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
timeit [i for i in range(1000000)]
87.3 ms ± 760 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Answer 1

为什么它们应该相同？是的，它们都是 O(n)，但set()需要对每个元素进行散列，并且需要考虑元素不是唯一的。这意味着每个元素的固定成本更高。

Big O 没有说绝对时间，只是随着输入大小的增加花费的时间会如何增长。两种 O(n) 算法，在给定相同输入的情况下，完成所花费的时间可能大不相同。您只能说，当输入的大小加倍时，这两个函数所花费的时间（大致）会加倍。

如果您想更好地了解 Big O，我强烈推荐Ned Batchelder 对该主题的介绍。

当没有重复时不应该 set(...) 大约等于 list(...)。

不，它们不相等，因为list()不散列。没有重复是没有意义的。

令我惊讶的是，集合理解和列表理解并没有像set()和list()显示的那样显示出那些巨大的偏差。

由 Python 解释器循环执行的附加循环增加了支配所用时间的开销。较高的固定成本set()则不那么突出。

还有其他差异可能会产生影响：

• 给定一个已知长度的序列，list()可以预先分配足够的内存来容纳这些元素。集合不能预先分配，因为它们不知道会有多少重复。预分配避免了必须动态增长列表的（摊销）成本。
• 列表和集合推导式一次添加一个元素，因此列表对象无法预分配，稍微增加了固定的每项成本。