rbossy
3/4/2008 3:10:00 PM
Quoting Raymond Hettinger <python@rcn.com>:
> [Robert Bossy]
> > I thought it would be useful if insort and consorts* could accept the
> > same options than list.sort, especially key and cmp.
>
> If you're going to do many insertions or searches, wouldn't it be
> *much* more efficient to store your keys in a separate array?
>
> The sort() function guarantees that it calls the key function exactly
> once for each member of the list. With and bisect/insort, successive
> searches can call the key function over and over again with the same
> value.
I factored your remark into the code. I actually don't have any particular
question about it, that's just an acknowledgment. Though I feel that if one
uses the default key, then an awkward list of twins is stored...
from operator import itemgetter
def identity(x): return x
class Bisect:
def __init__(self, it, key=identity, cmp=cmp):
self.lst = [ (key(x),x,) for x in it ]
self.lst.sort(cmp=cmp, key=itemgetter(0))
self.key = key
self.cmp = cmp
def insort_right(self, x, lo = 0, hi = None):
if hi is None:
hi = len(self.lst)
xk = self.key(x)
while lo < hi:
mid = (lo + hi) // 2
if self.cmp(xk, self.lst[mid][0]) < 0:
hi = mid
else:
lo = mid + 1
self.lst.insert(lo, (kx,x,))
# skipped insort_left, bisect_right, bisect_left
# also skipped the container methods __len__, __getitem__, __iter__
Cheers,
RB