[Python-Dev] decorate-sort-undecorate

[Alex Martelli]

On Wednesday 15 October 2003 09:48 pm, Ian Bicking wrote:
> On Wednesday, October 15, 2003, at 12:35 PM, Barry Warsaw wrote:
> > While we're hacking on [].sort(), how horrible would it be if we
> > modified it to return self instead of None?  I don't mind the
> > sort-in-place behavior, but it's just so inconvenient that it doesn't
> > return anything useful.  I know it would be better if it returned a new
> > list, but practicality beats purity. <wink>
>
> When doing DSU sorting, the in-place sorting isn't really a performance
> win, is it?  You already have to allocate and populate an entire
> alternate list with the sort keys, though I suppose you could have
> those mini key structs point to the original list.

I thought the idea being implemented avoided making a new list --
i.e., that the idea being implemented is the equivalent of:

# decorate
for i, item in enumerate(thelist):
    thelist[i] = CleverWrapper((key(item), item))

# sort (with the new stability guarantee)
thelist.sort()

# undecorate
for i, item in enumerate(thelist):
    thelist[i] = item[1]

where (the equivalent of):

class CleverWrapper(tuple):
    def __cmp__(self, other): return cmp(self[0], other[0])

so, there is no allocation of another list -- just (twice) a repopulation
of the existing one.  How _important_ that is to performance, I dunno,
but wanted to double-check on my understanding of this anyway.


> Okay, really I'm just hoping for [x for x in l sortby key(x)], if not
> now then someday -- if only there was a decent way of expressing that
> without a keyword... [...in l : key(x)] is the only thing I can think
> of that would be syntactically possible (without introducing a new
> keyword, new punctuation, or reusing a wholely inappropriate existing
> keyword).  Or ";" instead of ":", but neither is very good.

Peter Norvig's just-proposed "accumulator" syntax looks quite good to
me from this point of view, and superior to the "generator comprehension"
alternative (though I think the semantics might perhaps be tweaked, but I'm
thinking of writing a separate message about that).

IOW, if we can accept that [ ... ] is not necessarily a list, then 
    [SortedBy: key(x) for x in L] 
would look good to me.  (in this case this WOULD be a list, but I think
the notation pays for itself only if we can use it more generally).  Or
maybe SortedBy[key(x) for x in L] -- extending indexing syntax 
    <expression> [ ... ]
to mean something different if the ... includes a 'for', just like we
already extended list display syntax [ ... ] to mean list comprehension
in just such a case.


Alex