While we're talking about annoyances

Alex Martelli aleax at mac.com
Mon Apr 30 03:50:24 CEST 2007

Arnaud Delobelle <arnodel at googlemail.com> wrote:
> > >>     decorated.sort()
> > def index(sequence):
> >      return sorted(range(len(sequence)), key=sequence.__getitem__)
> But really these two versions of rank are slower than the original one
> (as sorting a list is O(nlogn) whereas filling a table with
> precomputed values is O(n) ).

Wrong, because the original one also had a sort step, of course, so it
was also, inevitably, O(N log N) -- I've quoted the .sort step above.

> Anyway I would like to contribute my own index function:
> def index(seq):
>      return sum(sorted(map(list,enumerate(seq)), key=list.pop), [])
> It's short and has the advantage of being self-documenting, which will
> save Steven a lot of annoying typing I hope ;)  Who said Python
> couldn't rival with perl?

sum is for summing NUMBERS -- using it on lists is O(N squared).

So, this solution is asymptotically VERY slow, as well as obfuscated.


More information about the Python-list mailing list