|
 |
Warp <war### [at] tag povrayorg> writes:
> The test was done in an Sun Ultra 5 (UltraSparc 333MHz, 128MB RAM). If
> someone wants to make the test with other systems, please be welcome. I'm
> interested (and I'm sure many other people are as well).
I've added heap sort to the mix.
- Heap sort: The other basic fast sorting algorithm. IIRC it should
theoretically be better than quick sort on the almost-reverse ordered
array. Against the randomized quick sort, however, it doesn't seem to
have that behaviour. Requiring only one #macro it's almost as concise
as quick sort and faster on short arrays.
Note that the array goes from 1 to size rather than 0 to size-1 and
stomps on the location just *before* the start of the array; that
simplifies the math required. The same algorithm ajusting for 0 to
size-1 ran more than 20% slower in all cases.
The tests were done on (one cpu of) an Origin 2000 (32 * MIPS R10000
195 MHz, 7808MB RAM).
* An array containing random numbers:
----------------------------------
Sorting 16 items:
~Secs Ticks Speed factor
Quick sort: 0 50000 1.00
Hybrid sort: 0 30000 0.60
Merge sort: 0 50000 1.00
NR-Merge sort: 0 40000 0.80
Heap sort: 0 20000 0.40
Insertion sort: 0 30000 0.60
Sorting 80 items:
~Secs Ticks Speed factor
Quick sort: 0 250000 1.00
Hybrid sort: 0 160000 0.64
Merge sort: 0 340000 1.36
NR-Merge sort: 0 260000 1.04
Heap sort: 0 190000 0.76
Insertion sort: 1 550000 2.20
Sorting 400 items:
~Secs Ticks Speed factor
Quick sort: 1 1350000 1.00
Hybrid sort: 1 1010000 0.75
Merge sort: 2 2110000 1.56
NR-Merge sort: 2 1530000 1.13
Heap sort: 1 1270000 0.94
Insertion sort: 14 14160000 10.49
Sorting 2000 items:
~Secs Ticks Speed factor
Quick sort: 8 7560000 1.00
Hybrid sort: 6 5920000 0.78
Merge sort: 12 12450000 1.65
NR-Merge sort: 9 9180000 1.21
Heap sort: 8 7760000 1.03
Insertion sort: 336 335770000 44.41
* An array containing almost ordered numbers:
------------------------------------------
(186 values out of 2001 random, rest consecutive)
Sorting 16 items:
~Secs Ticks Speed factor
Quick sort: 0 40000 1.00
Hybrid sort: 0 20000 0.50
Merge sort: 0 50000 1.25
NR-Merge sort: 0 40000 1.00
Heap sort: 0 30000 0.75
Insertion sort: 0 30000 0.75
Sorting 80 items:
~Secs Ticks Speed factor
Quick sort: 0 230000 1.00
Hybrid sort: 0 160000 0.70
Merge sort: 0 340000 1.48
NR-Merge sort: 0 240000 1.04
Heap sort: 0 210000 0.91
Insertion sort: 0 140000 0.61
Sorting 400 items:
~Secs Ticks Speed factor
Quick sort: 1 1300000 1.00
Hybrid sort: 1 990000 0.76
Merge sort: 2 2070000 1.59
NR-Merge sort: 1 1480000 1.14
Heap sort: 1 1360000 1.05
Insertion sort: 2 2000000 1.54
Sorting 2000 items:
~Secs Ticks Speed factor
Quick sort: 7 7030000 1.00
Hybrid sort: 5 5360000 0.76
Merge sort: 11 11490000 1.63
NR-Merge sort: 8 8170000 1.16
Heap sort: 10 10100000 1.44
Insertion sort: 41 40520000 5.76
* An array containing almost reverse-ordered numbers:
--------------------------------------------------
(202 values out of 2001 random, rest reversely consecutive)
Sorting 16 items:
~Secs Ticks Speed factor
Quick sort: 0 40000 1.00
Hybrid sort: 0 20000 0.50
Merge sort: 0 50000 1.25
NR-Merge sort: 0 40000 1.00
Heap sort: 0 30000 0.75
Insertion sort: 0 40000 1.00
Sorting 80 items:
~Secs Ticks Speed factor
Quick sort: 0 240000 1.00
Hybrid sort: 0 160000 0.67
Merge sort: 0 320000 1.33
NR-Merge sort: 0 240000 1.00
Heap sort: 0 180000 0.75
Insertion sort: 1 960000 4.00
Sorting 400 items:
~Secs Ticks Speed factor
Quick sort: 1 1320000 1.00
Hybrid sort: 1 930000 0.70
Merge sort: 2 1910000 1.45
NR-Merge sort: 1 1380000 1.05
Heap sort: 1 1200000 0.91
Insertion sort: 24 23870000 18.08
Sorting 2000 items:
~Secs Ticks Speed factor
Quick sort: 7 7350000 1.00
Hybrid sort: 6 5620000 0.76
Merge sort: 12 11530000 1.57
NR-Merge sort: 8 7920000 1.08
Heap sort: 8 7550000 1.03
Insertion sort: 600 599840000 81.61
======================================================================
The new/modified code:
---------------------
// ---------
// Heap Sort
// ---------
#macro HeapSort(Array, FirstInd, LastInd)
#declare Array[FirstInd-1] = 9999999999999999999;
#local I = FirstInd;
#while (I <= LastInd)
#local X = Array[I];
#local J = I;
#while (Array[div(J,2)] <= X)
#declare Array[J] = Array[div(J,2)];
#local J = div(J,2);
#end
#declare Array[J] = X;
#local I = I + 1;
#end
#local End = LastInd;
#while (FirstInd < End)
#local X = Array[End];
#declare Array[End] = Array[FirstInd];
#local I = FirstInd; #local J = I*2;
#while (J < End)
#if (J+1 < End & Array[J] < Array[J+1])
#local J = J + 1;
#end
#if (X <= Array[J])
#declare Array[I] = Array[J];
#local I = J; #local J = I*2;
#else
#local J = End;
#end
#end
#declare Array[I] = X;
#local End = End - 1;
#end
#end
//========================================================================
// Test sort algorithm speeds
//========================================================================
#version Unofficial MegaPov 0.6;
// Have to tweak the size for the heap
#declare ArraySize = 2001;
// original code...
// alternate array copy to setup the heap
#macro CopyHeap(Dest, Src, FirstInd, LastInd)
#while(FirstInd <= LastInd)
#declare Dest[FirstInd+1] = Src[FirstInd];
#local FirstInd = FirstInd+1;
#end
#end
// original code...
#macro MakeTest()
// original code...
CopyHeap(ArrayCopy, TestArray, 0, Amnt-1)
#local STime = start_chrono;
#local Ticks = tick_count;
HeapSort(ArrayCopy, 1, Amnt)
#local Ticks = tick_count-Ticks;
#local ETime = current_chrono;
CheckArray(ArrayCopy, 1, Amnt, "Heap sort")
#debug concat(" Heap sort: ", str(ETime, 6, 0), " ", str(Ticks,10,0), " ",
str(Ticks/QSTicks,0,2), "\n")
// original code...
#end
// etc, etc...
--
roh### [at] peacecom
Post a reply to this message
|
|
