如何使用带键的 bisect.insort_left？

Question

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

尝试根据键插入。

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

将插入放在 data[0] 。

从文档…

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

按排序顺序将 x 插入 a 中。这相当于 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) bisect.insort_left data 5EB0623BCD3EEMANING中的排序列表中现在 bisect.insort_left(data, ('brown', 7)) 把 ('brown', 7) 放在 data[0] …因为我没有使用键来插入…文档插入不使用不显示文档按键。

原文由 Merlin 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这与 SortedCollection 配方 的作用基本相同 bisect 文档 在其末尾提到 ： 部分，但与 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() 函数来执行此操作，因为它不是以支持键函数的方式编写的——相反，它只是比较传递给它的整个项目以插入， 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)

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

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

原文由 martineau 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

See how in my insert method I had to make it specific to the timetable dictionary otherwise insort_left would try insert "0359" where it should insert {"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)

原文由 Paul Rooney 发布，翻译遵循 CC BY-SA 4.0 许可协议