_ArrayIntroSort()

[-Ultima-]

Erm, not sure what else to say about this, really. It's an array sorting function that uses the IntroSort algorithm (sort of an amalgamation of QuickSort, HeapSort, and InsertionSort). For 1D arrays, my tests have shown improvements of, on average, 50-70% in comparison with _ArraySort() using the same datasets. For 2D arrays, the improvments generally float around 15-30%. YMMV, and it's really all dependent on the dataset fed into the functions that determine the length of time. I've seen times where the improvements were minimal (around or less than 5%), but for the most part, I get significant improvements.

Just a note about the code... There is a LOT of code duplication, but that's because of performance concerns. Code duplication happens when I need to check for ascending/descending sorting, and for 1D/2D array sorting. I could just as simply have put the conditionals inside a single for loop in many places, but since the conditionals would be static for each time through the loop, there is no point leaving them in the loop; they're just eating at performance, especially with the algorithm's heavy reliance on loops and recursion. So yeah, I sacrifice a bit more disk space for the sake of what is (IMHO) a great performance boost, but that's a perfectly-reasonable compromise, right?

Included in the download is a script for stress testing the function (aptly named _ArrayIntroSort_TEST.au3 xD). There are parameters and settings variables you can change at the top of the script; they're pretty straightforward. I also included a version without 2D array support. I don't think it performs much better on 1D arrays (an average of a percent or two of difference, IIRC), but the code is cleaner and easier on the eyes... somewhat (you'll still have to wade through a bit of duplication for descending sort).

Just for reference, I'm using an Intel Core 2 Duo E6600, but I doubt that'd make much difference in terms of performance gain. I don't feel too confident about this function's quality yet, but thought I'd post it for a wider audience to test. Happy guinea-pigging, and please comments and provide feedback! Thanks!

P.S.: I've run through Array.au3 in the last day or two, and have improved performance in a bunch of the functions. After I organize my changes, I'll create a new thread for the overhauled Array.au3.

_ArrayIntroSort.zip

Edited August 25, 2007 by -Ultima-

[randallc]

Hey!

I like it!

Compare with my vbs routine quicksort, which still reads as 150% better?; [PS which always sorts wholearray at present; start and end acn be added, but never nedded it..; but can also subsort 2D arrrays]

Does it mean it is worth my trying to use your algorithm in vbs to speed it up even more?

Best, Randall

Edited August 24, 2007 by randallc

[-Ultima-]

lol here I was, all happy that I managed to write a faster sorting function, and you come along with an even faster one that blows my function out of the water xD The only advantage I can see to mine now is that it's all native AutoIt :|

Um, if you want, you can try converting the introsort algorithm I used to VBScript. I'd be interested in seeing if there are any improvements

[randallc]

lol here I was, all happy that I managed to write a faster sorting function, and you come along with an even faster one that blows my function out of the water xD The only advantage I can see to mine now is that it's all native AutoIt :|

Um, if you want, you can try converting the introsort algorithm I used to VBScript. I'd be interested in seeing if there are any improvements

OK, I agree it is good to get it as pure AutoIt;

I'll look at the vbs sometime too.

Randall

[randallc]

Um, if you want, you can try converting the introsort algorithm I used to VBScript. I'd be interested in seeing if there are any improvements

Hi,

No,

Actually 10% slower than the vbs I had!

Oh well... I am looking at jscript now; the inbuilt sort is 5.5x as fast as your IntroSort for 1D; still trying to get it working in 2D in ScriptObject; natively its also faster, but the conversions required to get 2D to work there will mean not quite such a big speed increase; I'm guessing still x4, which will still put it x2 of my fastest vbs.

No; -[EDIT]

I have the 1D sort working, and it is 8-10x faster than _arraySort on 1D.

The 2D is a lot slower than my vbs sort routine (already 6x faster than _ArraySort); unless there is a way I don't know; looks like jscript does not use same fast sort for 2D (its 2D arrays are arrays of single arrays essentially! - I think!)

Best, randall

Func _JSort1D(ByRef $arEither2D1D)
    Local $code = '   function SortArray(arrArray) {'
    $code &= @LF & '            return arrArray.toArray().sort().join("|");'
    $code &= @LF & '        }'
    Local $jvs = ObjCreate("ScriptControl")
    $jvs.language = "jscript"
    $jvs.Timeout = -1
    $jvs.addcode ($code)
    FileWrite(@ScriptDir & "\subsortIntroau3a.jvs", $code)
    Local $arEither2D1DSt = $jvs.Run("SortArray", $arEither2D1D);, $iIndex, $icase)
    $arEither2D1D = StringSplit($arEither2D1DSt, "|")
    $jvs = ""
EndFunc   ;==>_JSort1D

[btw, The testing script is incorrect; the arrays are sorted the first round so order of testing counts; I have corrected it for my tests, but not in the posted zip yet..]

Edited September 13, 2007 by randallc

[-Ultima-]

[btw, The testing script is incorrect; the arrays are sorted the first round so order of testing counts; I have corrected it for my tests, but not in the posted zip yet..]

Yeah, I noticed the same thing... I'm not really sure why my function affects $avReference when I'm clearly copying $avReference (rather than using it directly). The easiest way I got around this was to set $array[0] = $array[0] immediately after $array = $avReference. Unfortunately, that seems to have cut the performance gain by around 30%, so it seems my function is actually faster than _ArraySort() by only 40%

I can't say I'm really all that surprised at how fast Javascript's built-in array sorting function is. Nevertheless, nice work there Now, imagine if WSH were using Opera's Javascript engine...

[randallc]

clearly copying $avReference (rather than using it directly).

hi,

Your original test script just gives the array another name;

$array=$avReference

, so there is only one array and it is sorted by whatever name you use to sort.

You would need to declare array separately, then copy each item in $avReference by a loop to $array each time, or make a whole set of arrays before the test loop; to use in the test ..

Best, Randall

[-Ultima-]

As far as I remember (I tested it a long time ago), setting a variable to an array doesn't set the variable as new name for the same pointer to the old array; it actually copies the old array. Granted, I might've tested it incorrectly, but that doesn't change the fact that $avReference wasn't changed after I called _ArraySort() on $array = $avReference :\

This script illustrates the point completely:

#Include <Array.au3>

Local $avArray
Local $avReference[4] = [3, 5, 6, 1]

$avArray = $avReference
$avArray[0] = 1
_ArrayDisplay($avArray, "$avArray")
_ArrayDisplay($avReference, "$avReference")

Edit: Mistake... I see what you mean now. Using _ArraySwap($avArray[0], $avArray[1]) modifies both $avArray and $avReference. Mistaken coding/testing on my part

I wonder if this means I should write an _ArrayCopy() function...

Edit: No, wait, I just tested $avArray[0] = $avArray[0], and it was as I thought: modifying the array just once copies it entirely -- copy on write.

#Include <Array.au3>

Local $avArray
Local $avReference[4] = [3, 5, 6, 1]

$avArray = $avReference
$avArray[0] = $avArray[0]
_ArraySwap($avArray[1], $avArray[3])
_ArrayDisplay($avArray, "$avArray")
_ArrayDisplay($avReference, "$avReference")

Edited December 7, 2007 by -Ultima-

[randallc]

Hi,

I've learnt something! thanks.

Randall