Python bisect 的 key 函数重复开销怎样减少

如果你给一组记录按字段排序，再用 bisect_left() 做范围定位，代码看起来已经是二分查找了，但性能仍可能不稳定：每次比较都要重新执行一次昂贵的 key 函数。解决办法不是把二分算法改成别的算法，而是让“排序对象”和“比较键”分离：先计算并保存一条有序的 keys 列表，查找时只对 keys 二分，再按返回的索引取回原记录。

官方文档地址：https://docs.python.org/3/library/bisect.html

Python 的 bisect 搜索函数不会保留 key 函数的返回值。如果同一个有序列表要被循环查询，优先考虑预计算 keys；只有数据经常变化或 key 很轻量时，才继续直接传 key。

先看见问题：二分很快，key 可能很慢

假设记录里存的是文件名和一段需要解析的时间字符串。列表按时间排序，查询时希望找到第一个不早于目标时间的记录：

from bisect import bisect_left
from datetime import datetime

records = [
    {"name": "a.log", "created_at": "2026-01-10 09:00:00"},
    {"name": "b.log", "created_at": "2026-01-10 10:30:00"},
    {"name": "c.log", "created_at": "2026-01-10 13:00:00"},
]

def created_at(record):
    # 这里模拟一次有成本的字段解析；真实项目中也可能是规范化、解码或对象访问。
    return datetime.strptime(record["created_at"], "%Y-%m-%d %H:%M:%S")

records.sort(key=created_at)
target = datetime(2026, 1, 10, 10, 0)
index = bisect_left(records, target, key=created_at)
print(records[index]["name"])

这段代码的排序结果没有问题，但 bisect_left 的比较过程会在搜索节点上调用 created_at。官方文档特别提醒，搜索函数是无状态的，使用过的 key 结果会被丢弃；当它被放进循环时，同一条记录的 key 可能再次计算。

用计数器判断是不是 key 在反复工作

不要只看“二分是 O(log n)”就认为整个查询一定便宜。给 key 加一个计数器，很快就能把搜索次数和解析次数分开：

from bisect import bisect_left

records = [{"score": score, "name": f"item-{score}"} for score in range(0, 1000, 10)]
calls = 0

def score_of(record):
    global calls
    # 计数只用于定位重复计算，不改变 key 的返回值。
    calls += 1
    return record["score"]

for target in (120, 340, 680, 920):
    # key 只接收列表元素；target 已经是同类型的比较值，不会再经过 key。
    position = bisect_left(records, target, key=score_of)
    print(target, position)

print("key calls:", calls)

如果循环查询很多目标，计数会随着查询次数增长。这里的重点不是某一次调用一定会比较多少个节点，而是 key 结果没有跨查询复用。若 key 内部包含日期解析、大小写归一化、路径处理或对象转换，重复成本就会比整数比较明显。

最稳妥的修复：预计算一条 keys 列表

当记录列表排序后会被查询多次，可以把每条记录的比较值提前取出。两条列表保持相同顺序：records[i] 的键必须始终是 keys[i]。二分只操作 keys，拿到位置后再访问 records：

from bisect import bisect_left
from datetime import datetime

records = [
    {"name": "a.log", "created_at": "2026-01-10 09:00:00"},
    {"name": "b.log", "created_at": "2026-01-10 10:30:00"},
    {"name": "c.log", "created_at": "2026-01-10 13:00:00"},
]

def created_at(record):
    # 排序和预计算共用同一个键定义，避免两处规则漂移。
    return datetime.strptime(record["created_at"], "%Y-%m-%d %H:%M:%S")

records.sort(key=created_at)
keys = [created_at(record) for record in records]
target = datetime(2026, 1, 10, 10, 0)

# 二分只读取已经准备好的 keys，不再解析记录。
index = bisect_left(keys, target)
if index 

这里的收益来自一次性付费：初始化阶段计算 N 个 key，之后每次查询只做对 keys 的二分。返回的 index 仍然指向原始记录，因此不会丢失其他字段。

新增和删除时，两个数组必须一起维护

并行列表的关键风险不是 bisect，而是同步。如果只插入 records 而忘记插入 keys，二分结果就会指向错误记录。新增记录时先算键，再用同一个位置插入两边：

from bisect import bisect_right

def insert_record(records, keys, record, key):
    # 先计算一次键，搜索和插入共用这个结果。
    record_key = key(record)
    position = bisect_right(keys, record_key)
    keys.insert(position, record_key)
    records.insert(position, record)

def remove_at(records, keys, position):
    # 删除必须使用同一个位置，保持两条列表长度和顺序一致。
    del keys[position]
    del records[position]

如果更新了某条记录的排序字段，最简单可靠的做法通常是删除旧位置、修改记录、重新插入。不要只改 records 中的字段，因为旧 key 仍会留在 keys 中。

还要注意，insort 的查找部分可以使用 key，但插入动作仍是线性移动；如果瓶颈来自大量中间插入，而不是 key 计算，预计算 keys 只能解决其中一段成本。

什么时候用缓存，什么时候用 keys

Python 文档还给出另一条思路：给 key 函数包一层缓存。它适合列表不变、key 计算昂贵、又希望保留原有 bisect_left(records, target, key=key) 调用形式的场景：

from bisect import bisect_left
from functools import cache

records = [(f"item-{score}", score) for score in range(0, 1000, 10)]

@cache
def score_of(record):
    # 元组是稳定、可哈希的输入，适合用作缓存键；可变字典不能直接这样缓存。
    return record[1]

target = 340
# 缓存让同一个元组的 key 结果可以跨查询复用。
index = bisect_left(records, target, key=score_of)
print(records[index] if index 

不过缓存方案要认真考虑缓存键的生命周期和容量；记录变化后，旧结果也可能失效。对于同一批数据需要大量查询，显式维护 keys 通常更容易看懂，也更容易在新增、删除和重排时一起更新。

用这张表做最后选择

几个容易忽略的边界

• keys 必须和 records 使用同一种排序规则；排序完成后再创建 keys。
• bisect_left 返回相等值的左侧位置，bisect_right 返回右侧位置，重复键要按业务选择。
• 二分只保证定位成本接近对数级；插入列表仍可能需要移动大量元素。
• 同一个序列被多个线程同时修改或查找时，不能把 bisect 当作线程安全容器。

总结

bisect 的 key 函数重复开销，本质上是“搜索函数不保存中间键”的结果。数据稳定且查询频繁时，使用 records + keys 两条并行列表最直接；数据变化较少、又想保留原调用方式时，可以考虑缓存 key。无论选哪种方案，都要把排序规则、更新动作和重复键策略放在一起设计。

相关问题

bisect 的 key 会作用于 target 吗？不会。key 用于提取列表元素的比较键，传入的 target 应该已经是可比较的键值。

为什么不直接用字典？bisect 适合找范围或插入点；如果目标是精确匹配某个唯一键，字典通常更直接。

预计算 keys 会不会占用更多内存？会增加一条键列表的存储，但换来了查询时不重复计算。应按 key 成本、查询次数和数据规模权衡。