Merlin Merlin -3 years ago 147
Python Question

How to use bisect.insort_left with a key?

Doc's are lacking an example...How do you use

bisect.insort_left)_
based on a key?

Trying to insert based on key.

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


puts insert at
data[0]
.

From docs...


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



    Insert x in a in sorted order. This is equivalent to
a.insert(bisect.bisect_left(a, x, lo, hi), x)
assuming that a is already sorted. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.


Sample usage:

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


I want to put
('brown', 7)
after
('red', 5)
on sorted list in
data
using
bisect.insort_left
. Right now
bisect.insort_left(data, ('brown', 7))
puts
('brown', 7)
at
data[0]
...because I am not using the keys to do insert...docs don't show to do inserts using the keys.

Answer Source

This does essentially the same thing the SortedCollection recipe does that the bisect documentation mentions in the See also section at the end which supports a key-function.

What's being done is a separate sorted keys list is maintained in parallel with the sorted data list to improve performance (it's faster than creating the keys list before each insertion, but keeping it around and updating it isn't a strict requirement). The ActiveState recipe encapsulated this for you within a class, but in the code below they're just two separate independent lists being passed around (so it'd be easier for them to get out of sync than it would be if they were both held in an instance of the recipe's class).

from bisect import bisect_left

# Based on code in the SortedCollection recipe:
#   http://code.activestate.com/recipes/577197-sortedcollection/
def insert(seq, keys, item, keyfunc):
    """Insert an item into the sorted list using separate corresponding
       keys list and a keyfunc to extract key from each item.
    """
    k = keyfunc(item)  # get key
    i = bisect_left(keys, k)  # determine where to insert item
    keys.insert(i, k)  # insert key of item in keys list
    seq.insert(i, item)  # insert the item itself in the corresponding spot

# initialize 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)]

Follow-on question:
    Can bisect.insort_left be used?

You can't simply use the bisect.insort_left() function to do this because it was written in a way that doesn't support a key-function — instead it just compares the whole item passed to it to insert, x, with one of the whole items in the array in its if a[mid] < x: statement. You can see what I mean by looking at the source for the bisect module in Lib/bisect.py.

Here's the relevant excerpt:

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)

You could modify the above to accept an optional key-function argument and use it:

def my_insort_left(a, x, lo=0, hi=None, keyfunc=lambda v: v):
    x_key = keyfunc(x)
    . . .
        if keyfunc(a[mid]) < x_key: lo = mid+1
    . . .

...and call it like this:

my_insort_left(data, ('brown', 7), key=lambda v: v[1])

Actually, if you're going to write a custom function, for the sake of more efficiency at the expense of unneeded generality, you could dispense with the adding of a generic key function argument and just hardcoded things to operate the way needed with the data format you have:

def my_insort_left(a, x, lo=0, hi=None):
    x_key = x[1]   # key on second element of each item sequence
    . . .
        if a[mid][1] < x_key: lo = mid+1
    . . .

...called this way:

my_insort_left(data, ('brown', 7))
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download