Is _Arraysort() a wimp?

[Spiff59]

I was surprised to get a recursion level/stack overflow crash (line 1187 of array.au3) out of _ArraySort() when I'd sent it an array defined as $aFileList[60000][2].

I'm sorting on the second column using _ArraySort($aFileList, 0, 1, 0 , 1). That column contains a numeric that exists in pairs and should result in a sorted list that looks like: "1,1,2,2,3,3,4,4...".

Rather than recreate the wheel is there a more rugged _Arraysort() already out there?

One using a pseudo-queue, rather than actual recursive function calls?

I couldn't find anything in the Examples forum...

Edited February 19, 2013 by Spiff59

[BrewManNH]

I just tested _ArraySort with this script, and it didn't crash for me.

#include <array.au3>
Global  $aFileList[100000][2]
for $i = 1 to 99999
    $aFileList[$i][1] = Random(1, 30, 1)
Next
_ArraySort($aFileList, 0, 1, 0, 1)
_ArrayDisplay($aFileList)

NB_ArrayDisplay will only show the first 65000 or so items in the array, they're all in there though.

[guinness]

Not that I'm aware of, well actually I personally pass to sort.exe to overcome this very rare issue.

[water]

_ArraySort calls internal function __ArrayQuickSort2D recursively. It looks like you have hit the MAXCALLRECURSE limit of 5100.

[Melba23]

water,

This explanation shows that you are very unlikely to get to 5100.

M23

[water]

The line where the OPs script crashes is in function __ArrayQuickSort2D calling itself.

Depending on the data in the array it looks like you reach a limit and the script crashes.

Maybe Jos can shed some light on the subject because he is the author

[BrewManNH]

With the script I posted above, using 99,999 random numbers between 1 and 30, the highest recursion level I was able to get to was 17. Even changing it to 1 to 100, I still never went above 17 levels of recursion. Unless I'm doing something wrong in my calculations which is entirely possible.

expandcollapse popup

; heres the modified _ArrayQuickSort2D that I used to monitor recursion level.
Func __ArrayQuickSort2D(ByRef $avArray, ByRef $iStep, ByRef $iStart, ByRef $iEnd, ByRef $iSubItem, ByRef $iSubMax)
    If $iEnd <= $iStart Then Return
    ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $Count = ' & $Count & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console

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

        ; Swap
        If $L <= $R Then
            For $i = 0 To $iSubMax
                $vTmp = $avArray[$L][$i]
                $avArray[$L][$i] = $avArray[$R][$i]
                $avArray[$R][$i] = $vTmp
            Next
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R
    $count += 1 ; <<<<<<<<<<<<<<<<<< add one to the count variable
    __ArrayQuickSort2D($avArray, $iStep, $iStart, $R, $iSubItem, $iSubMax)
    __ArrayQuickSort2D($avArray, $iStep, $L, $iEnd, $iSubItem, $iSubMax)
    $count = 1 ; reset the count variable when it gets to the end of the function and returns normally.
EndFunc   ;==>__ArrayQuickSort2D
; I also added a Global $Count = 1 to the top of the Array.au3 file for this.

[Jos]

The recursion limits are: 3900 limit for x64 and a 1900 limit for x86 ... not the 5100 as described in the helpfile.

See:

[Jos]

Maybe Jos can shed some light on the subject because he is the author

Have you seen the date I wrote those UDF's ... and probably had help from others too

[czardas]

Things may change when you try it with longish strings.

[guinness]

The recursion limits are: 3900 limit for x64 and a 1900 limit for x86 ... not the 5100 as described in the helpfile.

See:

Can I go ahead and change the help file then? As it seems that's a msssive difference since that was added to the help file. Edited February 19, 2013 by guinness

[Jos]

Can I go ahead and change the help file then? As it seems that's a msssive difference since that was added to the help file.

Yes of course ... feel free to make the update when you can access that section of the helpfile.

Thanks

Jos

[guinness]

Yes of course ... feel free to make the update when you can access that section of the helpfile.

Thanks

Jos

I have access already.

[water]

That column contains a numeric that exists in pairs ...

What's the highest and lowest number in this column? Edited February 19, 2013 by water

[Spiff59]

Here's a demonstrator with data closer to what is in my array...

#include <array.au3>
Global $aFileList[60001][2] = [[60000, ""]]

For $i = 1 to 30000
    $aFileList[$i][0] = "FileType_A" & $i
    $aFileList[$i][1] = StringRight("00000" & $i, 6)
