文档缺少示例...您如何基于 key 使用bisect.insort_left)_？
尝试根据键插入。
bisect.insort_left(data, ('brown', 7))
将插入放在
data[0]。从文档...
用法示例:
>>> 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]上...因为我没有使用键进行插入...文档未显示使用键进行插入。 最佳答案
这与 SortedCollection recipe 在中提到的 bisect documentation基本相同，另请参见:结尾处的部分，该部分支持键功能。
正在做的是将一个单独的已排序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)
您可以修改上面的内容以接受可选的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))
关于python - 如何通过 key 使用bisect.insort_left？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27672494/