[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: Jens Axel Søgaard <jensaxel@soegaard.net>*Subject*: Re: Wording of the rationale*From*: Jens Axel Søgaard <jensaxel@soegaard.net>*Date*: Tue, 07 Nov 2006 22:24:10 +0100*Cc*: srfi-95@srfi.schemers.org*Delivered-to*: srfi-95@srfi.schemers.org*In-reply-to*: <455080C2.2090103@soegaard.net>*References*: <455080C2.2090103@soegaard.net>*User-agent*: Thunderbird 1.5.0.7 (Windows/20060909)

Jens Axel Søgaard skrev: Quoting the rational of srfi-95:

* Four varieties of algorithms were provided (quick, heap, insert, merge) even though quick, heap, and insert sorts have no significant advantage over merge-sort.

Commenting:

Second: What does "no significant advantage" mean? I were of the impression, that the "hidden constants" of O(n log (n)) of vector-quick-sort were smaller than that of vector-merge-sort.

...

Also: Is merge-sort the fastest algorithm, if the elements are "almost sorted"?

I tried a few experiments, and discovered that heap-sort beats the other algorithms when the elements are in almost reverse order. (The most surprising about this, is that I didn't figured it out before running the test). That is: If you know something about the data to be sorted, you are in a position, where you *want* to choose between the various algorithms. /Jens Axel Søgaard A sorted, long vector: (vector 1 2 3 ... 1000000) with < ---------------------------------------------------------- vector-merge-sort! and vector-insert-sort! roughly the same time vector-heap-sort! *much* slower vector-merge-sort! cpu time: 62 real time: 63 gc time: 0 vector-insert-sort! cpu time: 62 real time: 63 gc time: 0 vector-heap-sort! cpu time: 2343 real time: 2359 gc time: 0 A reverse-sorted, long vector: (vector 10000 ... 3 2 1) with < ------------------------------------------------------------- vector-heap-sort! *very* fast vector-merge-sort! and vector-insert-sort! roughly the same time vector-merge-sort! cpu time: 2203 real time: 2219 gc time: 0 vector-insert-sort! cpu time: 2047 real time: 2046 gc time: 0 vector-heap-sort! cpu time: 16 real time: 16 gc time: 0 My test program and results follow: (require (lib "32.ss" "srfi")) ; interval : integer integer -> (list integer) ; (interval n m) => (list n n+1 ... m) (define (interval n m) (do ((i m (- i 1)) (xs '() (cons i xs))) ((< i n) xs))) ; copy the input vector, and time the sorting only (define (test orig-v sorter) (let (; copy v so we can sort the same vector several times (v (list->vector (vector->list orig-v)))) ; make sure the garbage of one test doesn't affect the next (collect-garbage) (collect-garbage) ; time the sorting only (time (sorter < v)))) 'SORTED-VECTOR-TEST (define n 1000000) (define v (list->vector (interval 1 n))) 'vector-merge-sort! (test v vector-merge-sort!) 'vector-insert-sort! (test v vector-insert-sort!) 'vector-heap-sort! (test v vector-heap-sort!) 'REVERSE-SORTED-VECTOR-TEST (define n 10000) (define v (list->vector (reverse! (interval 1 n)))) 'vector-merge-sort! (test v vector-merge-sort!) 'vector-insert-sort! (test v vector-insert-sort!) 'vector-heap-sort! (test v vector-heap-sort!) 'RANDOM-VECTOR-TEST (define n 10000) (define v (list->vector (map (lambda (n) (random 1000000)) (interval 1 n)))) 'vector-merge-sort! (test v vector-merge-sort!) 'vector-insert-sort! (test v vector-insert-sort!) 'vector-heap-sort! (test v vector-heap-sort!) The results were (a different run than the above): Welcome to DrScheme, version 359.100-svn6nov2006. Language: Pretty Big (includes MrEd and Advanced Student). SORTED-VECTOR-TEST vector-merge-sort! cpu time: 63 real time: 62 gc time: 0 vector-insert-sort! cpu time: 62 real time: 62 gc time: 0 vector-heap-sort! cpu time: 2359 real time: 2359 gc time: 0 REVERSE-SORTED-VECTOR-TEST vector-merge-sort! cpu time: 2110 real time: 2110 gc time: 0 vector-insert-sort! cpu time: 2000 real time: 2000 gc time: 0 vector-heap-sort! cpu time: 15 real time: 15 gc time: 0 RANDOM-VECTOR-TEST vector-merge-sort! cpu time: 16 real time: 16 gc time: 0 vector-insert-sort! cpu time: 1031 real time: 1062 gc time: 0 vector-heap-sort! cpu time: 31 real time: 31 gc time: 0

**References**:**Wording of the rationale***From:*Jens Axel Søgaard <jensaxel@soegaard.net>

- Prev by Date:
**Wording of the rationale** - Next by Date:
**Re: Wording of the rationale** - Previous by thread:
**Wording of the rationale** - Next by thread:
**Re: Wording of the rationale** - Index(es):