list.count() 与 Counter() 性能

Question

在尝试查找字符串中一堆字符的频率时，为什么对 4 个不同的字符运行 string.count(character) 4 次会比使用 collections.Counter(string) 产生更快的执行时间（使用 time.time()） ）？

背景：给定由字符串表示的一系列动作。有效移动为 R（右）、L（左）、U（上）和 D（下）。如果移动顺序带我回到原点，则返回 True。否则，返回 false。

# approach - 1 : iterate 4 times (3.9*10^-6 seconds)
def foo1(moves):
    return moves.count('U') == moves.count('D') and moves.count('L') == moves.count('R')

# approach - 2 iterate once (3.9*10^-5 seconds)
def foo2(moves): 
    from collections import Counter
    d = Counter(moves)
    return d['R'] == d['L'] and d['U'] == d['D']

import time
start = time.time()
moves = "LDRRLRUULRLRLRLRLRLRLRLRLRLRL"
foo1(moves)
# foo2(moves)
end = time.time()
print("--- %s seconds ---" % (end - start))

这些结果与我的预期相反。我的理由是，第一种方法应该需要更长的时间，因为字符串迭代了 4 次以上，而在第二种方法中，我们只迭代一次。可能是由于库调用开销造成的吗？

Answer 1

Counter理论上更快，但固定开销更高，特别是与 相比str.count，它可以通过直接内存比较扫描底层 C 数组，其中list.count必须对每个元素进行丰富的比较；转换moves为list单个字符的时间几乎是本地测试中时间的三倍foo1，从 448 ns 到 1.3 \xce\xbcs（实际上foo2稍微快一点，从 5.6 \xce\xbcs 下降到 5.48 \xce\xbcs）。

\n\n

其他问题：

\n\n

\n
1. 导入已经导入的模块使用缓存导入，但即使是缓存导入也会产生令人惊讶的开销（加载机器有很多东西需要检查以确保这样做是可以的）；在本地测试中，移动from collections import Counter到顶层将运行时间减少了foo21.6 \xce\xbcs（使用单个全局导入时为 5.6 \xce\xbcs，使用本地每次调用导入时为 7.2 \xce\xbcs）。这会因环境而有很大差异；在另一台机器上（用户和系统站点包中安装的东西较少），开销仅为 0.75 \xce\xbcs。无论如何，这对 来说是一个重大的、可以避免的劣势foo2。
\n
2. Counter现代Python使用C加速器来加速计数，但加速器仅在iterable足够长时提供好处。如果您使用list的形式moves，但将其乘以 100 以获得更长的序列，相对而言，差异会下降（对于 106 \xc2\xb5s 与foo1140 \xc2\xb5s foo2）
\n
3. 你只是没有计算很多东西；当您只关心四件事时，如果前一种情况的常数乘数（不包括在大 O 表示法中）低于后者，则支付O(n)四次可以轻松击败支付一次。O(n)对于任意数量的被计算的独特事物来说Counter仍然存在；O(n)调用.count是O(n)每次调用，但是如果您需要知道输入中每个唯一事物的计数，对于大多数唯一的输入，.count每个调用的单独调用将是渐近的O(n\xc2\xb2)。
\n
4. 在您的具体情况下，该.count方法是短路的，因此它甚至没有O(n)工作四次，只是两次；theU和D计数不匹配，因此它根本不会L计数。如果它不能短路（所有成本都在单次计数过程中支付），则不会明显变慢，但是在我从第#2点（更长的输入，形式）使用的同一基准中，您的106 \xc2\xb5s 到 185 \xc2\xb5s 如果我只是在（预乘法）的末尾添加一个（使和计数相同，并且需要另外两次调用）；只增加到 143 \xc2\xb5s（从 140 \xc2\xb5s），大概是因为实际上变得更长（加上之前乘以 100 意味着它从 2900 个元素增加到 3000 个）。RCounterfoo1listDmovesUDcountfoo2movesD
\n

\n\n

基本上，您有一些小的实施弱点，但大多数情况下，您碰巧选择了一个用例，该用例可以为 提供所有优势.count，而没有为 提供任何优势Counter。如果您的输入始终为str，并且您只count对它们执行少量固定次数，那么当然，重复调用count通常会获胜。但对于任意输入类型（尤其是迭代器，这count是不可能的，因为它不存在，而且只能迭代一次），特别是较大的输入类型，有更多独特的东西要计数，其中一致的性能很重要（因此依赖于短路以减少调用次数count是不可接受的），Counter将会获胜。

\n