While we're talking about annoyances
Michael Hoffman
cam.ac.uk at mh391.invalid
Sun Apr 29 22:08:30 EDT 2007
Alex Martelli wrote:
> 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.
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
More information about the Python-list
mailing list