如何通过密钥使用bisect.insort_left? [英] How to use bisect.insort_left with a key?

问题描述

文档缺少示例...您如何基于密钥使用bisect.insort_left)_?

Doc's are lacking an example...How do you use bisect.insort_left)_ based on a key?

尝试根据密钥插入.

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

放置在data[0]处.

来自文档...

bisect.insort_left( a，x，lo = 0，hi = len(a) )

    按排序顺序将 x 插入 a 中.假设 a 已被排序，这等效于a.insert(bisect.bisect_left(a, x, lo, hi), x).请记住，O(log n)搜索主要由缓慢的O(n)插入步骤决定.

bisect.insort_left(a, x, lo=0, hi=len(a))

    Insert x in a in sorted order. This is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x) assuming that a is already sorted. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

样品用量:

>>> 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)
>>>

我想使用bisect.insort_left将('brown', 7)之后的('brown', 7)放在data中的排序列表上.现在bisect.insort_left(data, ('brown', 7))将('brown', 7)放在data[0]处...因为我没有使用键进行插入...文档未显示使用键进行插入.

I want to put ('brown', 7) after ('red', 5) on sorted list in data using bisect.insort_left. Right now bisect.insort_left(data, ('brown', 7)) puts ('brown', 7) at data[0]...because I am not using the keys to do insert...docs don't show to do inserts using the keys.

推荐答案

bisect文档在最后的另请参见部分中提到，该部分支持键功能.

This does essentially the same thing the SortedCollection recipe does that the bisect documentation mentions in the See also: section at the end which supports a key-function.

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

What's being done is a separate sorted keys list is maintained in parallel with the sorted data list to improve performance (it's faster than creating the keys list before each insertion, but keeping it around and updating it isn't strictly required). The ActiveState recipe encapsulated this for you within a class, but in the code below they're just two separate independent lists being passed around (so it'd be easier for them to get out of sync than it would be if they were both held in an instance of the recipe's class).

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吗?

Follow-on question:
    Can bisect.insort_left be used?

不，您不能简单地使用bisect.insort_left()函数来执行此操作，因为它不是以支持键功能的方式编写的-而是仅将传递给它的整个项目进行比较以插入，并在其if a[mid] < x:语句中使用数组中的全部项目之一.通过查看

No, you can't simply use the bisect.insort_left() function to do this because it wasn't written in a way that supports a key-function—instead it just compares the whole item passed to it to insert, x, with one of the whole items in the array in its if a[mid] < x: statement. You can see what I mean by looking at the source for the bisect module in 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参数并使用它:

You could modify the above to accept an optional key-function argument and use it:

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
    . . .

...并这样称呼它:

...and call it like this:

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

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

Actually, if you're going to write a custom function, for the sake of more efficiency at the expense of unneeded generality, you could dispense with the adding of a generic key function argument and just hardcode everything to operate the way needed with the data format you have. This will avoid the overhead of repeated calls to a key-function while doing the insertions.

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:

...called this way without passing keyfunc:

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

这篇关于如何通过密钥使用bisect.insort_left?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！