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).

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.

--Guido

On Wed, Feb 8, 2012 at 2:18 PM, Amaury Forgeot d'Arc <amauryfa@gmail.com> wrote:
Hi,

2012/2/8 Masklinn <masklinn@masklinn.net>
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

_______________________________________________
Python-ideas mailing list
Python-ideas@python.org
http://mail.python.org/mailman/listinfo/python-ideas




--
--Guido van Rossum (python.org/~guido)