如何通过密钥使用bisect.insort_left？

Question

Doc缺少示例…您如何bisect.insort_left)_基于密钥使用？

尝试根据键插入。

bisect.insort_left(data, ('brown', 7))

将插入位置放在data[0]。

从文档…

bisect.insort_left( A，X，LO = 0，HI = LEN（a）中)

插入 X 在 一个 按排序顺序。这等效于a.insert(bisect.bisect_left(a, x, lo, hi), x)假设
a 已经排序。请记住，O（log n）搜索由缓慢的O（n）插入步骤主导。

用法示例：

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)
>>>

我希望把('brown', 7)后('red', 5)排序列表中data使用bisect.insort_left。眼下bisect.insort_left(data, ('brown', 7))看跌期权('brown', 7)的data[0]......因为我不使用的钥匙，做插入…文档不显示做用钥匙插入。

Answer 1

这确实基本上是同样的事情SortedCollection recipe确实该bisect文件中提到 另请参见： 部分在其支持一键功能结束。

要做的是将一个单独的排序keys列表与该排序data列表并行维护以提高性能（它比每次插入之前创建键列表都快，但是严格要求保留并更新它）。ActiveState配方为您将其封装在一个类中，但是在下面的代码中，它们只是传递的两个独立的独立列表（因此，与同时持有它们相比，它们不同步会更容易在食谱类的实例中）。

from bisect import bisect_left

def insert(seq, keys, item, keyfunc=lambda v: v):
    """Insert an item into a sorted list using a separate corresponding
       sorted keys list and a keyfunc() to extract the key from each item.

    Based on insert() method in SortedCollection recipe:
    http://code.activestate.com/recipes/577197-sortedcollection/
    """
    k = keyfunc(item)  # Get key.
    i = bisect_left(keys, k)  # Determine where to insert item.
    keys.insert(i, k)  # Insert key of item to keys list.
    seq.insert(i, item)  # Insert the item itself in the corresponding place.

# Initialize the sorted data and keys lists.
data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
data.sort(key=lambda r: r[1]) # Sort data by key value
keys = [r[1] for r in data]   # Initialize keys list
print(data)  # -> [('black', 0), ('blue', 1), ('red', 5), ('yellow', 8)]

insert(data, keys, ('brown', 7), keyfunc=lambda x: x[1])
print(data)  # -> [('black', 0), ('blue', 1), ('red', 5), ('brown', 7), ('yellow', 8)]

后续问题：
可以bisect.insort_left使用吗？

不，您不能简单地使用该bisect.insort_left()函数来完成此操作，因为它不是以支持键功能的方式编写的；相反，它只是将传递给它的整个项目与insert中的插入项目进行比较x，if a[mid] < x:语句中的数组。通过查看中的bisect模块源，可以了解我的意思Lib/bisect.py。

以下是相关摘录：

def insort_left(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the left of the leftmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    a.insert(lo, x)

您可以修改上面的内容以接受可选的key-function参数并使用它：

def my_insort_left(a, x, lo=0, hi=None, keyfunc=lambda v: v):
    x_key = keyfunc(x)  # Get comparison value.
    . . .
        if keyfunc(a[mid]) < x_key: # Compare key values.
            lo = mid+1
    . . .

…并这样称呼它：

my_insort_left(data, ('brown', 7), keyfunc=lambda v: v[1])

实际上，如果您要编写自定义函数，则为了提高效率而以不必要的通用性为代价，则可以省去添加通用键函数参数，而只需对所有内容进行硬编码即可以所需的方式操作数据格式。这样可以避免在插入时重复调用键函数的开销。

def my_insort_left(a, x, lo=0, hi=None):
    x_key = x[1]   # Key on second element of each item in sequence.
    . . .
        if a[mid][1] < x_key: lo = mid+1  # Compare second element to key.
    . . .

…这样调用而不传递keyfunc：

my_insort_left(data, ('brown', 7))