Mail Archives: djgpp-workers/1998/09/20/19:16:04
Dear DJ Delorie,
I have finished work on a new version of qsort that is substantially
better that the current version in our library. To show that this is
so, I append to this letter the results of two test runs. The first
shows the results of the current qsort, the second on the new version.
Each test run consists of two passes on the test program. Each pass
calls qsort 10 times to sort a different kind of sort target on each
call. On the first pass, each sort target consists of 20,000 items.
On the second pass, each sort target consists of 40,000 items.
As can be seen in the timing figures in the result printouts below,
our current version of qsort demonstrates quadratic timing behavior
on two of the sort targets. These sort targets are the last two in
the list. As you can see, the numbers of comparisons are virtually
quadrupled on targets that are double the size.
Similar runs are shown for the new version of qsort. As you can see,
the numbers of comparisons are much smaller for the targets at issue.
No such quadratic timing behavior is demonstrated.
On my Pentium 1:
Total sort time for the current version of qsort: 287.74 secs.
Total sort time for the new version of qsort: 3.35 secs.
Posted on ftp.delorie.com/incoming is tstqsort.zip that contains the
following files:
1. fqsort.c - the proposed new fat-pivot version of qsort.
2. lqsort.c - the current library version of qsort.
This version has hooks inserted to count swaps.
3. tstsort.c - a test driver for any sort function
that has a qsort-like calling protocol.
4. a header file, tsrtdefs.h, and five C-source files,
with extension .cin, that are included by tstsort.c.
5. a makefile
6. two result files identical to the stuff that is appended
to this letter - fqsort.out and lqsort.out.
7. a readme file that explains how the program works.
The makefile prepares two executables - fqsort.exe and lqsort.exe.
To duplicate the printouts appended below, execute each with the
following command lines:
lqsort N 20000 20000 40000 > lqsort.x
fqsort N 20000 20000 40000 > fqsort.x
Then, compare the new .x files with the corresponding .out files
from the zip archive. Except for the timing figures, the files
should compare exactly. Remember, lqsort (the library version)
will take substantially longer than fqsort to run.
K.B. Williams
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Generating Targets in [20000 (20000) 40000]
Sort Function is Standard Library Qsort
PlotTimer Option is FALSE
Items Comparisons Exchanges Code/Target I.D.
20000 315228 77650 (R) Random-Uniform
270865 0 (S) Already-Sorted
270866 10000 (V) Reverse-Sorted
900881 83589 (H) Reverse-Sorted-by-Halves
477073 19998 (F) First-Item-Out-of-Order
272199 6666 (T) Every-Third-Item-Inverted
270865 0 (Q) All-Items-Equal
281338 10629 (E) Every-Eighth-Item-Different
100050088 10195 (A) Alternating-Pairs
51016508 19662 (B) Bore-Sight-Simulation
Suite Stats: 20000 Items/Target, 58.131868 Seconds
154125911 Comparisons, 238389 Exchanges
Items Comparisons Exchanges Code/Target I.D.
40000 689461 169508 (R) Random-Uniform
581714 0 (S) Already-Sorted
581715 20000 (V) Reverse-Sorted
2043983 177877 (H) Reverse-Sorted-by-Halves
1034071 39998 (F) First-Item-Out-of-Order
584387 13333 (T) Every-Third-Item-Inverted
581714 0 (Q) All-Items-Equal
603311 22460 (E) Every-Eighth-Item-Different
400120590 20398 (A) Alternating-Pairs
198488228 38612 (B) Bore-Sight-Simulation
Suite Stats: 40000 Items/Target, 229.505495 Seconds
605309174 Comparisons, 502186 Exchanges
Total Sort Time: 0 Hrs, 4 Mins, 47.74 Secs
========================================================================
Generating Targets in [20000 (20000) 40000]
Sort Function is Fat-Pivot Quicksort (Median Pivots)
PlotTimer Option is FALSE
Items Comparisons Exchanges Code/Target I.D.
20000 313077 81837 (R) Random-Uniform
240010 4094 (S) Already-Sorted
260621 29998 (V) Reverse-Sorted
271539 83970 (H) Reverse-Sorted-by-Halves
260620 19998 (F) First-Item-Out-of-Order
252503 30602 (T) Every-Third-Item-Inverted
20003 1 (Q) All-Items-Equal
64460 9927 (E) Every-Eighth-Item-Different
30005 5003 (A) Alternating-Pairs
26615 6082 (B) Bore-Sight-Simulation
Suite Stats: 20000 Items/Target, 1.043956 Seconds
1739453 Comparisons, 271512 Exchanges
Items Comparisons Exchanges Code/Target I.D.
40000 661261 173685 (R) Random-Uniform
520011 8190 (S) Already-Sorted
561233 59998 (V) Reverse-Sorted
585485 178978 (H) Reverse-Sorted-by-Halves
561232 39998 (F) First-Item-Out-of-Order
544413 53404 (T) Every-Third-Item-Inverted
40003 1 (Q) All-Items-Equal
134495 21056 (E) Every-Eighth-Item-Different
60005 10003 (A) Alternating-Pairs
53077 11971 (B) Bore-Sight-Simulation
Suite Stats: 40000 Items/Target, 2.197802 Seconds
3721215 Comparisons, 557284 Exchanges
Total Sort Time: 0 Hrs, 0 Mins, 3.35 Secs
- Raw text -