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

[Guido van Rossum]

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 at gmail.com>wrote:

> Hi,
>
> 2012/2/8 Masklinn <masklinn at 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 at python.org
> http://mail.python.org/mailman/listinfo/python-ideas
>
>


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