|
 |
There was a thread about sorting some days ago in this groups, so I decided
to explore a bit array sorting in POV-Ray. This is the result of the
research.
The idea was to test different sorting algorithms made with POV-script
(as #macros) and see how fast they are with different amount of items.
I made a pov-scene which makes some tests and outputs information about
them in the #debug channel.
Some comments about the sorting algorithms:
- Quick sort: Or actually randomized quick sort. The basic fast sorting
algorithm. It performs very well with all the input types (due the the
"randomized" part). Fast, simple and reliable. Not the best for sorting
very short arrays, though. A positive thing is that it only requires one
#macro.
- Hybrid sort: A hybrid between quick sort and insertion sort. It applies
quick sort down to sub-blocks of 10 items at max, and then it sorts this
semi-sorted array by calling the insertion sort.
This "trick" takes advantage of the fact that insertion sort is faster
with very small arrays than quick sort, so it first makes small sub-blocks
(which are ordered with respect to each other) and then just calls the
insertion sort. Due to the insertion sort algorithm, it automatically
sorts each sub-block separately (and since the sub-blocks are very small,
10 items at max, it does it very fast).
As seen in the results, this algorithm is clearly the fastest one of all.
It requires three #macros, though.
- Merge sort: Regular recursive merge sort. It's surprisingly fast taking
into account that it uses an additional array and makes lots of "extra" copies
from one array to the other. It's, however, quite slower than quick sort.
Requires two #macros.
- NR-Merge sort: A non-recursive version of the merge sort algorithm. It
performs better than the recursive version, almost as fast as quick sort.
Another advantage over the recursive version is that it requires only
one #macro.
- Insertion sort: Added to the test more for comparison reasons than anything
else. Although it's one of the fastest O(n^2)-algorithms, it's still O(n^2),
which means that it's extremely slow with large arrays.
Because of the simplicity of the algorithm, it's the fastest with very
small arrays (some tens of items) and a bit bigger arrays which are almost
sorted. This fact is used in the hybrid sort described above.
However, as the size of the array grows, the execution time grows rapidly
until it's just too slow (as seen in the test, it's about 44 times slower
than quick sort with an array of 2000 random numbers).
- Bubble sort: I originally tested this horrible algorithm, but it was
so slow that I had to drop it out (sorting an array of 2000 items took
about 15 minutes).
If someone wants to test it, the test code is commented in the MakeTest()
macro.
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).
The table contains three values for each algorith:
- The first value is a rough estimate of the amount of seconds it took for
the algorithm to sort the array. Since it's resolution is 1 second, it's not
very accurate with small arrays.
- The second value is the number of ticks that it took. This is a bit more
accurate, but still not very accurate with small arrays (it seems that in
this system the tick resolution is 10000 ticks, with about 500000 being one
second, so the resolution is about 1/50 seconds). These resolutions probably
depend a lot in the system used.
- The third value is a speed factor with respect to quick sort (hence quick
sort itself has this value always set to 1.00). A value of eg. "2.00" means
that the algorithm took twice the time it took for quick sort. Again, with
small arrays the value is less accurate.
The results (as output by the test scene to the #debug channel):
* An array containing random numbers:
----------------------------------
Sorting 16 items:
~Secs Ticks Speed factor
Quick sort: 0 30000 1.00
Hybrid sort: 0 20000 0.67
Merge sort: 0 40000 1.33
NR-Merge sort: 0 40000 1.33
Insertion sort: 0 30000 1.00
Sorting 80 items:
~Secs Ticks Speed factor
Quick sort: 0 200000 1.00
Hybrid sort: 0 140000 0.70
Merge sort: 0 280000 1.40
NR-Merge sort: 0 210000 1.05
Insertion sort: 0 470000 2.35
Sorting 400 items:
~Secs Ticks Speed factor
Quick sort: 1 1100000 1.00
Hybrid sort: 1 840000 0.76
Merge sort: 2 1710000 1.55
NR-Merge sort: 1 1260000 1.15
Insertion sort: 12 11680000 10.62
Sorting 2000 items:
~Secs Ticks Speed factor
Quick sort: 6 6220000 1.00
Hybrid sort: 5 4880000 0.78
Merge sort: 10 10210000 1.64
NR-Merge sort: 7 7270000 1.17
Insertion sort: 277 277450000 44.61
* An array containing almost ordered numbers:
------------------------------------------
(186 values out of 2000 random, rest consecutive)
Sorting 16 items:
~Secs Ticks Speed factor
Quick sort: 0 30000 1.00
Hybrid sort: 0 20000 0.67
Merge sort: 0 40000 1.33
NR-Merge sort: 0 30000 1.00
Insertion sort: 0 10000 0.33
Sorting 80 items:
~Secs Ticks Speed factor
Quick sort: 0 180000 1.00
Hybrid sort: 0 130000 0.72
Merge sort: 0 280000 1.56
NR-Merge sort: 0 200000 1.11
Insertion sort: 0 120000 0.67
Sorting 400 items:
~Secs Ticks Speed factor
Quick sort: 1 1060000 1.00
Hybrid sort: 1 770000 0.73
Merge sort: 2 1690000 1.59
NR-Merge sort: 1 1210000 1.14
Insertion sort: 2 1670000 1.58
Sorting 2000 items:
~Secs Ticks Speed factor
Quick sort: 6 5980000 1.00
Hybrid sort: 4 4470000 0.75
Merge sort: 9 9440000 1.58
NR-Merge sort: 7 6510000 1.09
Insertion sort: 33 33360000 5.58
* An array containing almost reverse-ordered numbers:
--------------------------------------------------
(202 values out of 2000 random, rest reversely consecutive)
Sorting 16 items:
~Secs Ticks Speed factor
Quick sort: 0 30000 1.00
Hybrid sort: 0 20000 0.67
Merge sort: 0 40000 1.33
NR-Merge sort: 0 40000 1.33
Insertion sort: 0 30000 1.00
Sorting 80 items:
~Secs Ticks Speed factor
Quick sort: 0 190000 1.00
Hybrid sort: 0 120000 0.63
Merge sort: 0 260000 1.37
NR-Merge sort: 0 190000 1.00
Insertion sort: 1 820000 4.32
Sorting 400 items:
~Secs Ticks Speed factor
Quick sort: 1 1060000 1.00
Hybrid sort: 1 760000 0.72
Merge sort: 2 1570000 1.48
NR-Merge sort: 1 1090000 1.03
Insertion sort: 20 19780000 18.66
Sorting 2000 items:
~Secs Ticks Speed factor
Quick sort: 6 5900000 1.00
Hybrid sort: 4 4230000 0.72
Merge sort: 9 9450000 1.60
NR-Merge sort: 7 6520000 1.11
Insertion sort: 512 512190000 86.81
----------------------------------------------------------------------------
The sorting macros and the test scene:
---------8<---------8<---------8<---------8<---------8<---------8<----------
// -----------
// Bubble sort
// -----------
#macro BubbleSort(Array, FirstInd, LastInd)
#local Sorted = false;
#while(!Sorted)
#local Sorted = true;
#local Ind = FirstInd;
#while(Ind < LastInd)
#local NextInd = Ind+1;
#if(Array[Ind] > Array[NextInd])
#local Tmp = Array[Ind];
#declare Array[Ind] = Array[NextInd];
#declare Array[NextInd] = Tmp;
#local Sorted = false;
#end
#declare Ind = NextInd;
#end
#end
#end
// --------------
// Insertion sort
// --------------
#macro InsertionSort(Array, FirstInd, LastInd)
#local Ind1 = FirstInd+1;
#while(Ind1 <= LastInd)
#local Ind2 = Ind1;
#while(Ind2>0)
#local NextInd2 = Ind2-1;
#if(Array[Ind2] < Array[NextInd2])
#local Tmp = Array[Ind2];
#declare Array[Ind2] = Array[NextInd2];
#declare Array[NextInd2] = Tmp;
#local Ind2 = NextInd2;
#else
#local Ind2 = 0;
#end
#end
#local Ind1 = Ind1+1;
#end
#end
// ----------
// Merge sort
// ----------
#macro MergeSort(Array, FirstInd, LastInd)
#local HelpArray = array[LastInd+1]
MergeSortStep(Array, HelpArray, FirstInd, LastInd)
#end
#macro MergeSortStep(Array, HelpArray, FirstInd, LastInd)
#if(FirstInd < LastInd)
#local Mid = int((FirstInd+LastInd)/2);
MergeSortStep(Array, HelpArray, FirstInd, Mid)
MergeSortStep(Array, HelpArray, Mid+1, LastInd)
#local Ind = FirstInd;
#while(Ind <= LastInd)
#declare HelpArray[Ind] = Array[Ind];
#local Ind = Ind+1;
#end
#local I = FirstInd; #local J = FirstInd; #local K = Mid+1;
#while(J <= Mid & K <= LastInd)
#if(HelpArray[J] <= HelpArray[K])
#declare Array[I] = HelpArray[J];
#local J = J+1;
#else
#declare Array[I] = HelpArray[K];
#local K = K+1;
#end
#local I = I+1;
#end
#local K = (J>Mid ? 0 : Mid-LastInd);
#local J = I;
#while(J <= LastInd)
#declare Array[J] = HelpArray[J+K];
#local J = J+1;
#end
#end
#end
// -------------
// NR-Merge sort
// -------------
#macro NRMergeSort(Array, FirstInd, LastInd)
#local HelpArray = array[LastInd+1]
#local OrigToHlp = true;
#local Step = 2;
#local Size = (LastInd-FirstInd+1)*2;
#while(Step < Size)
#local FInd = FirstInd;
#local LInd = FInd+Step-1;
#local Mid = int((FInd+LInd)/2);
#while(Mid < LastInd)
#if(LInd > LastInd) #local LInd = LastInd; #end
#local I = FInd; #local J = FInd; #local K = Mid+1;
#if(OrigToHlp)
#while(J <= Mid & K <= LInd)
#if(Array[J] <= Array[K])
#declare HelpArray[I] = Array[J];
#local J = J+1;
#else
#declare HelpArray[I] = Array[K];
#local K = K+1;
#end
#local I = I+1;
#end
#else
#while(J <= Mid & K <= LInd)
#if(HelpArray[J] <= HelpArray[K])
#declare Array[I] = HelpArray[J];
#local J = J+1;
#else
#declare Array[I] = HelpArray[K];
#local K = K+1;
#end
#local I = I+1;
#end
#end
#local K = (J>Mid ? 0 : Mid-LInd);
#local J = I;
#if(OrigToHlp)
#while(J <= LInd)
#declare HelpArray[J] = Array[J+K];
#local J = J+1;
#end
#else
#while(J <= LInd)
#declare Array[J] = HelpArray[J+K];
#local J = J+1;
#end
#end
#local FInd = FInd+Step;
#local LInd = FInd+Step-1;
#local Mid = int((FInd+LInd)/2);
#end
#if(Mid >= LastInd)
#if(OrigToHlp)
#while(FInd <= LastInd)
#declare HelpArray[FInd] = Array[FInd];
#local FInd = FInd+1;
#end
#else
#while(FInd <= LastInd)
#declare Array[FInd] = HelpArray[FInd];
#local FInd = FInd+1;
#end
#end
#end
#local Step = Step*2;
#local OrigToHlp = (OrigToHlp ? false : true);
#end
#if(!OrigToHlp)
#while(FirstInd <= LastInd)
#declare Array[FirstInd] = HelpArray[FirstInd];
#local FirstInd = FirstInd+1;
#end
#end
#end
// ----------
// Quick sort
// ----------
#declare QuickSortSeed = seed(0);
#macro QuickSort(Array, FirstInd, LastInd)
#while(FirstInd < LastInd)
#local RInd = FirstInd+rand(QuickSortSeed)*(LastInd-FirstInd);
#local Tmp = Array[FirstInd];
#declare Array[FirstInd] = Array[RInd];
#declare Array[RInd] = Tmp;
#local X = Array[FirstInd];
#local I = FirstInd-1; #local J = LastInd+1; #local Mid = -1;
#while(Mid < 0)
#local J = J-1; #while(Array[J] > X) #local J = J-1; #end
#local I = I+1; #while(Array[I] < X) #local I = I+1; #end
#if(I<J)
#local Tmp = Array[I];
#declare Array[I] = Array[J];
#declare Array[J] = Tmp;
#else
#local Mid = J;
#end
#end
QuickSort(Array, FirstInd, Mid)
#local FirstInd = Mid+1;
#end
#end
// -----------------
// Hybrid quick sort
// -----------------
#macro HybridQuickSort(Array, FirstInd, LastInd)
HybridQuickSortStep(Array, FirstInd, LastInd)
InsertionSort(Array, FirstInd, LastInd)
#end
#macro HybridQuickSortStep(Array, FirstInd, LastInd)
#local FInd = FirstInd;
#while(FInd < LastInd-10)
#local RInd = FInd+rand(QuickSortSeed)*(LastInd-FInd);
#local Tmp = Array[FInd];
#declare Array[FInd] = Array[RInd];
#declare Array[RInd] = Tmp;
#local X = Array[FInd];
#local I = FInd-1; #local J = LastInd+1; #local Mid = -1;
#while(Mid < 0)
#local J = J-1; #while(Array[J] > X) #local J = J-1; #end
#local I = I+1; #while(Array[I] < X) #local I = I+1; #end
#if(I<J)
#local Tmp = Array[I];
#declare Array[I] = Array[J];
#declare Array[J] = Tmp;
#else
#local Mid = J;
#end
#end
HybridQuickSortStep(Array, FInd, Mid)
#local FInd = Mid+1;
#end
#end
//========================================================================
// Test sort algorithm speeds
//========================================================================
#version Unofficial MegaPov 0.6;
#declare ArraySize = 2000;
#declare TestArray = array[ArraySize]
#declare ArrayCopy = array[ArraySize]
#macro CopyArray(Dest, Src, FirstInd, LastInd)
#while(FirstInd <= LastInd)
#declare Dest[FirstInd] = Src[FirstInd];
#local FirstInd = FirstInd+1;
#end
#end
#macro CheckArray(Array, FirstInd, LastInd, Name)
#local Ind = FirstInd;
#while(Ind < LastInd)
#if(Array[Ind] > Array[Ind+1])
#debug concat("Ooops! ", Name, " doesn't work...\n")
#error ""
#end
#local Ind=Ind+1;
#end
#end
#macro MakeTest()
#local Amnt = 16;
#while(Amnt <= ArraySize)
#debug concat("\nSorting ", str(Amnt,0,0), " items:\n")
#debug " ~Secs Ticks Speed factor\n"
CopyArray(ArrayCopy, TestArray, 0, Amnt-1)
#local STime = start_chrono;
#local QSTicks = tick_count;
QuickSort(ArrayCopy, 0, Amnt-1)
#local QSTicks = tick_count-QSTicks;
#local ETime = current_chrono;
CheckArray(ArrayCopy, 0, Amnt-1, "Quick sort")
#debug concat(" Quick sort: ", str(ETime, 6, 0), " ", str(QSTicks,10,0), "
1.00\n")
CopyArray(ArrayCopy, TestArray, 0, Amnt-1)
#local STime = start_chrono;
#local Ticks = tick_count;
HybridQuickSort(ArrayCopy, 0, Amnt-1)
#local Ticks = tick_count-Ticks;
#local ETime = current_chrono;
CheckArray(ArrayCopy, 0, Amnt-1, "Hybrid quick sort")
#debug concat(" Hybrid sort: ", str(ETime, 6, 0), " ", str(Ticks,10,0), " ",
str(Ticks/QSTicks,0,2), "\n")
CopyArray(ArrayCopy, TestArray, 0, Amnt-1)
#local STime = start_chrono;
#local Ticks = tick_count;
MergeSort(ArrayCopy, 0, Amnt-1)
#local Ticks = tick_count-Ticks;
#local ETime = current_chrono;
CheckArray(ArrayCopy, 0, Amnt-1, "Merge sort")
#debug concat(" Merge sort: ", str(ETime, 6, 0), " ", str(Ticks,10,0), " ",
str(Ticks/QSTicks,0,2), "\n")
CopyArray(ArrayCopy, TestArray, 0, Amnt-1)
#local STime = start_chrono;
#local Ticks = tick_count;
NRMergeSort(ArrayCopy, 0, Amnt-1)
#local Ticks = tick_count-Ticks;
#local ETime = current_chrono;
CheckArray(ArrayCopy, 0, Amnt-1, "NR-Merge sort")
#debug concat(" NR-Merge sort: ", str(ETime, 6, 0), " ", str(Ticks,10,0), " ",
str(Ticks/QSTicks,0,2), "\n")
CopyArray(ArrayCopy, TestArray, 0, Amnt-1)
#local STime = start_chrono;
#local Ticks = tick_count;
InsertionSort(ArrayCopy, 0, Amnt-1)
#local Ticks = tick_count-Ticks;
#local ETime = current_chrono;
CheckArray(ArrayCopy, 0, Amnt-1, "Insertion sort")
#debug concat(" Insertion sort: ", str(ETime, 6, 0), " ", str(Ticks,10,0), " ",
str(Ticks/QSTicks,0,2), "\n")
/*
CopyArray(ArrayCopy, TestArray, 0, Amnt-1)
#local STime = start_chrono;
#local Ticks = tick_count;
BubbleSort(ArrayCopy, 0, Amnt-1)
#local Ticks = tick_count-Ticks;
#local ETime = current_chrono;
CheckArray(ArrayCopy, 0, Amnt-1, "Bubble sort")
#debug concat(" Bubble sort: ", str(ETime, 6, 0), " ", str(Ticks,10,0), " ",
str(Ticks/QSTicks,0,2), "\n")
*/
#local Amnt = Amnt*5;
#end
#end
#debug "* An array containing random numbers:\n"
#debug " ----------------------------------\n"
#declare R=seed(0);
#declare Ind=0;
#while(Ind<ArraySize)
#declare TestArray[Ind] = rand(R)*1000;
#declare Ind=Ind+1;
#end
MakeTest()
#debug "\n* An array containing almost ordered numbers:\n"
#debug " ------------------------------------------\n"
#declare Cnt=0;
#declare Ind=0;
#while(Ind<ArraySize)
#if(rand(R) < .1)
#declare TestArray[Ind] = rand(R)*1000;
#declare Cnt = Cnt+1;
#else
#declare TestArray[Ind] = Ind;
#end
#declare Ind=Ind+1;
#end
#debug concat("(",str(Cnt,0,0)," values out of ",str(ArraySize,0,0)," random, rest
consecutive)\n")
MakeTest()
#debug "\n* An array containing almost reverse-ordered numbers:\n"
#debug " --------------------------------------------------\n"
#declare Cnt=0;
#declare Ind=0;
#while(Ind<ArraySize)
#if(rand(R) < .1)
#declare TestArray[Ind] = rand(R)*1000;
#declare Cnt = Cnt+1;
#else
#declare TestArray[Ind] = ArraySize-Ind;
#end
#declare Ind=Ind+1;
#end
#debug concat("(",str(Cnt,0,0)," values out of ",str(ArraySize,0,0)," random, rest
reversely consecutive)\n")
MakeTest()
---------8<---------8<---------8<---------8<---------8<---------8<----------
--
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/
Post a reply to this message
|
|
povray