为什么在bisect函数中添加`reversed`参数被认为效率低？

Question

我们可以使用Python的bisect模块来高效地将项目插入到一个已经排好序的列表中。

不过，这个列表必须是按升序排列的，这并不总是能保证的。

在文档中，解释了原因：

与sorted()函数不同，bisect()函数不支持key或reversed参数，因为这样会导致设计效率低下（连续调用bisect函数时不会“记住”之前的key查找）。

但是，当我查看源代码时，并没有看到任何似乎在“记住”key查找的内容。

我们可以简单地添加一个reversed参数，并在必要时交换这个条件表达式中的then部分：

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

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

Answer 1

你可以写一个适配器：

import bisect

class rvrbisect:
    def __init__(self, data):
        self.data = data

    def idxcnv(self, idx): return len(self.data) - idx - 1

    def __getitem__(self, idx):
        return self.data[self.idxcnv(idx)]

    def __setitem__(self, idx, value):
        self.data[self.idxcnv(idx)] = value

    def __len__(self): return len(self.data)

    def insert(self, idx, value):
        self.data.insert(self.idxcnv(idx) + 1, value)

data = rvrbisect([30, 20, 10])
bisect.insort(data, 25)
bisect.insort(data, 15)
bisect.insort(data, 1)
bisect.insort(data, 190)
print data.data

Answer 2

文档的意思是，bisect这个函数是为了在同一组项目上反复使用而设计的。与其每次都动态计算键值，不如提前计算好键值再使用，这样效率更高，特别是因为项目列表和键值列表是平行的，所以可以用同一个索引来处理两者。

至于反转，你可以通过反转键值列表来达到同样的效果：

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

不过，这样做只有在你需要多次搜索时，反复使用同样的键值才有意义。