[Python-ideas] Optional key to `bisect`'s functions?

[Guido van Rossum]

On Thu, Feb 9, 2012 at 9:27 AM, Raymond Hettinger <
raymond.hettinger at gmail.com> wrote:

>
> On Feb 8, 2012, at 4:25 PM, Guido van Rossum wrote:
>
> Also note that "many times" is actually O(log N) per insertion, which
> isn't so bad. The main use case for bisect() is to manage a list that sees
> updates *and* iterations -- otherwise building the list unsorted and
> sorting it at the end would make more sense. The key= option provides a
> balance between the cost/elegance for updates and for iterations.
>
>
> Would you be open to introducing a SortedList class to encapsulate the
> data so that key functions get applied no more than once per record and the
> sort order is maintained as new items are inserted?
>

Hm. A good implementation of such a thing would probably require a B-tree
implementation (or some other tree). That sounds like a good data type to
have in the collections module, but doesn't really address the desire to
use bisect on a list. Also it further erodes my desire not to bother the
programmer with subtle decisions about the choice of data type: the most
basic types (string, number, list, dict) are easy enough to distinguish,
and further choices between subclasses or alternatives are usually a
distraction.


> ISTM, the whole problem with bisect is that the underlying list is naked,
> leaving no way to easily correlate the sort keys with the corresponding
> sorted records.
>

That same "problem" would exist for sorted() and list.sort(), and the
solution there (parameterize it with a key= option) easily generalizes to
bisect (and to heapq, for that matter).

The more fundamental "conflict" here seems to be between algorithms and
classes. list.sort(), bisect and heapq focus on the algorithm. In some
sense they reflect the state of the world before object-oriented
programming was invented. Sometimes it is useful to encapsulate these in
classes. Other times, the encapsulation doesn't add to the clarity of the
program.

One more thing: bisect.py doesn't only apply to insertions. It is also
useful to find a "nearest" elements in a pre-sorted list. Probably that
list was sorted using list.sort(), possibly using key=...

-- 
--Guido van Rossum (python.org/~guido)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20120209/ad2dce99/attachment.html>