Adding key and reverse args to bisect
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. (and anywhere else it makes sense in the bisect module). Would this be easy enough to do? It looks like the main difficulty may have to do with the C implementation. I've also noticed that sort appears far faster; is the C implementation working as expected? It may be nice to have the reverse parameter as well, but I'm not sure how that could be implemented right off the bat. David A. Barrett     Here's an example I've coded up for my own use (reverse hasn't been implemented here): def bisect_right(a, x, lo=0, hi=None, key=lambda x: x, reverse=False): """A keyed version of bisect.bisect_bisect_right: return i: for all e in a[:i] e <= x < f, for all f in a[i:] """ if hi is None: hi = len(a) if reverse: while lo < hi: mid = (lo+hi)//2 if key(a[mid]) < key(x): hi = mid else: lo = mid+1 else: while lo < hi: mid = (lo+hi)//2 if key(x) < key(a[mid]): hi = mid else: lo = mid+1 return lo def bisect_left(a, x, lo=0, hi=None, key=lambda x: x, reverse=False): """A keyed version of bisect.bisect_bisect_left: return i: for all e in a[:i] e < x <= f, for all f in a[i:] """ if hi is None: hi = len(a) if reverse: while lo < hi: mid = (lo+hi)//2 if key(x) < key(a[mid]): lo = mid+1 else: hi = mid else: while lo < hi: mid = (lo+hi)//2 if key(a[mid]) < key(x): lo = mid+1 else: hi = mid return lo
[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
On Thu, Jun 11, 2009, David A. Barrett wrote:
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.
Raymond addressed your actual question, but please post suggestions like this to pythonideas, that's the best place for them.  Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ "If you don't know what your program is supposed to do, you'd better not start writing it." Dijkstra
participants (3)

Aahz

David A. Barrett

Raymond Hettinger