为何Python二分查找添加搜索起点优化后运行速度反而慢两倍？

本想通过缩小二分查找区间优化有序列表的元素计数逻辑，实际测试性能反而下降两倍以上：

• 初始实现思路：对有序列表a，用bisect_left找到目标值x的左边界，用bisect_right找到右边界，两个位置的差值就是x的出现次数，初始代码如下：

from bisect import bisect_left, bisect_right

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

• 预期优化思路：右边界不可能出现在左边界之前，因此给bisect_right传入左边界位置作为查找起点，跳过左边界之前的区间，减少比较次数（参考bisect模块的参数规则），优化后代码如下：

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

• 基准测试结果：优化后版本耗时达到原版本的两倍以上

254 ms ±  1 ms  original
 525 ms ±  2 ms  optimized

• 测试逻辑：生成1000万个取值范围在0到99999的随机整数，排序后得到有序列表，遍历列表中所有不重复的整数执行计数（本次测试仅验证性能，不讨论Counter等其他计数方案），测试代码如下：

import random
from bisect import bisect_left, bisect_right
from timeit import repeat
from statistics import mean, stdev

def original(a, x):
    start = bisect_left(a, x)
    stop = bisect_right(a, x)
    return stop - start

def optimized(a, x):
    start = bisect_left(a, x)
    stop = bisect_right(a, x, start)
    return stop - start

a = sorted(random.choices(range(100_000), k=10_000_000))
unique = set(a)

def count_all():
    for x in unique:
        count(a, x)
for count in original, optimized:
    times = repeat(count_all, number=1)
    ts = [t * 1e3 for t in sorted(times)[:3]]
    print(f'{round(mean(ts)):4} ms ± {round(stdev(ts)):2} ms ', count.__name__)

这个“优化”收益极低，反而引入了额外开销：

1. 优化带来的性能收益可以忽略：二分查找的时间复杂度是O(log n)，对长度为1000万的列表，一次完整二分查找仅需要约24次比较就能定位边界。本次测试场景中，每个数值平均仅出现100次（1000万总元素 / 10万取值范围 = 平均每值出现100次），传入lo=start仅把查找区间长度缩短了100，对应的比较次数仅减少了不到1次，几乎没有实际收益。
2. 传入额外参数引入了可观的额外开销：bisect模块的函数是C实现的，当不显式传入lo、hi参数时，函数直接使用C层面预设的默认值（0和列表总长度），不需要额外做参数处理；一旦显式传入lo参数，C函数就要额外执行参数解析、边界合法性校验等逻辑，这部分开销远大于省下来的不到1次比较的成本，十几万次调用累积下来，总耗时直接翻倍。

注：这个传参技巧不是完全没用，如果场景中单个值的连续出现区间非常长（比如半个列表都是同一个值），传入lo参数能减少多次比较，收益可以覆盖参数处理的开销；但在本次测试的场景下，收益微乎其微，额外开销占了主导，才会出现越优化越慢的结果。

内容的提问来源于stack exchange，提问作者Kelly Bundy