为什么二分搜索优化要慢得多？

Question

假设的优化使代码速度慢了一倍以上。

\n

我通过查找某个值出现的范围来计算该值x在排序列表中出现的频率：a

\n

from bisect import bisect_left, bisect_right\n\ndef count(a, x):\n    start = bisect_left(a, x)\n    stop = bisect_right(a, x)\n    return stop - start\n

\n

但是，嘿，它不能在开始之前停止，因此我们可以通过省略开始之前的部分（doc）来优化第二次搜索：

\n

def count(a, x):\n    start = bisect_left(a, x)\n    stop = bisect_right(a, x, start)\n    return stop - start\n

\n

但当我进行基准测试时，优化版本花费的时间是原来的两倍：

\n

 254 ms \xc2\xb1  1 ms  original\n 525 ms \xc2\xb1  2 ms  optimized\n

\n

为什么？

\n

该基准测试构建了一个从 0 到 99999 的一千万个随机整数的排序列表，然后对所有不同的整数进行计数（仅用于基准测试，指出没有用Counter）（在线尝试！）：

\n

import random\nfrom bisect import bisect_left, bisect_right\nfrom timeit import repeat\nfrom statistics import mean, stdev\n\ndef original(a, x):\n    start = bisect_left(a, x)\n    stop = bisect_right(a, x)\n    return stop - start\n\ndef optimized(a, x):\n    start = bisect_left(a, x)\n    stop = bisect_right(a, x, start)\n    return stop - start\n\na = sorted(random.choices(range(100_000), k=10_000_000))\nunique = set(a)\n\ndef count_all():\n    for x in unique:\n        count(a, x)\nfor count in original, optimized:\n    times = repeat(count_all, number=1)\n    ts = [t * 1e3 for t in sorted(times)[:3]]\n    print(f\'{round(mean(ts)):4} ms \xc2\xb1 {round(stdev(ts)):2} ms \', count.__name__)\n

\n

Answer 1

基准测试在几个方面会引发不利的缓存影响。

首先，我打赌这个断言会为你通过（就像对我一样）：

assert list(unique) == sorted(unique)

不能保证它会通过，但考虑到迄今为止 CPython 的集合类型和整数哈希的实现，它很可能会通过。

这意味着您for x in unique正在x按严格递增的顺序进行尝试。这使得内部的潜在探测序列bisect_left()从一个到下一个几乎相同x，因此许多被比较的值可能位于缓存中。bisect_right()原始版本也是如此，但在优化版本中bisect_right()，尝试之间的潜在探测序列不同，因为尝试之间的起始索引不同。

要使两个版本都减慢“很多”，请在断言后添加以下内容：

unique = list(unique)
random.shuffle(unique)

现在，尝试之间的输入没有规律性x，因此尝试之间的潜在探测序列也没有系统相关性。

其他缓存效果只需一次尝试即可实现。bisect_left()在原文中，和之间的潜在探针序列完全相同bisect_right()。读取解析的条目bisect_left()很可能仍然位于缓存中以供bisect_right()重用。

但在优化版本中，潜在的探针序列不同，因为切片边界不同。例如，bisect_left()总是从比较x开始a[5000000]。在原始版本中，bisect_right()也总是从进行相同的比较开始，但在优化版本中几乎总是选择不同的索引来a开始 - 并且该索引纯粹是运气好而在缓存中等待。

尽管如此，我通常在我自己的代码中使用你的优化。但这是因为我的比较操作通常比整数比较昂贵得多，并且保存比较比保存一些缓存未命中更有价值。比较小整数的成本非常低，因此节省其中一些是没有什么价值的。