Next
For $i = 1 to 30000
    $aFileList[$i + 30000][0] = "FileType_B" & $i
    $aFileList[$i + 30000][1] = StringRight("00000" & $i, 6)
Next
_ArrayDisplay($aFileList)

_ArraySort($aFileList, 0, 1, 0, 1)
_ArrayDisplay($aFileList)

You'll have to kick your feet up and wait a few minutes for the crash.

Edit: Results with 3.3.8.1 or 3.3.9.4 on XP SP3

Edited February 19, 2013 by Spiff59

[BrewManNH]

Finally crashed for me.

Probably an edge case issue though, most people will never see results like this, or they'd create their own sort routine if they did.

[water]

I think you need so select another algorithm for faster/complete results.

[KaFu]

I use this function in all my programs... and no, there's not enough time to make a coffee ...

expandcollapse popup

#region _ArraySortClib
#include <memory.au3>
Global $h_DLL_user32 = DllOpen("user32.dll")
Global $h_DLL_msvcrt = DllOpen("msvcrt.dll")
Global $h_DLL_Kernel32 = DllOpen("kernel32.dll")

Global $pEnumProc_ArraySortClib_Mem1 = _MemVirtualAlloc(0, 64, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE) ; needed for _ArraySortClib()
Global $pEnumProc_ArraySortClib_Mem2 = _MemVirtualAlloc(0, 64, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE) ; needed for _ArraySortClib()
Global $pEnumProc_ArraySortClib_Mem3 = _MemVirtualAlloc(0, 36, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE) ; needed for _ArraySortClib()
OnAutoItExitRegister("ArraySortClib_Mem_Release")
Func ArraySortClib_Mem_Release()
_MemVirtualFree($pEnumProc_ArraySortClib_Mem1, 0, $MEM_RELEASE) ; release mem reserved for _ArraySortClib()
_MemVirtualFree($pEnumProc_ArraySortClib_Mem2, 0, $MEM_RELEASE) ; release mem reserved for _ArraySortClib()
_MemVirtualFree($pEnumProc_ArraySortClib_Mem3, 0, $MEM_RELEASE) ; release mem reserved for _ArraySortClib()
DllClose($h_DLL_user32)
DllClose($h_DLL_msvcrt)
DllClose($h_DLL_Kernel32)
EndFunc ;==>ArraySortClib_Mem_Release
#endregion _ArraySortClib



#include <array.au3> ; not needed for _ArraySortClib() itself, only for example
Global $aFileList[60001][2] = [[60000, ""]]

$timer = TimerInit()
For $i = 1 To 30000
$aFileList[$i][0] = "FileType_A" & $i
$aFileList[$i][1] = StringRight("00000" & $i, 6)
Next
For $i = 1 To 30000
$aFileList[$i + 30000][0] = "FileType_B" & $i
$aFileList[$i + 30000][1] = StringRight("00000" & $i, 6)
Next
ConsoleWrite(TimerDiff($timer) & @CRLF)

$timer = TimerInit()
_ArrayDisplay($aFileList)
ConsoleWrite(TimerDiff($timer) & @CRLF)

; _ArraySort($aFileList, 0, 1, 0, 1)
$timer = TimerInit()
_ArraySortClib($aFileList, 1, 0, 0, 0, 1)
ConsoleWrite(TimerDiff($timer) & @CRLF)

$timer = TimerInit()
_ArrayDisplay($aFileList)
ConsoleWrite(TimerDiff($timer) & @CRLF)



; http://www.autoitscript.com/forum/index.php?showtopic=63525&view=findpost&p=474072
;===============================================================================
; Function Name: _ArraySortClib() v4
; Description:       Sort 1D/2D array using qsort() from C runtime library
; Syntax:
; Parameter(s):  $Array - the array to be sorted, ByRef
;                $iMode - sort mode, can be one of the following:
;                    0 = numerical, using double precision float compare
;                    1 = string sort, case insensitive (default)
;                    2 = string sort, case sensitive
;                    3 = word sort, case insensitive - compatible with AutoIt's native compare
;                $fDescend - sort direction. True = descending, False = ascending (default)
;                $iStart - index of starting element (default 0 = $array[0])
;                $iEnd - index of ending element (default 0 = Ubound($array)-1)
;                $iColumn - index of column to sort by (default 0 = first column)
;                $iStrMax - max string length of each array element to compare (default 4095 chars)
; Requirement(s): msvcrt.dll (shipped with Windows since Win98 at least), 32-bit version of AutoIt
; Return Value(s): Success = Returns 1
;                Failure = Returns 0 and sets error:
;                    @error 1 = invalid array
;                    @error 2 = invalid param
;                    @error 3 = dll error
;                    @error 64 = 64-bit AutoIt unsupported
; Author(s): Siao
; Modification(s): KaFu, added three global _MemVirtualAlloc() calls to top of script to prevent DEP Errors:
;
; Global $pEnumProc_ArraySortClib_Mem1 = _MemVirtualAlloc(0, 64, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE) ; needed for _ArraySortClib()
; Global $pEnumProc_ArraySortClib_Mem2 = _MemVirtualAlloc(0, 64, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE) ; needed for _ArraySortClib()
; Global $pEnumProc_ArraySortClib_Mem3 = _MemVirtualAlloc(0, 36, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE) ; needed for _ArraySortClib()
;
;===============================================================================

