Surprising (for me) benchmark results...

[Daniel Berlin]

On Tue, 1 May 2001, Courageous wrote:

>
> >In Perl and Java, the builtin sort, and in C++ std::sort.  Why would
> >you expect this to be best in Python?
>
> Python uses "Sample Sort," a highly optimized form of quick sort
> that's very difficult to beat. Note well that some algorithms may
> share a primary complexity factor, but you can still shave off
> secondary complexity factors in order to double or even triple
> algorithm speed while maintaining the same primary complexity.
>
> For example O( logN) might be O ( logN + big-K ) or O ( logN / 3).
>
> Sample sort is in all likelihood what's being demonstrated here.
> Furthermore, virtually all the work of this program is actually occuring
> in native C. Which happens fairly frequently in Python, so the example
> stands, IMO.
Actually, the sort is probably not the bottleneck.
As the file gets larger, the bottleneck becomes disk time, not sort time.
In fact, in external sort programs (IE where you use a fixed amount of
main memory, no matter what the size of the input file), which is
the fastest way to sort once your file becomes bigger than main memory,
the time is completely dominated by disk read/write/seek (mainly seek) time.
Not at all by sort time.


 >
> > C//
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>