42

文档缺少示例...您如何bisect.insort_left)_根据密钥使用？

尝试基于键插入。

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

将插入放在data[0].

从文档...

bisect.insort_left(a, x, lo=0, hi=len(a)按排序顺序)

    插入x。这相当于假设a已经排序。请记住，O(log n) 搜索主要由缓慢的 O(n) 插入步骤支配。a.insert(bisect.bisect_left(a, x, lo, hi), x)

示例用法：

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

4

5 回答 5

24

你可以将你的迭代包装在一个实现__getitem__和的类中__len__。这使您有机会将密钥与bisect_left. 如果您将类设置为将可迭代和键函数作为参数。

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

一个例子更清楚

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 角度来看，这些方式都不是特别理想的。

所以最简单的方法是只使用KeyWrapperwith bisect_left，它会返回插入索引，然后自己进行插入。您可以轻松地将其包装在专用函数中。

例如

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

在这种情况下，请确保您没有实现insert，因此您将立即意识到如果您不小心将 a 传递给了一个可能不会做正确事情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)
于 2016-09-15T00:19:05.560 回答
19

这基本上与文档在其另请参阅：最后部分中提到的SortedCollection 配方所做的相同，但与配方中的方法不同，显示的功能支持键功能。bisectinsert()

正在做的是与排序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))
于 2014-12-28T01:45:31.203 回答
10

向您的课程添加比较方法

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

#!/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

另请参阅：类的“启用”比较

在 Python 3.5.2 中测试。

上游请求/补丁

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

于 2019-03-05T16:29:02.350 回答
7

如果您的目标是维护一个按 key 排序的列表，执行诸如bisect insert、 delete 和 update之类的常规操作，我认为sortedcontainers也应该满足您的需求，并且您将避免 O(n) 插入。

于 2016-06-18T09:04:30.667 回答
3

从 Python 3.10 开始，模块中的所有二进制搜索助手bisect现在都接受一个key参数：

key指定一个参数的键函数，用于从每个输入元素中提取比较键。默认值为None （直接比较元素）。

因此，您可以传递用于对数据进行排序的相同函数：

>>> import bisect
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> data
[('black', 0), ('blue', 1), ('red', 5), ('yellow', 8)]
>>> bisect.insort_left(data, ('brown', 7), key=lambda r: r[1])
>>> data
[('black', 0), ('blue', 1), ('red', 5), ('brown', 7), ('yellow', 8)]
于 2021-10-20T13:57:54.130 回答