Func _ArraySortClib(ByRef $array, $iMode = 1, $fDescend = False, $iStart = 0, $iEnd = 0, $iColumn = 0, $iStrMax = 4095)
If @AutoItX64 Then Return SetError(64, 0, 0)
Local $iArrayDims = UBound($array, 0)
If @error Or $iArrayDims > 2 Then Return SetError(1, 0, 0)
Local $iArraySize = UBound($array, 1), $iColumnMax = UBound($array, 2)
If $iArraySize < 2 Then Return SetError(1, 0, 0)
If $iEnd < 1 Or $iEnd > $iArraySize - 1 Then $iEnd = $iArraySize - 1
If ($iEnd - $iStart < 1) Then
; ConsoleWrite("- _ArraySortClib ERROR: #1 - " & ($iEnd - $iStart < 1) & @tab & ($iEnd - $iStart) & @crlf)
Return SetError(2, 0, 0)
EndIf
If $iArrayDims = 2 And ($iColumnMax - $iColumn < 0) Then
; ConsoleWrite("- _ArraySortClib ERROR: #2 - " & $iArrayDims & @tab & ($iColumnMax - $iColumn < 0) & @tab & ($iColumnMax - $iColumn) & @crlf)
Return SetError(2, 0, 0)
EndIf
If $iStrMax < 1 Then
; ConsoleWrite("- _ArraySortClib ERROR: #3 - " & $iStrMax & @crlf)
Return SetError(2, 0, 0)
EndIf
Local $i, $j, $iCount = $iEnd - $iStart + 1, $fNumeric, $aRet, $sZero = ChrW(0), $sStrCmp, $sBufType = 'byte[', $tSource, $tIndex, $tFloatCmp

Local $tEnumProc = DllStructCreate('byte[64]', $pEnumProc_ArraySortClib_Mem1)
Local $tCmpWrap = DllStructCreate('byte[64]', $pEnumProc_ArraySortClib_Mem2)

If $h_DLL_msvcrt = -1 Then Return SetError(3, 0, 0)

;; initialize compare proc
Switch $iMode
Case 0
$fNumeric = True
$tFloatCmp = DllStructCreate('byte[36]', $pEnumProc_ArraySortClib_Mem3)
DllStructSetData($tFloatCmp, 1, '0x8B4C24048B542408DD01DC1ADFE0F6C440750D80E441740433C048C333C040C333C0C3')
DllStructSetData($tCmpWrap, 1, '0xBA' & Hex(Binary(DllStructGetPtr($tFloatCmp)), 8) & '8B4424088B4C2404FF30FF31FFD283C408C3')
DllStructSetData($tEnumProc, 1, '0x8B7424048B7C24088B4C240C8B442410893789470483C60883C708404975F1C21000')
Case 1, 2
$sStrCmp = "_strcmpi" ;case insensitive
If $iMode = 2 Then $sStrCmp = "strcmp" ;case sensitive
$aRet = DllCall($h_DLL_Kernel32, 'ptr', 'GetModuleHandle', 'str', 'msvcrt.dll')
$aRet = DllCall($h_DLL_Kernel32, 'ptr', 'GetProcAddress', 'ptr', $aRet[0], 'str', $sStrCmp)
;If $aRet[0] = 0 Then Return SetError(3, 0, 0 * DllClose($h_DLL_msvcrt))
If $aRet[0] = 0 Then Return SetError(3, 0, 1)
DllStructSetData($tCmpWrap, 1, '0xBA' & Hex(Binary($aRet[0]), 8) & '8B4424088B4C2404FF30FF31FFD283C408C3')
DllStructSetData($tEnumProc, 1, '0x8B7424048B7C24088B4C240C8B542410893789570483C7088A064684C075F9424975EDC21000')
Case 3
$sBufType = 'wchar['
$aRet = DllCall($h_DLL_Kernel32, 'ptr', 'GetModuleHandle', 'str', 'kernel32.dll')
$aRet = DllCall($h_DLL_Kernel32, 'ptr', 'GetProcAddress', 'ptr', $aRet[0], 'str', 'CompareStringW')
;If $aRet[0] = 0 Then Return SetError(3, 0, 0 * DllClose($h_DLL_msvcrt))
If $aRet[0] = 0 Then Return SetError(3, 0, 1)
DllStructSetData($tCmpWrap, 1, '0xBA' & Hex(Binary($aRet[0]), 8) & '8B4424088B4C24046AFFFF306AFFFF3168000000006800040000FFD283E802C3')
DllStructSetData($tEnumProc, 1, '0x8B7424048B7C24088B4C240C8B542410893789570483C7080FB70683C60285C075F6424975EAC21000')
Case Else

