Not so long I’ve new test results for sorting methods. Now I decided to get everything I can from Quick sort algorithm. I’ve searched for all fast implementations and try to reuse them for Flash. I’ve learnt that non-recursive method surely would be faster then recursive calls. So now we have several non-recursive implementations one of them run faster on PC another on Mac. Better check yourself and see what it faster for you.
[UPDATED]
I’ve add some code optimization tips. And it looks like we got some speed improvements. Specially in Non recursive methods.
[UPDATED 2]
More optimization tips. Added FlashSort algorithm that became the fastest in my tests.
Here is my test results for PC and Mac sorting 100K length array:
———— PC ————
- Qsort + Insertion Sort | 57 Ms.
- 3 Way Qsort + Insertion | 52 Ms.
- Non-recursive Qsort | 53 Ms.
- Optimized Non-recursive Qsort | 36 Ms.
- Non-recursive Qsort II | 43 Ms.
- FlashSort | 29 Ms.
- Built in Array Sort | 90 Ms.
———— Mac ————
- Qsort + Insertion Sort | 49 Ms.
- 3 Way Qsort + Insertion | 50 Ms.
- Non-recursive Qsort | 49 Ms.
- Optimized Non-recursive Qsort | 47 Ms.
- Non-recursive Qsort II | 58 Ms.
- FlashSort | 33 Ms.
- Built in Array Sort | 85 Ms.
Download Sorting Test Class
@katopz If u need fast sort of 3D Vectors I would recommend to use 2 Vectors as I wrote before. One containing your projected vertices coordinates (I suppose u use Utils3D.projectVectors) and another Vector.
Tested it quite often now and with all scales the Non-recursive Qsort II is about 10% faster than Optimized Non-recursive Qsort, in almost all cases:
(143714 times executed)
QSORT + INSERTION SORT 88
3 WAY QSORT 109
NON RECURSIVE QSORT 94
OPTIMISED NON RECURSIVE QSORT 84
NON RECURSIVE QSORT II 71
BUILT IN ARRAY.SORT 133
SORTING RESULTS
———————
QSORT + INSERTION SORT 56
3 WAY QSORT 86
NON RECURSIVE QSORT 56
OPTIMISED NON RECURSIVE QSORT 47
NON RECURSIVE QSORT II 47
BUILT IN ARRAY.SORT 106
Quad Core 2Ghz
SORTING RESULTS (100000K, PC)
———————
QSORT + INSERTION SORT 56
3 WAY QSORT 56
NON RECURSIVE QSORT 57
OPTIMISED NON RECURSIVE QSORT 51
NON RECURSIVE QSORT II 50
BUILT IN ARRAY.SORT 116
LINUX (CORE 2 DUO)
———————
QSORT + INSERTION SORT 115
3 WAY QSORT 125
NON RECURSIVE QSORT 89
OPTIMISED NON RECURSIVE QSORT 78
NON RECURSIVE QSORT II 107
BUILT IN ARRAY.SORT 167
SORTING RESULTS (MAC BOOK PRO 2.2 Ghz INTEL CORE 2 DUO)
———————
QSORT + INSERTION SORT 68
3 WAY QSORT 93
NON RECURSIVE QSORT 59
OPTIMISED NON RECURSIVE QSORT 58
NON RECURSIVE QSORT II 77
BUILT IN ARRAY.SORT 104
PC 2.5 GHz, Quadcore
QSORT + INSERTION SORT 38
3 WAY QSORT 42
NON RECURSIVE QSORT 33
OPTIMISED NON RECURSIVE QSORT 35
NON RECURSIVE QSORT II 36
BUILT IN ARRAY.SORT 77
—————
Just wondering how FlashSort would do in flash ?
Interesting result, so far I’ve though it’s no use replacing the native Array.sort
FlashSort: http://www.neubert.net/FSOIntro.html
Hi again
I see you’re using Vectors for testing the different sorts, and Array for built-in method, is that the main reason for the built-in method being slower ? – and how would the built-in Vector.sort do in this test ?
@piXelero I decided to find better solution when I was in need) I was experimenting with flash 3d capabilities and need fast sort for z-poses of triangles. Later I tried to learn more and here is the result. Why I am using Vector: this is because using array for this methods is slow and array built in sort method is faster. But there is no built in sort method for Vector! You can only specify compare function and it runs very slow. So this is the answer – you got your own sorting methods for Vector arrays. I will update this post with more speedy version today (some optimization tips in code)
as far as I understand Flashsort is for Integer vectors. I dont think it is very useful. Better to have fast solution for Numbers and if you change it to integers it surely will be faster.
SORTING RESULTS
———————
QSORT + INSERTION SORT 78
3 WAY QSORT 51
NON RECURSIVE QSORT 75
OPTIMISED NON RECURSIVE QSORT 49
NON RECURSIVE QSORT II 44
BUILT IN ARRAY.SORT 87
—————————————-
btw, test from code that you provide is…
—————————————-
qsort+insert: 238
3way qsort: 310
non recursive qsort: 190
opt non recursive qsort: 154
non recursive qsort2: 112
array.sort: 86
—————————————-
weird eh?
@katopz that’s really strange… I’ve re-uploaded it again. Please check it again… Also make sure you don’t run it in debug mode.
qsort+insert:65
3way qsort:79
non recursive qsort:51
opt non recursive qsort:58
non recursive qsort2:50
array.sort:90
————————
without debug mode
@katopz thats better
but you results slower then mine…
~140.000 times
SORTING RESULTS
———————
QSORT + INSERTION SORT 84
3 WAY QSORT 105
NON RECURSIVE QSORT 72
OPTIMISED NON RECURSIVE QSORT 63
NON RECURSIVE QSORT II 66
BUILT IN ARRAY.SORT 129
About speed testing: Algorithms show some dynamics: Some are faster on small amount of data, others with big amounts: Furthermore: You should put the “player version” in the text field so its easy to find out what’s been testet.
I once made for as2 a good statistic approach for this kind of executions: You have to test your approach vor various kind of amounts: I used to test:
per version:
data null – 50% of tries
data 1 – 47% of tries
data 100 – 2% of tries
data 100000 – 1% of tries
(the amount of tries should vary to the state where null shows some result while 100000 doesn’t take too much time)
and each of the versions in mixed order: so any overhead or position problem is eliminated. Every level i compared and got the results.
SORTING RESULTS
———————
QSORT + INSERTION SORT: 33
3 WAY QSORT: 36
NON RECURSIVE QSORT:29
OPTIMISED NON RECURSIVE QSORT:25
NON RECURSIVE QSORT II:30
BUILT IN ARRAY.SORT:73
SORTING RESULTS (LINUX 2.6.28-11-GENERIC – LNX 10,0,22,87)
——————————————————–
QSORT + INSERTION SORT 101
3 WAY QSORT + INSERTION 86
NON RECURSIVE QSORT 67
OPTIMISED NON RECURSIVE QSORT 64
NON RECURSIVE QSORT II 80
FLASH SORT 47
BUILT IN ARRAY.SORT 151
SORTING RESULTS (WINDOWS XP – WIN 10,0,22,87)
——————————————————–
QSORT + INSERTION SORT 58
3 WAY QSORT + INSERTION 71
NON RECURSIVE QSORT 56
OPTIMISED NON RECURSIVE QSORT 46
NON RECURSIVE QSORT II 50
FLASH SORT 22
BUILT IN ARRAY.SORT 105
SORTING RESULTS (WINDOWS XP – WIN 10,0,22,87)
——————————————————–
QSORT + INSERTION SORT 195
3 WAY QSORT + INSERTION 57
NON RECURSIVE QSORT 73
OPTIMISED NON RECURSIVE QSORT 31
NON RECURSIVE QSORT II 45
FLASH SORT 27
BUILT IN ARRAY.SORT 91
Dual Core 2.53 Ghz FSC Tablet PC T5010
SORTING RESULTS (MAC OS 10.5.7 – MAC 10,0,22,87)
——————————————————–
QSORT + INSERTION SORT 55
3 WAY QSORT + INSERTION 54
NON RECURSIVE QSORT 50
OPTIMISED NON RECURSIVE QSORT 44
NON RECURSIVE QSORT II 63
FLASH SORT 38
BUILT IN ARRAY.SORT 90
I wonder: have you benchmarked that to see if the overhead of splitting out and using an indices vector is actually faster than using an Array with sortOn()? Presumably for a sort of 3D triangles you’re going to sort on the average Z depth of them, which you could store as a field and use sortOn(“averageZDepth”). I’d be really interested in any results you may have in this area. Thanks for the great article and demo app!
@Jackson I think that sorting in 3D application is heavy depends on your code structure. In my case I was computing and storing Z positions of triangles in one loop so I was able to store indices at the same time. As the result of the projecting loop I had 2 Vector Arrays that I can use for sorting routine. I think that it was mistake to write that this idea would work with Utils3D.projectVectors method because in this case you really have an overhead computations.
SORTING RESULTS (WINDOWS XP – WIN 10,0,32,18)
——————————————————–
QSORT + INSERTION SORT 1470
3 WAY QSORT + INSERTION 1127
NON RECURSIVE QSORT 1181
OPTIMISED NON RECURSIVE QSORT 804
NON RECURSIVE QSORT II 834
FLASH SORT 688
BUILT IN ARRAY.SORT 2592
SORTING RESULTS (WINDOWS VISTA – WIN 10,0,22,87)
——————————————————–
QSORT + INSERTION SORT 51
3 WAY QSORT + INSERTION 56
NON RECURSIVE QSORT 47
OPTIMISED NON RECURSIVE QSORT 34
NON RECURSIVE QSORT II 40
FLASH SORT 24
BUILT IN ARRAY.SORT 68
——————————————————–
The doc’s don’t confirm this; but I’ve heard it said that using uint instead of int is slightly quicker. Either way, it would allow for larger amounts of data to be sorted, as it’s limit is double that of int (2^32-1).
A thought worth mentioning anyway.
SORTING RESULTS (MAC OS 10.5.8 – MAC 10,0,42,34)
——————————————————–
QSORT + INSERTION SORT 58
3 WAY QSORT + INSERTION 61
NON RECURSIVE QSORT 54
OPTIMISED NON RECURSIVE QSORT 54
NON RECURSIVE QSORT II 67
FLASH SORT 41
BUILT IN ARRAY.SORT 103
——————————————————–
BTW, downloaded the class and it has errors on lines 43 and 90.
SORTING RESULTS (WINDOWS 7 – WIN 10,0,32,18)
——————————————————–
QSORT + INSERTION SORT 76
3 WAY QSORT + INSERTION 70
NON RECURSIVE QSORT 85
OPTIMISED NON RECURSIVE QSORT 45
NON RECURSIVE QSORT II 48
FLASH SORT 35
BUILT IN ARRAY.SORT 105
thanks for the test, very useful
You should add the radix sort.