sorting many arrays from one...

[Jerzy Karczmarczuk]

Alex Martelli wrote:

> ... ABSOLUTELY forget the idea of passing a compare function to aux.sort!!!
> This would drag the sorting down to a HORRIBLE crawl.  COnsider (python
> 2.2.1, -O, on 1.4 GHz Athlon with DDR RAM to burn):

...
> >>> a=time.clock(); xx.sort(); b=time.clock(); print b-a
> 0.81

> ...
> >>> a=time.clock(); xx.sort(f); b=time.clock(); print b-a
> 10.97

> even for this super-simplified case where the sequence to sort is so
> clean and the comparison function does nothing more than delegate to
> the same cmp that would be used anyway, you pay well more than an
> order of magnitude for the privilege of passing a compare function
> to the sort method!!!

This was one of my principal griefs when I began to learn Python. I still
don't know why is it so costly. One may suppose that an interpreted user
function f which calls cmp may be the main reason, but xx.sort(cmp) is
also slow [in my rudimentary test about twice as fast as sort(f)].

Somebody cares about explaining this behaviour? Dynamic dispatching,
while sort() does not any dereferencing? Or what?

For people coming from the Functional Programming Realm such slowdown
of parameterized functionals is hard to accept...


> Don't do it.  Use D-S-U, as AMPLY explained in the searching and
> sorting chapter of the Python Cookbook 

I don't want to depreciate your helpful attitude addressed to a person
in need, nor say anything bad about something considered a "common idiom",
but the idea of Decorate-Sort-Undecorate, which begins by constructing
an additional list with fast-sortable keys is also something hard to
digest. The author of the original question had 300 000 items. I had
once five times more, and I found it a bit ridiculous to pollute the
memory with an ephemeric sequence just because there is something lousy
with parametrized sort (and possibly other H. O. functions?)
What do you think?


Jerzy Karczmarczuk
Caen, France