Return SetError(2, 0, 0)
EndSwitch
;; write data to memory
If $fNumeric Then
$tSource = DllStructCreate('double[' & $iCount & ']')
If $iArrayDims = 1 Then
For $i = 1 To $iCount
DllStructSetData($tSource, 1, $array[$iStart + $i - 1], $i)
Next
Else
For $i = 1 To $iCount
DllStructSetData($tSource, 1, $array[$iStart + $i - 1][$iColumn], $i)
Next
EndIf
Else
Local $sMem = ""
If $iArrayDims = 1 Then
For $i = $iStart To $iEnd
$sMem &= StringLeft($array[$i], $iStrMax) & $sZero
Next
Else
For $i = $iStart To $iEnd
$sMem &= StringLeft($array[$i][$iColumn], $iStrMax) & $sZero
Next
EndIf
$tSource = DllStructCreate($sBufType & StringLen($sMem) + 1 & ']')
DllStructSetData($tSource, 1, $sMem)
$sMem = ""
EndIf
;; index data
$tIndex = DllStructCreate('int[' & $iCount * 2 & ']')
DllCall($h_DLL_user32, 'uint', 'CallWindowProc', 'ptr', DllStructGetPtr($tEnumProc), 'ptr', DllStructGetPtr($tSource), 'ptr', DllStructGetPtr($tIndex), 'int', $iCount, 'int', $iStart)
;; sort
DllCall($h_DLL_msvcrt, 'none:cdecl', 'qsort', 'ptr', DllStructGetPtr($tIndex), 'int', $iCount, 'int', 8, 'ptr', DllStructGetPtr($tCmpWrap))
;DllClose($h_DLL_msvcrt)
;; rearrange the array by sorted index
Local $aTmp = $array, $iRef
If $iArrayDims = 1 Then ; 1D
If $fDescend Then
For $i = 0 To $iCount - 1
$iRef = DllStructGetData($tIndex, 1, $i * 2 + 2)
$array[$iEnd - $i] = $aTmp[$iRef]
Next
Else ; ascending
For $i = $iStart To $iEnd
$iRef = DllStructGetData($tIndex, 1, ($i - $iStart) * 2 + 2)
$array[$i] = $aTmp[$iRef]
Next
EndIf
Else ; 2D
If $fDescend Then
For $i = 0 To $iCount - 1
$iRef = DllStructGetData($tIndex, 1, $i * 2 + 2)
For $j = 0 To $iColumnMax - 1
$array[$iEnd - $i][$j] = $aTmp[$iRef][$j]
Next
Next
Else ; ascending
For $i = $iStart To $iEnd
$iRef = DllStructGetData($tIndex, 1, ($i - $iStart) * 2 + 2)
For $j = 0 To $iColumnMax - 1
$array[$i][$j] = $aTmp[$iRef][$j]
Next
Next
EndIf
EndIf
Return 1
EndFunc ;==>_ArraySortClib

Edit: Added some timers, the lagging part now is the _ArrayDisplay(), the sorting of the 60.000 2D elements itself takes ~750ms on my computer .

Edited February 19, 2013 by KaFu

[Spiff59]

I don't consider the data I'm feeding it to be exotic in any way.

Asking it to sort on a field containing "00001" through "60000" with dupes seems pretty straightforward.

Perhaps _ArraySort() should adopt a new algorithm?

typo

Edit2: @KaFu Works very nicely! I'll insert that code. Thanks.

Edited February 19, 2013 by Spiff59

[Spiff59]

I use this function in all my programs... and no, there's not enough time to make a coffee ...

Is yours based upon an older version than the one at the top of this thread: ?

Or is it a refined/improved version?

Using it as a simple UDF without the #region data seems the easiest to implement...