python - 为什么向二等分函数添加 `reversed` 参数被认为效率低下？

Question

我们可以使用Python的bisect模块可有效地将项目插入已排序的列表中。

但是列表必须按升序排序，但情况并非总是如此。

在 documentation ，解释一下原因:

Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups).

但是，当我查看source code时，我看不到任何似乎“记住”键查找的内容。

我们只需添加 reversed参数，并交换 then必要时作为此条件表达式的一部分:

if x < a[mid]: hi = mid
else: lo = mid+1

为什么这被认为是低效的设计？

Answer 1

文档的内容是，bisect 函数旨在对同一项目列表反复使用。与使用函数求值来动态计算键不同，预先计算键并使用它们会更有效，特别是因为项目列表和键列表是并行的，因此可以对两者使用相同的索引。

对于反转，通过反转键列表也可以获得相同的效果:

items = [9,7,5,3,1]
keys = list(reversed(items))
index = len(items)-bisect_right(keys,7)

但同样，只有当您要一遍又一遍地重复使用相同的键进行多次搜索时，这才有意义。