Re: [leafnode-list] 2.0b8_ma3 leafnode very slow

[Matthias Andree <ma@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>]

Matthias Andree <ma@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> writes:

> Is that "check for ascending order, if violated, call qsort"? If so,
> natural mergesort will implicitly keep track of that.
> 
> I think I'll implement that with qsort-like arguments, unless I find it
> on the web under BSD/MIT license.

Ok, I found a good mergesort in my FreeBSD 4.3-STABLE and ripped it off,
and filed a PR to fix FreeBSD 4.3 type signedness clashes in merge.c by
the way :^)

I wrote sort.c which hooks a counter into the compare function and
found:

for my presorted groupinfo (23843 entries):

quicksort: 0,11 s 169220 comparisons
mergesort: 0,02 s  23842 comparisons

for my de.rec.fotografie xover (5861 entries):

quicksort: 62172 comparisons unsorted, 35603 sorted
mergesort: 41508 comparisons unsorted,  5860 sorted

(I cannot get the CPU times for the last case, the rlimit timevals don't
differ.)

My sort.c currently calls mergesort and falls back to qsort should
mergesort fail (for ENOMEM).

Should be faster now :-)

-- 
Matthias Andree

-- 
leafnode-list@xxxxxxxxxxxxxxxxxxxxxxxxxxxx -- mailing list for leafnode
To unsubscribe, send mail with "unsubscribe" in the subject to the list