czardas

Optimized _ArraySort

44 posts in this topic

A while ago I suggested that _ArraySort could be optimized for 2D arrays. I have asked for MVPs to test this code and give feedback, but it seems everyone is rather busy. I have decided to reproduce the code here, so you may do with it as you wish. My results show that (generally) the more columns you have, the faster the function runs. In some tests it ran 6 times faster than the original. This is a spin-off from another project of mine which you may already be familiar with.

#include <Array.au3>

; #FUNCTION# ====================================================================================================================
; Author ........: Jos
; Modified.......: LazyCoder - added $iSubItem option; Tylo - implemented stable QuickSort algo; Jos - changed logic to correctly Sort arrays with mixed Values and Strings; Melba23 - implemented stable pivot algo; czardas - speed optimization for 2D arrays
; ===============================================================================================================================
Func _ArraySort_NEW2(ByRef $aArray, $iDescending = 0, $iStart = 0, $iEnd = 0, $iSubItem = 0, $iPivot = 0)

    If $iDescending = Default Then $iDescending = 0
    If $iStart = Default Then $iStart = 0
    If $iEnd = Default Then $iEnd = 0
    If $iSubItem = Default Then $iSubItem = 0
    If $iPivot = Default Then $iPivot = 0
    If Not IsArray($aArray) Then Return SetError(1, 0, 0)

    Local $iUBound = UBound($aArray) - 1
    If $iUBound = -1 Then Return SetError(5, 0, 0)

    ; Bounds checking
    If $iEnd = Default Then $iEnd = 0
    If $iEnd < 1 Or $iEnd > $iUBound Or $iEnd = Default Then $iEnd = $iUBound
    If $iStart < 0 Or $iStart = Default Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(2, 0, 0)

    If $iDescending = Default Then $iDescending = 0
    If $iPivot = Default Then $iPivot = 0
    If $iSubItem = Default Then $iSubItem = 0

    ; Sort
    Switch UBound($aArray, $UBOUND_DIMENSIONS)
        Case 1
            If $iPivot Then ; Switch algorithms as required
                __ArrayDualPivotSort($aArray, $iStart, $iEnd)
            Else
                __ArrayQuickSort1D($aArray, $iStart, $iEnd)
            EndIf
            If $iDescending Then _ArrayReverse($aArray, $iStart, $iEnd)
        Case 2
            If $iPivot Then Return SetError(6, 0, 0) ; Error if 2D array and $iPivot
            Local $iSubMax = UBound($aArray, $UBOUND_COLUMNS) - 1
            If $iSubItem > $iSubMax Then Return SetError(3, 0, 0)

            If $iDescending Then
                $iDescending = -1
            Else
                $iDescending = 1
            EndIf

            Local $aTrac[$iUBound +1] ; to track migrating indeces
            For $i = $iStart To $iEnd
                $aTrac[$i] = $i
            Next

            __ArrayQuickSort2D_NEW2($aArray, $aTrac, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax)
            __SwapSequence2D($aArray, $aTrac, $iStart, $iEnd)
        Case Else
            Return SetError(4, 0, 0)
    EndSwitch

    Return 1
EndFunc   ;==>_ArraySort

; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name...........: __ArrayQuickSort2D
; Description ...: Helper function for sorting 2D arrays
; Syntax.........: __ArrayQuickSort2D ( ByRef $aArray, ByRef $iStep, ByRef $iStart, ByRef $iEnd, ByRef $iSubItem, ByRef $iSubMax )
; Parameters ....: $aArray  - Array to sort
;                  $iStep    - Step size (should be 1 to sort ascending, -1 to sort descending!)
;                  $iStart   - Index of array to start sorting at
;                  $iEnd     - Index of array to stop sorting at
;                  $iSubItem - Sub-index to sort on in 2D arrays
;                  $iSubMax  - Maximum sub-index that array has
; Return values .: None
; Author ........: Jos van der Zande, LazyCoder, Tylo, Ultima, czardas
; Modified.......:
; Remarks .......: For Internal Use Only
; Related .......:
; Link ..........:
; Example .......:
; ===============================================================================================================================
Func __ArrayQuickSort2D_NEW2(Const ByRef $aArray, ByRef $aTrac, Const ByRef $iStep, Const ByRef $iStart, Const ByRef $iEnd, Const ByRef $iSubItem, Const ByRef $iSubMax)
    If $iEnd <= $iStart Then Return

    Local $iTmp

    ; InsertionSort (faster for smaller segments)
    If ($iEnd - $iStart) < 15 Then
        For $i = $iStart + 1 To $iEnd
            $iTmp = $aTrac[$i]

            If IsNumber($aArray[$iTmp][$iSubItem]) Then
                For $j = $i - 1 To $iStart Step -1
                    ; Follows the same logic as __ArrayQuickSort1D
                    If ((($aArray[$iTmp][$iSubItem] * $iStep) >= $aArray[$aTrac[$j]][$iSubItem] * $iStep) And IsNumber($aArray[$aTrac[$j]][$iSubItem])) _
                    Or (Not IsNumber($aArray[$aTrac[$j]][$iSubItem]) And StringCompare($aArray[$iTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            Else
                For $j = $i - 1 To $iStart Step -1
                    If (StringCompare($aArray[$iTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            EndIf

            $aTrac[$j + 1] = $iTmp
        Next
        Return
    EndIf

    ; QuickSort
    Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[$aTrac[Int(($iStart + $iEnd) / 2)]][$iSubItem], $bNum = IsNumber($vPivot)
    Do
        If $bNum Then
            ; While ($iStep * ($aArray[$L][$iSubItem] - $vPivot) < 0 And IsNumber($aArray[$L][$iSubItem])) Or (Not IsNumber($aArray[$L][$iSubItem]) And $iStep * StringCompare($aArray[$L][$iSubItem], $vPivot) < 0)
            While ($iStep * ($aArray[$aTrac[$L]][$iSubItem] - $vPivot) < 0 And IsNumber($aArray[$aTrac[$L]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$L]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            ; While ($iStep * ($aArray[$R][$iSubItem] - $vPivot) > 0 And IsNumber($aArray[$R][$iSubItem])) Or (Not IsNumber($aArray[$R][$iSubItem]) And $iStep * StringCompare($aArray[$R][$iSubItem], $vPivot) > 0)
            While ($iStep * ($aArray[$aTrac[$R]][$iSubItem] - $vPivot) > 0 And IsNumber($aArray[$aTrac[$R]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$R]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        Else
            While ($iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            While ($iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        EndIf

        ; Swap
        If $L <= $R Then
            $iTmp = $aTrac[$L]
            $aTrac[$L] = $aTrac[$R]
            $aTrac[$R] = $iTmp
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R

    __ArrayQuickSort2D_NEW2($aArray, $aTrac, $iStep, $iStart, $R, $iSubItem, $iSubMax)
    __ArrayQuickSort2D_NEW2($aArray, $aTrac, $iStep, $L, $iEnd, $iSubItem, $iSubMax)
EndFunc   ;==>__ArrayQuickSort2D_NEW2


; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name...........: ___SwapSequence2D
; Description ...: Helper function for populating 2D arrays. [algorithm modelled on the knight's tour problem]
; Author ........: czardas
; ===============================================================================================================================
Func __SwapSequence2D(ByRef $aArray, ByRef $aTrac, $iStart, $iEnd)
    Local $iCols = UBound($aArray, 2), $aFirst[$iCols], $i, $iNext

    For $iInit = $iStart To $iEnd ; initialize each potential overwrite sequence [separate closed system]
        If $aTrac[$iInit] <> $iInit Then ; rows will now be overwritten in accordance with tracking information
            $i = $iInit ; set the current row as the start of the sequence

            For $j = 0 To $iCols -1
                $aFirst[$j] = $aArray[$i][$j] ; copy the first row [although we don't know where to put it yet]
            Next

            Do
                For $j = 0 To $iCols -1
                    $aArray[$i][$j] = $aArray[$aTrac[$i]][$j] ; overwrite each row [following the trail]
                Next
                $iNext = $aTrac[$i] ; get the index of the next row in the sequence
                $aTrac[$i] = $i ; set to ignore rows already processed [may be needed once, or not at all]
                $i = $iNext ; follow the trail as far as it goes [indices could be higher or lower]
            Until $aTrac[$i] = $iInit ; all tracking sequences end at this juncture

            For $j = 0 To $iCols -1
                $aArray[$i][$j] = $aFirst[$j] ; now we know where to put the initial row we copied earlier
            Next
            $aTrac[$i] = $i ; set to ignore rows already processed [as above]
        EndIf
    Next
EndFunc ;==> __SwapSequence2D

 

2 people like this

Share this post


Link to post
Share on other sites



Quote

No feedback is also a form of feedback.

 

1 person likes this

Share this post


Link to post
Share on other sites

How about just a like, i would also give it stars if it were in examples?

1 person likes this

,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)

Share this post


Link to post
Share on other sites

Your supposed to rip it apart, try to break it and prove it to be less suitable than the current version, or report failure to do so after the attempt. Not to worry though, Melba23 said he thought it was worthwhile developing at least. I have just about run out of things to test, and have presented it here for wider scrutiny. Some tests are slow and should really be tested on a powerful machine: which I don't have.

Share this post


Link to post
Share on other sites

@czardas I don't have a ton of time to write anything up, but have a bevy of high end machines, both physical and virtual, if you want to post some examples you would like tested.

1 person likes this

√-1 2^3 ∑ π, and it was delicious!

Share this post


Link to post
Share on other sites

Thanks JLogan3013, it's very kind of you to offer. :) I'll put post some tests quite soon.

Share this post


Link to post
Share on other sites

Sorry, I was busy with some gfx filter ideas I had which I wanted to implement and thus I didn't see this thread.

Well done czardas, the speed is around 80% - 90% faster than the original one. :thumbsup:

I tested an 2D array with 3765 lines and 10 columns. The content of the sorted array is the same as the built-in sort function!

I assume you love arrays... ;)

 

1 person likes this

Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Share this post


Link to post
Share on other sites

#8 ·  Posted (edited)

 

Okay here's, what I would call, some extreme tests. There are eight tests and three parameters that can be modified. You can run all eight tests one after the other, or one at a time. I have ran tests 1, 2 and 4. I also seem to have stumbled upon a silent COM error occurring with second loop (fixed by adding line # 36 to the test).

Test # 1 : Penalty = 0
170698.808549553 _ArraySort($aArray2D, 0, 0, 0, 0)
50058.7355801295 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

->22:05:37 AutoIt3.exe ended.rc:1

Back on topic, I have not yet ran all 8 tests. The code below is set to only run test 4 - change the following values $iFirstTest = 4 and $iLastTest = 4, depending on how much time you have. Test 8 should be the toughest. There will always be some discrepancy in the results because the sorting columns (only) contain similar data: the starting conditions are not identical. This saves having to store the exact initial conditions while sorting.

The penalty parameter adds bloat to the array. I haven't yet tested the difference this makes. It should make more difference to the first tests (with more columns) because of the way I've coded this. Be careful with adding penalties (start small with penalty = 1). Memory issues will occur at some point. With test number 8, a tracker array containing 8388608 indices uses up a fair amount of RAM. The question is how frequently is something like this is going to be a problem, and for who?

#include <Array.au3>

Global $iPenalty = 0 ; Caution: 1 penalty point = between 8 and 16 megabytes depending on the test number
Global $iFirstTest = 4 ; lowest test number = 1
Global $iLastTest = 4 ; highest test number = 8

; the following sleep values can be modified depending on available RAM
Global $iNap = 30000 ; 30 secs - short sleep
Global $iSleep = 40000 ; 40 secs - long sleep to be multiplied by the test number because each test becomes more brutal

; Bounds for 2D arrays containing 16777216 elements [Rows, Columns]
Global $aArray[0][0], $aArray2D = $aArray, $aBounds = [['',''],[512,32768],[1024,16384],[2048,8192],[4096,4096],[8192,2048],[16384,1024],[32768,512],[8388608, 2]]
Global $iTimer, $sBloat = StringFormat("%0" & $iPenalty & "s", "")

For $iTestNum = $iFirstTest To $iLastTest
    ;ReDim $aArray2D[0][0] ; get rid of all previous data [COM ERROR HERE ON 1ST REPEAT ==> see line 36 below]

    ReDim $aArray2D [$aBounds[$iTestNum][0]] [$aBounds[$iTestNum][1]] ; resize the array
    GenerateHorribleData($aArray2D) ; the first two columns are filled with random strings and numbers
    AddMoreBloat($aArray2D) ; the rest array is filled with the same string duplicated again and again
    Sleep($iNap)
    ConsoleWrite("Test # " & $iTestNum & " : Rows = " & UBound($aArray2D) & " : Columns = " & UBound($aArray2D, 2) & " : Penalty = " & $iPenalty & @LF)

    ; now we are ready to run tests
    $iTimer = TimerInit()
    ; for the 1st test, sort on the first column
    _ArraySort($aArray2D, 0, 0, 0, 0)
    ConsoleWrite(TimerDiff($iTimer) & " _ArraySort($aArray2D, 0, 0, 0, 0)" & @LF)
    Sleep($iSleep * $iTestNum) ; multiplied by the test number because each test becomes more brutal

    $iTimer = TimerInit()
    ; sort similar data on the second column
    _ArraySort_NEW2($aArray2D, 0, 0, 0, 1) ; the more rows, the more similar the starting conditions [lost after the 1st sort]
    ConsoleWrite(TimerDiff($iTimer) & " _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)" & @LF & @LF)

    $aArray2D = $aArray ; patch to deal with the COM error above
    Sleep($iSleep * $iTestNum)
Next

Func GenerateHorribleData(ByRef $aArray2D)
    If Not IsArray($aArray2D) Or UBound($aArray2D, 0) <> 2 Or UBound($aArray2D) < 2 Or UBound($aArray2D, 2) < 2 Then Return SetError(1)

    ; strings of 4 characters selected from 95 available characters would generate enough permutations to fill an array with 16777216 elements
    ; so I guess 3 characters will suffice
    Local $iCount = 0, $aCombi[1714750] ; 2 * 95 ^ 3

    ; create 857375 unique strings
    For $i = 32 To 126 ; use ascii range 126 - 31 = 95 characters
        For $j = 32 To 126
            For $k = 32 To 126
                $aCombi[$iCount] = $sBloat & Chr($i) & Chr($j) & Chr($k)
                $iCount += 1
            Next
        Next
    Next

    ; add another 857375 integers - exactly the same number as strings
    For $i = 857375 To 1714749
        $aCombi[$i] = $i
    Next

    _ArrayShuffle($aCombi) ; generate a random sample of 1714750 unique values
    For $i = 0 To UBound($aArray2D) - 1
        $aArray2D[$i][0] = $aCombi[Mod($i, 1714750)]
    Next

    _ArrayShuffle($aCombi) ; generate a similar random sample of 1714750 unique values
    For $i = 0 To UBound($aArray2D) - 1
        $aArray2D[$i][1] = $aCombi[Mod($i, 1714750)]
    Next
    ;_ArrayDisplay($aCombi, "Combi", '857000:857374')
EndFunc ; GenerateHorribleData

Func AddMoreBloat(ByRef $aArray2D)
    Local $sMoreBloat = $sBloat & "str"
    If Not IsArray($aArray2D) Or UBound($aArray2D, 0) <> 2 Or UBound($aArray2D) < 2 Or UBound($aArray2D, 2) < 2 Then Return SetError(1)
    For $i = 0 To UBound($aArray2D) -1
        For $j = 2 To UBound($aArray2D, 2) -1
            $aArray2D[$i][$j] = $sMoreBloat
        Next
    Next
EndFunc


; #FUNCTION# ====================================================================================================================
; Author ........: Jos
; Modified.......: LazyCoder - added $iSubItem option; Tylo - implemented stable QuickSort algo; Jos - changed logic to correctly Sort arrays with mixed Values and Strings; Melba23 - implemented stable pivot algo; czardas - speed optimization for 2D arrays
; ===============================================================================================================================
Func _ArraySort_NEW2(ByRef $aArray, $iDescending = 0, $iStart = 0, $iEnd = 0, $iSubItem = 0, $iPivot = 0)

    If $iDescending = Default Then $iDescending = 0
    If $iStart = Default Then $iStart = 0
    If $iEnd = Default Then $iEnd = 0
    If $iSubItem = Default Then $iSubItem = 0
    If $iPivot = Default Then $iPivot = 0
    If Not IsArray($aArray) Then Return SetError(1, 0, 0)

    Local $iUBound = UBound($aArray) - 1
    If $iUBound = -1 Then Return SetError(5, 0, 0)

    ; Bounds checking
    If $iEnd = Default Then $iEnd = 0
    If $iEnd < 1 Or $iEnd > $iUBound Or $iEnd = Default Then $iEnd = $iUBound
    If $iStart < 0 Or $iStart = Default Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(2, 0, 0)

    If $iDescending = Default Then $iDescending = 0
    If $iPivot = Default Then $iPivot = 0
    If $iSubItem = Default Then $iSubItem = 0

    ; Sort
    Switch UBound($aArray, $UBOUND_DIMENSIONS)
        Case 1
            If $iPivot Then ; Switch algorithms as required
                __ArrayDualPivotSort($aArray, $iStart, $iEnd)
            Else
                __ArrayQuickSort1D($aArray, $iStart, $iEnd)
            EndIf
            If $iDescending Then _ArrayReverse($aArray, $iStart, $iEnd)
        Case 2
            If $iPivot Then Return SetError(6, 0, 0) ; Error if 2D array and $iPivot
            Local $iSubMax = UBound($aArray, $UBOUND_COLUMNS) - 1
            If $iSubItem > $iSubMax Then Return SetError(3, 0, 0)

            If $iDescending Then
                $iDescending = -1
            Else
                $iDescending = 1
            EndIf

            Local $aTrac[$iUBound +1] ; to track migrating indeces
            For $i = $iStart To $iEnd
                $aTrac[$i] = $i
            Next

            __ArrayQuickSort2D_NEW2($aArray, $aTrac, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax)
            __SwapSequence2D($aArray, $aTrac, $iStart, $iEnd)
        Case Else
            Return SetError(4, 0, 0)
    EndSwitch

    Return 1
EndFunc   ;==>_ArraySort

; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name...........: __ArrayQuickSort2D
; Description ...: Helper function for sorting 2D arrays
; Syntax.........: __ArrayQuickSort2D ( ByRef $aArray, ByRef $iStep, ByRef $iStart, ByRef $iEnd, ByRef $iSubItem, ByRef $iSubMax )
; Parameters ....: $aArray  - Array to sort
;                  $iStep    - Step size (should be 1 to sort ascending, -1 to sort descending!)
;                  $iStart   - Index of array to start sorting at
;                  $iEnd     - Index of array to stop sorting at
;                  $iSubItem - Sub-index to sort on in 2D arrays
;                  $iSubMax  - Maximum sub-index that array has
; Return values .: None
; Author ........: Jos van der Zande, LazyCoder, Tylo, Ultima, czardas
; Modified.......:
; Remarks .......: For Internal Use Only
; Related .......:
; Link ..........:
; Example .......:
; ===============================================================================================================================
Func __ArrayQuickSort2D_NEW2(Const ByRef $aArray, ByRef $aTrac, Const ByRef $iStep, Const ByRef $iStart, Const ByRef $iEnd, Const ByRef $iSubItem, Const ByRef $iSubMax)
    If $iEnd <= $iStart Then Return

    Local $iTmp

    ; InsertionSort (faster for smaller segments)
    If ($iEnd - $iStart) < 15 Then
        For $i = $iStart + 1 To $iEnd
            $iTmp = $aTrac[$i]

            If IsNumber($aArray[$iTmp][$iSubItem]) Then
                For $j = $i - 1 To $iStart Step -1
                    ; Follows the same logic as __ArrayQuickSort1D
                    If ((($aArray[$iTmp][$iSubItem] * $iStep) >= $aArray[$aTrac[$j]][$iSubItem] * $iStep) And IsNumber($aArray[$aTrac[$j]][$iSubItem])) _
                    Or (Not IsNumber($aArray[$aTrac[$j]][$iSubItem]) And StringCompare($aArray[$iTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            Else
                For $j = $i - 1 To $iStart Step -1
                    If (StringCompare($aArray[$iTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            EndIf

            $aTrac[$j + 1] = $iTmp
        Next
        Return
    EndIf

    ; QuickSort
    Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[$aTrac[Int(($iStart + $iEnd) / 2)]][$iSubItem], $bNum = IsNumber($vPivot)
    Do
        If $bNum Then
            ; While ($iStep * ($aArray[$L][$iSubItem] - $vPivot) < 0 And IsNumber($aArray[$L][$iSubItem])) Or (Not IsNumber($aArray[$L][$iSubItem]) And $iStep * StringCompare($aArray[$L][$iSubItem], $vPivot) < 0)
            While ($iStep * ($aArray[$aTrac[$L]][$iSubItem] - $vPivot) < 0 And IsNumber($aArray[$aTrac[$L]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$L]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            ; While ($iStep * ($aArray[$R][$iSubItem] - $vPivot) > 0 And IsNumber($aArray[$R][$iSubItem])) Or (Not IsNumber($aArray[$R][$iSubItem]) And $iStep * StringCompare($aArray[$R][$iSubItem], $vPivot) > 0)
            While ($iStep * ($aArray[$aTrac[$R]][$iSubItem] - $vPivot) > 0 And IsNumber($aArray[$aTrac[$R]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$R]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        Else
            While ($iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            While ($iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        EndIf

        ; Swap
        If $L <= $R Then
            $iTmp = $aTrac[$L]
            $aTrac[$L] = $aTrac[$R]
            $aTrac[$R] = $iTmp
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R

    __ArrayQuickSort2D_NEW2($aArray, $aTrac, $iStep, $iStart, $R, $iSubItem, $iSubMax)
    __ArrayQuickSort2D_NEW2($aArray, $aTrac, $iStep, $L, $iEnd, $iSubItem, $iSubMax)
EndFunc   ;==>__ArrayQuickSort2D_NEW2


; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name...........: ___SwapSequence2D
; Description ...: Helper function for populating 2D arrays. [algorithm modelled on the knight's tour problem]
; Author ........: czardas
; ===============================================================================================================================
Func __SwapSequence2D(ByRef $aArray, ByRef $aTrac, $iStart, $iEnd)
    Local $iCols = UBound($aArray, 2), $aFirst[$iCols], $i, $iNext

    For $iInit = $iStart To $iEnd ; initialize each potential overwrite sequence [separate closed system]
        If $aTrac[$iInit] <> $iInit Then ; rows will now be overwritten in accordance with tracking information
            $i = $iInit ; set the current row as the start of the sequence

            For $j = 0 To $iCols -1
                $aFirst[$j] = $aArray[$i][$j] ; copy the first row [although we don't know where to put it yet]
            Next

            Do
                For $j = 0 To $iCols -1
                    $aArray[$i][$j] = $aArray[$aTrac[$i]][$j] ; overwrite each row [following the trail]
                Next
                $iNext = $aTrac[$i] ; get the index of the next row in the sequence
                $aTrac[$i] = $i ; set to ignore rows already processed [may be needed once, or not at all]
                $i = $iNext ; follow the trail as far as it goes [indices could be higher or lower]
            Until $aTrac[$i] = $iInit ; all tracking sequences end at this juncture

            For $j = 0 To $iCols -1
                $aArray[$i][$j] = $aFirst[$j] ; now we know where to put the initial row we copied earlier
            Next
            $aTrac[$i] = $i ; set to ignore rows already processed [as above]
        EndIf
    Next
EndFunc ;==> __SwapSequence2D

 

Test # 1 : Rows = 512 : Columns = 32768 : Penalty = 0
175234.748283886 _ArraySort($aArray2D, 0, 0, 0, 0)
49156.9694463294 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Test # 2 : Rows = 1024 : Columns = 16384 : Penalty = 0
196477.845967679 _ArraySort($aArray2D, 0, 0, 0, 0)
70024.0488928627 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Test # 4 : Rows = 4096 : Columns = 4096 : Penalty = 0
283877.033926195 _ArraySort($aArray2D, 0, 0, 0, 0)
72032.9163305307 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Edit

Test # 8 : Rows = 8388608 : Columns = 2 : Penalty = 0
1696033.42199072 _ArraySort($aArray2D, 0, 0, 0, 0)
1313561.93845872 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

 

Edited by czardas

Share this post


Link to post
Share on other sites

#9 ·  Posted (edited)

The above tests are focused on the largest arrays possible, and that last test took the best part of an hour to run. I would like them to be run on a high-end machine with some penalty (bloat) added. More specific/accurate tests can be done with smaller arrays quite quickly, so I can handle that myself. I'll create, and post the results of, these smaller tests shortly.

Edited by czardas

Share this post


Link to post
Share on other sites

#10 ·  Posted (edited)

19 hours ago, UEZ said:

... The content of the sorted array is the same as the built-in sort function!

I assume you love arrays... ;)

I could not confirm this. :no:

#include <Array.au3>

Local $aWithDupes = [['s',0],['dupe',1],['d',2],['dupe',3],['dupe',4],['a',5],['dupe',6],['l',7],['z',8],['dupe',9]]
_ArrayDisplay($aWithDupes)

Local $aTest = $aWithDupes
_ArraySort($aTest)
_ArrayDisplay($aTest)

$aTest = $aWithDupes
_ArraySort_NEW2($aTest)
_ArrayDisplay($aTest)

Notice that duplicates end up in different positions. The code can be made to follow the exact same logic as the original, but it would be sub-optimal regarding speed. The time penalty would not have such a great impact, and the change would actually involve less code. I don't know how many people rely on the exact behaviour of the sort function, but for anyone who does, this change would indeed break those scripts. You can choose to have it run (let's say) 4 times faster, or 3 times faster with exact modelling of the original.

I don't love arrays, but I can get my head around them at least. :P (just about)

Edited by czardas

Share this post


Link to post
Share on other sites

#11 ·  Posted

Hmmm, the test array I used worked properly. :(

 

I'm sure you will fix it. :)

1 person likes this

Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Share this post


Link to post
Share on other sites

#12 ·  Posted (edited)

It's not a bug and I really doubt it will break many scripts. It's hard to spot if you don't know about it though. The only difference is that insertion sort is not used in the original. All that needs doing is to remove that part of the code and it will still run faster, but not quite as fast. The slightly faster version will probably effect 1 in a million scripts (if any at all). Don't quote me on that last statistic. :shhh:

Func __ArrayQuickSort2D_NEW2(Const ByRef $aArray, ByRef $aTrac, Const ByRef $iStep, Const ByRef $iStart, Const ByRef $iEnd, Const ByRef $iSubItem, Const ByRef $iSubMax)
    If $iEnd <= $iStart Then Return

    Local $iTmp

    ; InsertionSort (faster for smaller segments)
    ;If ($iEnd - $iStart) < 15 Then
    ;    For $i = $iStart + 1 To $iEnd
    ;        $iTmp = $aTrac[$i]

    ;        If IsNumber($aArray[$iTmp][$iSubItem]) Then
    ;            For $j = $i - 1 To $iStart Step -1
    ;                ; Follows the same logic as __ArrayQuickSort1D
    ;                If ((($aArray[$iTmp][$iSubItem] * $iStep) >= $aArray[$aTrac[$j]][$iSubItem] * $iStep) And IsNumber($aArray[$aTrac[$j]][$iSubItem])) _
    ;                Or (Not IsNumber($aArray[$aTrac[$j]][$iSubItem]) And StringCompare($aArray[$iTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
    ;                $aTrac[$j + 1] = $aTrac[$j]
    ;            Next
    ;        Else
    ;            For $j = $i - 1 To $iStart Step -1
    ;                If (StringCompare($aArray[$iTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
    ;                $aTrac[$j + 1] = $aTrac[$j]
    ;            Next
    ;        EndIf

    ;        $aTrac[$j + 1] = $iTmp
    ;    Next
    ;    Return
    ;EndIf

    ; QuickSort
    Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[$aTrac[Int(($iStart + $iEnd) / 2)]][$iSubItem], $bNum = IsNumber($vPivot)
    Do
        If $bNum Then
            ; While ($iStep * ($aArray[$L][$iSubItem] - $vPivot) < 0 And IsNumber($aArray[$L][$iSubItem])) Or (Not IsNumber($aArray[$L][$iSubItem]) And $iStep * StringCompare($aArray[$L][$iSubItem], $vPivot) < 0)
            While ($iStep * ($aArray[$aTrac[$L]][$iSubItem] - $vPivot) < 0 And IsNumber($aArray[$aTrac[$L]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$L]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            ; While ($iStep * ($aArray[$R][$iSubItem] - $vPivot) > 0 And IsNumber($aArray[$R][$iSubItem])) Or (Not IsNumber($aArray[$R][$iSubItem]) And $iStep * StringCompare($aArray[$R][$iSubItem], $vPivot) > 0)
            While ($iStep * ($aArray[$aTrac[$R]][$iSubItem] - $vPivot) > 0 And IsNumber($aArray[$aTrac[$R]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$R]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        Else
            While ($iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            While ($iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        EndIf

        ; Swap
        If $L <= $R Then
            $iTmp = $aTrac[$L]
            $aTrac[$L] = $aTrac[$R]
            $aTrac[$R] = $iTmp
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R

    __ArrayQuickSort2D_NEW2($aArray, $aTrac, $iStep, $iStart, $R, $iSubItem, $iSubMax)
    __ArrayQuickSort2D_NEW2($aArray, $aTrac, $iStep, $L, $iEnd, $iSubItem, $iSubMax)
EndFunc   ;==>__ArrayQuickSort2D_NEW2

There are various things to consider. The idea does not have to be included, but I would be happy to try and implement a natural sort algorithm whether the discussion leads to approval or not.

Edited by czardas

Share this post


Link to post
Share on other sites

#13 ·  Posted

Here are the results I got, I did 1, 2, 4, 8, then 8 with penalty of 8. I was surprised by the penalty = 8 test.

$iPenalty = 0, $iFirstTest = 1, $iLastTest = 1
Test # 1 : Rows = 512 : Columns = 32768 : Penalty = 0
143321.83322182 _ArraySort($aArray2D, 0, 0, 0, 0)
55373.6809426896 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)
>Exit code: 0    Time: 356

$iPenalty = 0, $iFirstTest = 2, $iLastTest = 2
Test # 2 : Rows = 1024 : Columns = 16384 : Penalty = 0
142162.607119061 _ArraySort($aArray2D, 0, 0, 0, 0)
30920.2960152757 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)
>Exit code: 0    Time: 409.1

$iPenalty = 0, $iFirstTest = 4, $iLastTest = 4
Test # 4 : Rows = 4096 : Columns = 4096 : Penalty = 0
164597.794412418 _ArraySort($aArray2D, 0, 0, 0, 0)
27695.3273390892 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)
>Exit code: 0    Time: 592.3

$iPenalty = 0, $iFirstTest = 8, $iLastTest = 8
Test # 8 : Rows = 8388608 : Columns = 2 : Penalty = 0
1453897.91097751 _ArraySort($aArray2D, 0, 0, 0, 0)
1171085.54159816 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)
>Exit code: 0    Time: 3380

$iPenalty = 8, $iFirstTest = 8, $iLastTest = 8
Test # 8 : Rows = 8388608 : Columns = 2 : Penalty = 8
1418870.40608513 _ArraySort($aArray2D, 0, 0, 0, 0)
1130443.45119282 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)
>Exit code: 0    Time: 3303

 

1 person likes this

√-1 2^3 ∑ π, and it was delicious!

Share this post


Link to post
Share on other sites

#14 ·  Posted (edited)

The results for test #4 are awesome (6x)! :D The discrepancies between similar tests are possibly to do with initial conditions being different due to the randomization elements. These results do give a rough impression though. It's easier to test smaller arrays using the exact same starting conditions, because the extra memory usage, or processing to recreate identical conditions, will have less impact. More accurate (faster) tests are the next step.

Edited by czardas

Share this post


Link to post
Share on other sites

#15 ·  Posted (edited)

This morning I decided to run a few more tests. Adding penalty to #8 has the least impact because there were only two columns in the previous setup and most of the bloat goes in the later columns. Today I started by replacing line #12 in the code (see post #8) with arrays of half the size (half the number of columns).

;Global $aArray[0][0], $aArray2D = $aArray, $aBounds = [['',''],[512,32768],[1024,16384],[2048,8192],[4096,4096],[8192,2048],[16384,1024],[32768,512],[8388608, 2]]
Global $aArray[0][0], $aArray2D = $aArray, $aBounds = [['',''],[512,16384],[1024,8192],[2048,4096],[4096,2048],[8192,1024],[16384,512],[32768,2],[8388608, 1]]

After the first few tests, the impact of adding bloat was less significant than I expected.

Test # 1 : Rows = 512 : Columns = 16384 : Penalty = 2
76811.5074279989 _ArraySort($aArray2D, 0, 0, 0, 0)
18193.2968898804 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Test # 2 : Rows = 1024 : Columns = 8192 : Penalty = 2
84717.2172744297 _ArraySort($aArray2D, 0, 0, 0, 0)
18144.7808150558 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Test # 3 : Rows = 2048 : Columns = 4096 : Penalty = 2
93833.4150010339 _ArraySort($aArray2D, 0, 0, 0, 0)
19189.5574071755 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Test # 2 : Rows = 1024 : Columns = 8192 : Penalty = 8
84880.5072911176 _ArraySort($aArray2D, 0, 0, 0, 0)
17839.1749402236 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Test # 2 : Rows = 1024 : Columns = 8192 : Penalty = 16
84795.8181283365 _ArraySort($aArray2D, 0, 0, 0, 0)
17771.4004566596 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Test # 2 : Rows = 1024 : Columns = 8192 : Penalty = 32
90627.6302338924 _ArraySort($aArray2D, 0, 0, 0, 0)
21132.7072223856 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)


_ArraySort Fights Back (Finally)
The inevitable consequence of creating a large array of indices (impact on memory) can be seen when the penalty is increased.

Test # 2 : Rows = 1024 : Columns = 8192 : Penalty = 64
104398.929485705 _ArraySort($aArray2D, 0, 0, 0, 0)
110281.877706684 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Test # 5 : Rows = 8192 : Columns = 1024 : Penalty = 32
109472.45225898 _ArraySort($aArray2D, 0, 0, 0, 0)
19341.5113888217 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

Test # 5 : Rows = 8192 : Columns = 1024 : Penalty = 64
136909.819564135 _ArraySort($aArray2D, 0, 0, 0, 0)
305167.581757499 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

I strongly suspect that my meagre 2GB RAM is responsible for the drop in performance and that a more powerful machine will give very different result. The above tests (with a penalty of 64) involve arrays containing approx 562036736 bytes of string data [8192 * 1024 * (64+3)]. This may be of concern to anyone who wants to really push AutoIt to its limits. I find this quite interesting.

Edited by czardas

Share this post


Link to post
Share on other sites

#16 ·  Posted (edited)

Run as a g4 bit compiled script on         

Operating System:    Windows 10 Pro 64-bit
                         CPU:    Intel Core i7 3930K @ 3.20GHz    39 °C
                                     Sandy Bridge-E 32nm Technology
                         RAM:   16.0GB DDR3 @ 686MHz (9-9-9-27)

 

2016-05-04 21:49:20 : Test # 1 : Rows = 512 : Columns = 32768 : Penalty = 8
2016-05-04 21:50:43 : 82874.451353783 _ArraySort($aArray2D, 0, 0, 0, 0)
2016-05-04 21:51:05 : 17891.0788136815 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

2016-05-04 21:51:45 : Test # 2 : Rows = 1024 : Columns = 16384 : Penalty = 8
2016-05-04 21:53:15 : 89442.9059982006 _ArraySort($aArray2D, 0, 0, 0, 0)
2016-05-04 21:53:41 : 18227.9454162255 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

2016-05-04 21:54:27 : Test # 3 : Rows = 2048 : Columns = 8192 : Penalty = 8
2016-05-04 21:56:05 : 98350.9272928814 _ArraySort($aArray2D, 0, 0, 0, 0)
2016-05-04 21:56:35 : 17475.8334700289 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

2016-05-04 21:57:24 : Test # 4 : Rows = 4096 : Columns = 4096 : Penalty = 8
2016-05-04 21:59:09 : 105236.219224862 _ArraySort($aArray2D, 0, 0, 0, 0)
2016-05-04 21:59:42 :  17301.3922441432 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

2016-05-04 22:00:35 : Test # 5 : Rows = 8192 : Columns = 2048 : Penalty = 8
2016-05-04 22:02:26 : 110781.084877993 _ArraySort($aArray2D, 0, 0, 0, 0)
2016-05-04 22:03:04 :  17766.9943631727 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

2016-05-04 22:04:02 : Test # 6 : Rows = 16384 : Columns = 1024 : Penalty = 8
2016-05-04 22:06:03 : 120854.19835518 _ArraySort($aArray2D, 0, 0, 0, 0)
2016-05-04 22:06:45 :  18254.6572794107 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

2016-05-04 22:07:49 : Test # 7 : Rows = 32768 : Columns = 512 : Penalty = 8
2016-05-04 22:09:58 : 128907.441270622 _ArraySort($aArray2D, 0, 0, 0, 0)
2016-05-04 22:10:45 :  19264.1309021409 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

2016-05-04 22:12:10 : Test # 8 : Rows = 8388608 : Columns = 2 : Penalty = 8
2016-05-04 22:25:11 : 781343.570276423 _ArraySort($aArray2D, 0, 0, 0, 0)
2016-05-04 22:36:42 : 658688.551623695 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

 

Edited by Bowmore
1 person likes this

"Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to build bigger and better idiots. So far, the universe is winning."- Rick Cook

Share this post


Link to post
Share on other sites

#17 ·  Posted (edited)

Thanks @Bowmore (for your time) that's really helpful. I came up with this method to solve a different problem (not speed optimization per se), but the results are rather positive for arrays with more than 1 column. The trade-off comes when huge amounts of data are contained within the array - when the original function out-performs the modified version. These tests do not take into consideration the fact that RAM will also (likely) be allocated to running GUI code and other applications. Also the difference is not so great with only a few columns (perhaps double speed on average - with typical use).

Several questions remain: Is it worthwhile adding extra code to the Array UDF? If so, do we keep both versions? There are three conditions where the original function is faster:

1. Arrays with less than about ten rows (doesn't appear to be important)
2. Arrays with only one column (not yet tested)
3. Arrays containing a massive amount of data (ugh!)

I am inclined to think that bloat should generally be avoided, particularly in the UDFs included with AutoIt. On the other hand, the modified version suits me more than the original, although I don't tend to push the limits of AutoIt as much as some people do. This is where the opinions of experienced programmers out there can really help to answer these questions. My opinion alone may not lead to the best conclusion.

Edited by czardas

Share this post


Link to post
Share on other sites

#18 ·  Posted

Here my results

Test # 1 : Rows = 512 : Columns = 32768 : Penalty = 0
100.607 Sec : _ArraySort($aArray2D, 0, 0, 0, 0)
23.498 Sec : _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)
Ratio = 4.3
 
Test # 2 : Rows = 1024 : Columns = 16384 : Penalty = 0
114.401 Sec : _ArraySort($aArray2D, 0, 0, 0, 0)
23.45 Sec : _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)
Ratio = 4.9
 
Test # 4 : Rows = 4096 : Columns = 4096 : Penalty = 0
137.269 Sec : _ArraySort($aArray2D, 0, 0, 0, 0)
23.47 Sec : _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)
Ratio = 5.8
 
Test # 8 : Rows = 8388608 : Columns = 2 : Penalty = 0
1072.845 Sec : _ArraySort($aArray2D, 0, 0, 0, 0)
883.013 Sec : _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)
Ratio = 1.2
 
Just a silly question
I don't understand the lines which are for COM interference,
and also why to introduce so long sleep
Thanks for the help
1 person likes this

Share this post


Link to post
Share on other sites

#19 ·  Posted (edited)

Hi jpm, the high sleep value was me being worried that my PC might overheat. It has done so in the past, but that's partly because I'm using old hardware. I was planning on trying to create a reproducer for the COM error, but I don't know what is causing it. I just changed the first part of the code to this (functions need including of course):

#include <Array.au3>

Global $iPenalty = 0 ; [64] ; Caution: 1 penalty point = between 8 and 16 megabytes depending on the test number
Global $iFirstTest = 1 ; lowest test number = 1
Global $iLastTest = 3 ; highest test number = 8

; the following sleep values can be modified depending on available RAM
Global $iNap = 30000 ; 30 secs - short sleep
Global $iSleep = 40000 ; 40 secs - long sleep to be multiplied by the test number because each test becomes more brutal

; Bounds for 2D arrays containing 16777216 elements [Rows, Columns]
Global $aArray[0][0], $aArray2D = $aArray, $aBounds = [['',''],[512,32768],[1024,16384],[2048,8192],[4096,4096],[8192,2048],[16384,1024],[32768,512],[8388608, 2]]
;Global $aArray[0][0], $aArray2D = $aArray, $aBounds = [['',''],[512,16384],[1024,8192],[2048,4096],[4096,2048],[8192,1024],[16384,512],[32768,2],[8388608, 1]]
Global $iTimer, $sBloat = StringFormat("%0" & $iPenalty & "s", "")
;MsgBox(0, "", $sBloat)

For $iTestNum = $iFirstTest To $iLastTest
    ReDim $aArray2D[0][0] ; get rid of all previous data [COM ERROR HERE ON 1ST REPEAT ==> see line 36 below]

    ReDim $aArray2D [$aBounds[$iTestNum][0]] [$aBounds[$iTestNum][1]] ; resize the array
    GenerateHorribleData($aArray2D) ; the first two columns are filled with random strings and numbers
    AddMoreBloat($aArray2D) ; the rest array is filled with the same string duplicated again and again
    Sleep($iNap)
    ConsoleWrite("Test # " & $iTestNum & " : Rows = " & UBound($aArray2D) & " : Columns = " & UBound($aArray2D, 2) & " : Penalty = " & $iPenalty & @LF)

    ; now we are ready to run tests
    $iTimer = TimerInit()
    ; for the 1st test, sort on the first column
    _ArraySort($aArray2D, 0, 0, 0, 0)
    ConsoleWrite(TimerDiff($iTimer) & " _ArraySort($aArray2D, 0, 0, 0, 0)" & @LF)
    Sleep($iSleep * $iTestNum) ; multiplied by the test number because each test becomes more brutal

    $iTimer = TimerInit()
    ; sort similar data on the second column
    _ArraySort_NEW2($aArray2D, 0, 0, 0, 1) ; the more rows, the more similar the starting conditions [lost after the 1st sort]
    ConsoleWrite(TimerDiff($iTimer) & " _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)" & @LF & @LF)

    ;$aArray2D = $aArray ; patch to deal with the COM error above
    Sleep($iSleep * $iTestNum)
Next

After about two or three minutes I got this:

>Running:(3.3.14.2):C:\Program Files\AutoIt3\autoit3.exe "C:\Users\czardas\Documents\SortLargeTests.au3"    
--> Press Ctrl+Alt+Break to Restart or Ctrl+Break to Stop
->11:34:47 AutoIt3.exe ended.rc:1
+>11:34:48 AutoIt3Wrapper Finished.

 

Edited by czardas

Share this post


Link to post
Share on other sites

#20 ·  Posted (edited)

@jpm Oops, I forgot to change the huge penalty value back to 0. It was 64 in the last test I ran. I have changed it back to 0 and ran the test again. It only completed the first test before silently failing. I don't even know if it's the same error as in the abrupt termination above.

>Running:(3.3.14.2):C:\Program Files\AutoIt3\autoit3.exe "C:\Users\czardas\Documents\SortLargeTests.au3"    
--> Press Ctrl+Alt+Break to Restart or Ctrl+Break to Stop
Test # 1 : Rows = 512 : Columns = 32768 : Penalty = 0
188742.3367892 _ArraySort($aArray2D, 0, 0, 0, 0)
73859.7321439298 _ArraySort_NEW2($aArray2D, 0, 0, 0, 1)

->12:07:37 AutoIt3.exe ended.rc:1
+>12:07:37 AutoIt3Wrapper Finished.

Edit: If you can reproduce the same error, it may be connected to ReDim. I just intended to delete the data and reset the bounds. The alternative method I chose works fine.

Edit 2: The tests are also running fine for me (with the above code) when I halve the size of the arrays, so memory is part of the issue that I'm seeing. I thought there used to be a message - 'out of memory' or something like that. Why it would work with larger arrays when not using ReDim[0][0], but fail when including that line of code, is beyond me.

I'm running Windows 7 Pro SP1.

Edited by czardas

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now