python - 为什么多个 list.count 调用比单个循环更快？

Question

我有一个像这样生成的 2 元素 tuple 的 list:

import random

l = list(range(8)) * 7
random.shuffle(l)
l = list(zip(*[iter(l)] * 2))

l 的输出:

[(1, 3),
 (6, 6),
 (1, 0),
 (4, 6),
 (1, 5),
 (7, 5),
 (4, 0),
 (5, 4),
 (4, 7),
 (4, 4),
 (0, 6),
 (2, 0),
 (3, 2),
 (7, 7),
 (6, 0),
 (2, 5),
 (1, 5),
 (0, 1),
 (0, 4),
 (5, 3),
 (7, 2),
 (3, 3),
 (6, 3),
 (2, 6),
 (7, 7),
 (5, 2),
 (3, 1),
 (2, 1)]

我正在计算元组 e 及其反向出现的次数:

e = (1, 5)

首先，我正在使用 list.count，它应该有一个 O(2n)，因为该方法被调用了两次，因此列表被遍历了两次:

%timeit l.count(e) + l.count(e[::-1])
# 1.46 µs ± 11.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

然后我使用一个传统的 for 循环，它只用 O(n) 遍历列表一次:

%%timeit
c = 0
for t in l:
    if t in (e, e[::-1]):
        c += 1
# 5.57 µs ± 35.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

为什么第一个比第二个快 ~1.5-4，即使它遍历整个列表两次？

Answer 1

非常简单的答案是 count 是用纯 C 实现的，因此运行速度比 Python 循环快。然而，有很多微妙之处需要考虑。

首先，您没有以最有效的方式编写循环。每次执行表达式 t in (e, e[::-1]) 时，都会发生三件事:

1. e 元组与 e[::-1] 反转。请注意，这只需要发生一次——您可以存储结果并重新使用它。但是现在，它在循环中每次都会执行。

2. 这两个元组存储在一个外部元组中。这也只需要发生一次，但同样，每次循环都会执行。

3. 最后，检查外部元组中的每个项目是否与 t 相等。这确实必须在每次循环中发生，因为 t 的值每次都会改变。

这是我电脑上的速度测试结果:

In [6]: %%timeit
   ...: c = 0
   ...: for t in l:
   ...:     if t in (e, e[::-1]):
   ...:         c += 1
   ...: 
7.39 µs ± 43.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

为了简化这一点，您可以只创建一次外部元组。称它为 e_test:

e_test = (e, e[::-1])

然后事情就快多了:

In [8]: %%timeit
    ...: c = 0
    ...: for t in l:
    ...:     if t in e_test:
    ...:         c += 1
    ...: 
3.05 µs ± 62.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

我认为这可能是使用普通 Python for 循环实现此测试的最快方法。但是，基于count 的解决方案仍然更快!

In [9]: %timeit l.count(e) + l.count(e[::-1])
2.19 µs ± 62 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

我们可以通过再次预先计算反向元组来进一步改进:

In [10]: e_rev = e[::-1]

In [11]: %timeit l.count(e) + l.count(e_rev)
2.06 µs ± 62.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

在同一个循环中执行两个测试当然是有好处的。但与其他因素相比，好处实际上非常小。在这种情况下它甚至更小，因为 count 循环发生在 C 中，这极大地减少了额外 for 循环的成本。

在实践中，如果您要决定是在一个循环中执行多个操作还是执行多个循环，您应该选择最容易阅读和维护的内容，因为 99% 的时间，多个循环的开销将被大大超过通过在循环内部执行的操作的成本。

作为最后的说明，这里是我能找到的基于 count 的方法的最佳替代方法。它们都创建一个 set 而不是一个元组，这意味着 in 表达式在恒定时间内工作。我原以为在这里使用集合不会比使用元组更好，因为只有两个项目要测试。但事实证明性能确实更好，至少在我的机器上是这样:

In [32]: e_test_set = set(e_test)

In [33]: %timeit sum([1 for t in l if t in e_test_set])
2.34 µs ± 90.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

请注意，这使用了显式列表推导式，而不是将生成器表达式传递给 sum。如果你传递一个生成器表达式，它会慢大约十分之一微秒。这仍然比基于 count 的方法慢!

但是一旦您创建了一个列表，就会发现您根本不需要计算总和。一个列表的总和就是它的长度。

In [34]: %timeit len([1 for t in l if t in e_test_set])
2.07 µs ± 73.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

现在，我们终于有了一个可以与基于 count 的方法竞争的版本，至少在这个规模上是这样。对于更大的列表，我预计这会再次变慢，因为为列表分配内存会花费太多时间。