On Apr 30, 2:50 am, [EMAIL PROTECTED] (Alex Martelli) wrote: > Arnaud Delobelle <[EMAIL PROTECTED]> 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.
I am fully aware of the meaning of O(...). Nevertheless (speed != asymptotic speed) and one sort is still better than two sorts IMHO. Moreover the second sort is redundant and less clear than a simple loop. > > 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. And it was also a JOKE. There were some clues: * I claimed that the function was self-documenting, even though it was obviously obfuscated (as you rightly pointed out). * It relies on a side effect of the 'key' function list.pop, which is very bad form. * It is indeed very slow (yes, sum() is not the best for lists) * I mentioned that Python could rival perl. I was meant to be a clumsy but 'concise' amalgam that would perform the task (although not efficiently) while being difficult to make sense of. -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
