[Python-Dev] decorate-sort-undecorate
Alex Martelli
aleaxit at yahoo.com
Thu Oct 16 04:20:24 EDT 2003
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
More information about the Python-Dev
mailing list