Hi, 2012/2/8 Masklinn

The ``bisect`` stuff is pretty neat, although probably underused (especially the insorts), but their usefulness is limited by the requirement that the lists directly contain sortable items, as opposed to ``sorted`` or ``list.sort``.

It's possible to "use" them by copy/pasting the (Python) functions into the project/library code and adding either a custom key directly or a key function, but while this can still yield an order-of-magnitude speed gain over post-sorting sequences, it's cumbersome and it loses the advantage of _bisect's accelerators.

Therefore, I believe it would be pretty neat to add an optional ``key=`` keyword (only?) argument, with the same semantics as in ``sorted``. It would make ``bisect`` much easier to use especially in stead of append + sorted combinations. The key should work for both insertion functions and bisection search ones. bisect key

This was proposed several times on the issue tracker (search for "bisect key"), and these proposals have always been rejected: http://bugs.python.org/issue4356 http://bugs.python.org/issue1451588 http://bugs.python.org/issue3374 The last one summarizes the reasons of the rejection. The documentation (http://docs.python.org/library/bisect.html, "see also") contains a link to a "SortedCollection" recipe. I haven't looked at the SortedCollection class in detail, but you could try to have it included in the stdlib... -- Amaury Forgeot d'Arc

On 2/8/2012 7:25 PM, Guido van Rossum wrote:

Hmm... I disagree with Raymond's rejection of the proposed feature. I have come across use cases for this functionality multiple time in real life.

Basically Raymond says "bisect can call the key() function many times, which leads to bad design". His alternative, to use a list of (key, value) tuples, is often a bit clumsy when passing the sorted list to another function (e.g. for printing); having to transform the list using e.g. [v for (k, v) in a] feels clumsy and suboptimal. So I'm not sure that refusing the key= option always leads to the best design (in the sense of the most readable code).

An alternative to the n x 2 array is two n-arrays or a 2 x n array. Then there is no problem using either the keys or the values array. To use insort_right or insort_left for this, they would have to return the insertion position instead of None. Right now one must use bisect_right or _left and then .insert into both arrays instead of just the vals array.

Adding key= is particularly attractive since the current invariant is something like "if a == sorted(a) before the operation, then a == sorted(a) after the operation". Adding a key= option would simply change that to sorted(a, key=key) on both counts.

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.

For *large enough* lists, the O(n*n) cost of insertions will dominate the O(n*logN) key() calls, so reducing the latter to O(n) key calls will not matter. -- Terry Jan Reedy

On 2012-02-09, at 01:25 , Guido van Rossum wrote:

Hmm... I disagree with Raymond's rejection of the proposed feature. I have come across use cases for this functionality multiple time in real life.

Basically Raymond says "bisect can call the key() function many times, which leads to bad design". His alternative, to use a list of (key, value) tuples, is often a bit clumsy when passing the sorted list to another function (e.g. for printing); having to transform the list using e.g. [v for (k, v) in a] feels clumsy and suboptimal.

Yes, this is the kind of things which prompted my original email. It is even clumsier when there are many (smaller) lists to manipulate and insert into in turn, and requires two verbose and potentially expensive phases of decoration and undecoration. Using two separate lists has similar (though simpler) issues, especially when producing API-related structures as the "helper" collection must be cleaned up during an undecoration phase. And as Terry notes, this gets very clumsy as each candidate insertion now requires three statements (a call to bisect_right to get the insertion index followed by an insertion into the helper list and an other one for the actual list).

On 9 February 2012 00:25, Guido van Rossum wrote:

Basically Raymond says "bisect can call the key() function many times, which leads to bad design". His alternative, to use a list of (key, value) tuples, is often a bit clumsy when passing the sorted list to another function (e.g. for printing); having to transform the list using e.g. [v for (k, v) in a] feels clumsy and suboptimal.

Also, in Python 3 one can't assume that values will be comparable so the (key, value) tuple trick won't work: comparing the tuples may well throw a TypeError. Here's a simple example below. The class 'Person' has no natural order, but we may want to keep a list of people sorted by iq:

...

...

class Person: ... def __init__(self, height, iq): ... self.height = height ... self.iq = iq ... arno = Person(184, 101) guido = Person(179, 185) steve = Person(168, 101) key = lambda p: p.iq people = [] bisect.insort(people, (key(arno), arno)) bisect.insort(people, (key(guido), guido)) bisect.insort(people, (key(steve), steve)) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unorderable types: Person() < Person()

-- Arnaud

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? 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. Raymond

On Thu, Feb 9, 2012 at 9:27 AM, Raymond Hettinger < raymond.hettinger@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)

On Feb 9, 2012, at 9:50 AM, Daniel Stutzbach wrote:

Maintaining a sorted list using Python's list type is a trap. The bisect is O(log n), but insertion and deletion are still O(n).

A SortedList class that provides O(log n) insertions is useful from time to time. There are several existing implementations available (I wrote one of them, on top of my blist type), each with their pros and cons.

I concur. People who want to maintain sorted collections (periodically adding and deleting items) are far better-off using your blist, a binary tree, or an in-memory sqlite database. Otherwise, we will have baited them into a non-scalable O(n) solution. Unfortunately, when people see the word "bisect", they will presume they've got O(log n) code. We've documented the issue with bisect.insort(), but the power of suggestion is very strong. Raymond

On Thu, Feb 9, 2012 at 12:34 PM, Raymond Hettinger < raymond.hettinger@gmail.com> wrote:

Bisect in particular had way too much focus on the algorithm. The API is awkward and error-prone for many common use cases.

I've tried to remedy that through documenting how to implement the common use cases: http://docs.python.org/py3k/library/bisect.html#searching-sorted-lists

The issue is that the current API focuses on "insertion points" rather than on finding values. Unfortunately, this API is very old, so the only way to fix it is to introduce a new class.

If we introduced class around a sorted sequence, then we could make an reasonable API that corresponds to what people usually want to do with sorted sequences.

Of course, that still leaves the issue with an O(n) insort. As Daniel pointed-out, a list is not the correct underlying data structure if you want to do periodic insertions and deletions.

Maybe you're overanalyzing the problem? It seems what you want would require a PEP and/or a reference implementation that is thoroughly tested as a 3rd party package before it warrants inclusion into the stdlib. In the mean time adding a key= option that echoes the API offered by list.sort() and sorted() is a no-brainer. -- --Guido van Rossum (python.org/~guido)

On Thu, Feb 9, 2012 at 1:51 PM, Terry Reedy wrote:

On Feb 9, 2012, at 9:50 AM, Daniel Stutzbach wrote:

...

A SortedList class that provides O(log n) insertions is useful from

time to time. There are several existing implementations available (I

...

...

wrote one of them, on top of my blist type), each with their pros and cons.

Are your blist leaves lists (or arrays) of some maximum size?

Yes. Each leaf has at most 128 elements. It's a compile-time constant. -- Daniel Stutzbach