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

Question

我对 set() 和 list() 构造函数进行了计时。 set() 明显慢于 list()。我使用不存在重复项的值对它们进行基准测试。我知道设置使用哈希表是它速度较慢的原因吗？

截至撰写本文时，我正在使用 Python 3.7.5 [MSC v.1916 64 位 (AMD64)]、Windows 10(第 8 期) 三月)。

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

当大小增加时，set() 变得比 list() 慢得多

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

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

# When size is one million.
timeit set(range(<b>1000000</b>))
<b>86.9 ms</b> ± 1.78 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
timeit list(range(<b>1000000</b>))
<b>37.7 ms</b> ± 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(<b>100</b>)}
<b>3.96 µs</b> ± 858 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
timeit [i for i in range(<b>100</b>)]
<b>3.01 µs</b> ± 265 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

# When size is ten thousand.
timeit {i for i in range(<b>10000</b>)}
<b>434 µs</b> ± 5.11 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
timeit [i for i in range(<b>10000</b>)]
<b>395 µs</b> ± 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(<b>1000000</b>)}
<b>95.1 ms</b> ± 2.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
timeit [i for i in range(<b>1000000</b>)]
<b>87.3 ms</b> ± 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’s introduction to the subject .

When there are no duplicates shouldn't set(...) approximately equal be to list(...).

不，它们不相等，因为 list() 不进行哈希处理。没有重复项并不说明。

To my suprise set comprehension and list comprehension didn't show those huge deviations like set() and list() showed.

Python 解释器循环执行的附加循环会增加开销，从而影响所用时间。 set() 较高的固定成本就不那么突出了。

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

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