如何使用带密钥的bisect.insort_left？

Question

医生缺少一个example...How --你使用基于密钥的bisect.insort_left)_吗？

尝试根据键插入。

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

把插入放在data[0]上。

从医生那里。

bisect.insort_left(a，x，lo=0，hi=len(A)hi=len(A)按排序顺序插入x。这相当于假设a已经排序的a.insert(bisect.bisect_left(a, x, lo, hi), x)。请记住，O(log )搜索是由缓慢的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)之后的('red', 5)放在data中的排序列表中。现在，bisect.insort_left(data, ('brown', 7))将('brown', 7)放在data[0]...because上，我不使用键来执行insert...docs，也不显示使用键进行插入。

Answer 1

这在本质上与食谱在其中提到的一样(参见:最后的部分)，但与食谱中的insert()方法不同，显示的函数支持一个键函数。

正在进行的工作是与排序的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()函数来实现这一点，因为它不是以支持键函数的方式编写的，相反，它只是将传递给它的整个项与其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)

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

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这样称呼它：

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

...called以这种方式进行，而不传递keyfunc：

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

Answer 2

您可以将可迭代性封装在实现__getitem__和__len__的类中。这使您有机会在bisect_left中使用密钥。如果您将类设置为以迭代函数和键函数作为参数。

为了将其扩展到insort_left中使用，需要实现insert方法。这里的问题是，如果您这样做，insort_left将尝试将您的键参数插入到包含键是其成员的对象的列表中。

一个更清楚的例子

from bisect import bisect_left, insort_left


class KeyWrapper:
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __getitem__(self, i):
        return self.key(self.it[i])

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

    def insert(self, index, item):
        print('asked to insert %s at index%d' % (item, index))
        self.it.insert(index, {"time":item})

timetable = [{"time": "0150"}, {"time": "0250"}, {"time": "0350"}, {"time": "0450"}, {"time": "0550"}, {"time": "0650"}, {"time": "0750"}]

bslindex = bisect_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")

islindex = insort_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")

看看如何在我的insert方法中，我必须使它特定于时间表字典，否则insort_left将尝试插入"0359"，它应该在哪里插入{"time": "0359"}

方法可以是为比较构建一个虚拟对象，从KeyWrapper继承并重写insert，或者传递某种工厂函数来创建对象。从惯用python的角度来看，这些方法都不是特别可取的。

因此，最简单的方法就是使用KeyWrapper和bisect_left，它返回插入索引，然后自己执行插入。您可以轻松地将其封装在一个专用函数中。

例如：

bslindex = bisect_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")
timetable.insert(bslindex, {"time":"0359"})

在这种情况下，请确保您没有实现insert，因此如果您意外地将KeyWrapper传递给像insort_left这样的变异函数，您就会立即意识到它可能做不到正确的事情。

使用示例数据

from bisect import bisect_left


class KeyWrapper:
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __getitem__(self, i):
        return self.key(self.it[i])

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

data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
data.sort(key=lambda c: c[1])

newcol = ('brown', 7)

bslindex = bisect_left(KeyWrapper(data, key=lambda c: c[1]), newcol[1])
data.insert(bslindex, newcol)

print(data)

以下是正确键入的类：

from typing import TypeVar, Generic, Sequence, Callable


T = TypeVar('T')
V = TypeVar('V')


class KeyWrapper(Generic[T, V]):
    def __init__(self, iterable: Sequence[T], key: Callable[[T], V]):
        self.it = iterable
        self.key = key

    def __getitem__(self, i: int) -> V:
        return self.key(self.it[i])

    def __len__(self) -> int:
        return len(self.it)

Answer 3

向类添加比较方法

有时候，这是最不痛苦的方法，特别是如果您已经有了一个类，并且只想按键排序：

#!/usr/bin/env python3

import bisect
import functools

@functools.total_ordering
class MyData:
    def __init__(self, color, number):
        self.color = color
        self.number = number
    def __lt__(self, other):
        return self.number < other.number
    def __str__(self):
        return '{} {}'.format(self.color, self.number)

mydatas = [
    MyData('red', 5),
    MyData('blue', 1),
    MyData('yellow', 8),
    MyData('black', 0),
]
mydatas_sorted = []
for mydata in mydatas:
    bisect.insort(mydatas_sorted, mydata)
for mydata in mydatas_sorted:
    print(mydata)

输出：

black 0
blue 1
red 5
yellow 8

另见：类的“启用”比较

在Python3.5.2中测试。

上游请求/修补程序

我觉得这迟早会发生;-)

• https://github.com/python/cpython/pull/13970
• https://bugs.python.org/issue4356