[Python-Dev] Adding key and reverse args to bisect

[Raymond Hettinger]

[David A. Barrett]
>I propose adding the key parameter
> to the bisect.bisect routines.  This
> would allow it to be used on lists with
> an ordering other than the one "natural"
> to the contained objects.

Algorithmically, the bisect routines are the wrong place to do key lookups.
If you do many calls to bisect(), each one will make multiple calls to the key
function, potentially repeating calls that were made on previous searches.
Instead, it is better to search a list of precomputed keys to find the index
of the record in question.

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])    # key function called exactly len(data) times
>>> keys = [r[1] for r in data]
>>> 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)


Raymond