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.
Well, counting the index() function that is called in both cases, the original rank() had one sort, but my version has two sorts. -- Michael Hoffman -- http://mail.python.org/mailman/listinfo/python-list