时间戳

首页 > 解决方案 > 为什么 set() 构造函数比 list() 慢

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

问题描述

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

在撰写本文时（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)

标签： pythonlistperformanceset

解决方案

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

Big O 没有说明绝对时间，只说明所用时间将如何随着输入大小的增长而增长。两个 O(n) 算法，给定相同的输入，可能需要完全不同的时间来完成。您只能说，当输入的大小加倍时，这两个函数所花费的时间（大约）会加倍。

如果你想更好地理解 Big O，我强烈推荐Ned Batchelder 对这个主题的介绍。

当没有重复项时，不应设置（...）大约等于列表（...）。

不，它们不相等，因为list()不散列。没有重复并不意味着。

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

由 Python 解释器循环执行的附加循环增加了占主导地位的开销。较高的固定成本set()则不那么突出。

还有其他差异可能会有所不同：

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

推荐阅读