list.count() 对比 Counter() 性能

Question

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

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


# 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 μs（而 foo2 实际上会快一点，从 5.6 μs 下降到 5.48 μs）。

其他问题：

导入一个已经导入的模块使用缓存导入，但是即使是缓存导入也有惊人的开销（加载机制有很多东西要检查确保可以这样做）；在本地测试中，将 from collections import Counter 移动到顶层将 foo2 的运行时间减少了 1.6 微秒（单个全局导入为 5.6 微秒，本地 per-call 导入为 7.2 微秒）。这将因环境而异 lot；在另一台机器上（用户和系统都安装了更少的东西 site-packages），开销仅为 0.75 μs。无论如何，这对 foo2.
Counter 现代 Python 使用 C 加速器来加速计数，但 加速器仅在迭代足够长时提供好处 。如果您使用 moves 的 list 形式，但将其乘以 100 以生成更长的序列，则差异会下降，相对而言（foo1 为 106 µs，[=140 µs foo2)
你只是没有数到很多东西；当你只关心四件事时，支付 O(n) 四次可以轻松击败支付 O(n) 一次，如果前一种情况具有较低的常量乘数 （这是' t 包含在 big-O 符号中）比后者。 Counter 仍然是 O(n) 以计算任意数量的独特事物；调用 .count 是每次调用 O(n)，但是如果您需要知道输入中每个唯一事物的计数，对于大多数唯一的输入，每个 .count 调用将渐近O(n²).
.count 方法在您的特定情况下是 short-circuiting，所以 它甚至没有做 O(n) 四次工作，只有两次 ; U 和 D 计数不匹配，因此根本不会计算 L 和 R。 Counter 如果不能 short-circuit 也不会明显变慢（所有成本都在单次计算中支付），但是你的 foo1，在我从点开始使用的相同基准中#2（较长的输入，list 形式），如果我只是在 (pre-multiplication) moves 的末尾添加一个 D，则从 106 µs 到 185 µs （使 U 和 D 计数相同，并且需要另外两次 count 调用）； foo2 仅上升到 143 µs（从 140 µs），大概是因为 moves 实际上变长了（在乘以 100 之前添加 D 意味着它从 2900 个元素计数到 3000） .

基本上，您有一些小的实施弱点，但大多数情况下，您碰巧选择了一个用例，该用例为 .count、none 和 Counter 提供了所有优势。如果您的输入始终是 str，并且您只是 count 对它们进行少量固定次数的输入，那么可以肯定的是，重复调用 count 通常会成功。但是对于任意输入类型（尤其是迭代器，其中 count 是不可能的，既因为它不存在，也因为你只能迭代它一次），尤其是更大的类型，有更多独特的东西要计算，性能一致计数（因此依靠 short-circuiting 来减少 count 调用的次数是不可接受的），Counter 将获胜。

list.count() 对比 Counter() 性能

list.count() vs Counter() performance

counter

performancecounter

count

performance-testing

python-3.x