list.count() 与 Counter() 性能

在尝试查找字符串中一堆字符的频率时，为什么对 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 次以上，而在第二种方法中，我们只迭代一次。可能是由于库调用开销造成的吗？

Counter理论上更快，但固定开销更高，特别是与str.count，它可以通过直接内存比较来扫描底层 C 数组, where list.count必须对每个元素进行丰富的比较；转换moves to a list单个字符的时间几乎增加了三倍foo1在本地测试中，从 448 ns 到 1.3 μs（同时foo2实际上变得更快了一点，从 5.6 μs 下降到 5.48 μs）。

其他问题：

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

基本上，您有一些小的实施弱点，但大多数情况下，您碰巧选择了一个可以发挥所有优势的用例.count, 没有一个Counter。如果你的输入总是str，而你只是count进行少量固定次数的调用，然后当然，重复调用count一般都会赢。但对于任意输入类型（尤其是迭代器，其中count是不可能的，既因为它不存在，又因为你只能迭代它一次），尤其是较大的，有更多独特的东西要计算，其中一致的性能很重要（因此依靠短路来减少count不接受电话），Counter会赢。