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

Question

我有一个由 2 元素元组组成的列表，如下所示:

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 的方法竞争的版本，至少在这个规模上是这样。对于更大的列表，我预计这会再次变慢，因为为列表分配内存会花费太多时间。