这确实基本上是同样的事情
SortedCollectionrecipe确实该
bisect文件中提到 另请参见: 部分在其支持一键功能结束。
要做的是将一个单独的排序
keys列表与该排序
data列表并行维护以提高性能(它比每次插入之前创建键列表都快,但是严格要求保留并更新它)。ActiveState配方为您将其封装在一个类中,但是在下面的代码中,它们只是传递的两个独立的独立列表(因此,与同时持有它们相比,它们不同步会更容易在食谱类的实例中)。
from bisect import bisect_leftdef 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://pre.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 valuekeys = [r[1] for r in data] # Initialize keys listprint(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,
ifa[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))