czardas Posted May 10, 2016 Author Posted May 10, 2016 (edited) I have this funny habit of inventing things that have already been invented. Some internal functions could be renamed eg. __ArrayTagSort2D(), Here's a first redraft of the help file description. I've only included sections where changes would be required. What do you think? Description: Sort a 1D or 2D array on a specific index using the dualpivotsort/quicksort/insertionsort/tagsort algorithms Syntax: _ArraySort ( ByRef $aArray [, $iDescending = 0 [, $iStart = 0 [, $iEnd = 0 [, $iSubItem = 0 [, $iAlgorithm = 0]]]]] ) Parameters: $iAlgorithm - [optional] Use dual-pivot sort for 1D arrays, or tag sort for 2D arrays (default = quicksort) Comments: By default the UDF uses a QuickSort algorithm to sort the array. Setting the $iAlgorithm parameter uses dual-pivot sort with 1D arrays, and tag sort with 2D arrays. Dual-pivot sort can be significantly faster for large arrays (> 50 elements) and tag sort can be significantly faster for arrays with a large number of columns. The tag sort method uses more memory and may be less suitable for sorting large arrays on a less powerful machine (depends on the amount of bloat). With tag sort and 1D algorithms, relatively short arrays will be sorted using an insertion sort (< 15 elements/rows with Quick Sort and Tag Sort; < 45 elements with Dual-Pivot Sort). Note that there is no guarantee that a specific algorithm will be faster in any given case. Needs Removing: @error = 6 - $iPivot used with 2D array Edited May 10, 2016 by czardas grammar operator64 ArrayWorkshop
Moderators Melba23 Posted May 10, 2016 Moderators Posted May 10, 2016 czardas, Great minds..... Here is the suggested Help file text I have been working in this morning: $iAlternate [optional] 1D array sorted with PivotSort algorithm 2D array sorted with TagSort algorithm Default: both sorted with QuickSort algorithm Return Value Success: 1. Failure: 0 and sets the @error flag to non-zero. @error: 1 - $aArray is not an array 2 - $iStart is greater than $iEnd 3 - $iSubItem is greater than subitem count 4 - $aArray is not a 1D or 2D array 5 - $aArray is empty 6 - Deprecated Remarks By default the UDF uses a QuickSort algorithm to sort both 1D and 2D arrays. For 1D arrays setting the $iAlternate parameter uses a DualPivotSort algorithm - this can be significantly faster for large arrays (> 50 elements). In both algorithms, relatively short arrays will be sorted using an insertion sort (< 15 elements with QuickSort; < 45 elements with Dual PivotSort). For 2D arrays setting the $iAlternate parameter uses a TagSort algorithm - this is considerably faster when dealing with multiple columns. However, this algoritm uses more memory and may not be suitable for large arrays on less powerful machines. Note that there is no guarantee that a specific algorithm will be faster in a given case. And my suggested recode of the _ArraySort functions: expandcollapse popup#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_NEW(ByRef $aArray, $iDescending = 0, $iStart = 0, $iEnd = 0, $iSubItem = 0, $iAlternate = 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 $iAlternate = Default Then $iAlternate = 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 $iAlternate = Default Then $iAlternate = 0 If $iSubItem = Default Then $iSubItem = 0 ; Sort Switch UBound($aArray, $UBOUND_DIMENSIONS) Case 1 If $iAlternate Then ; Use PivotSort algorithm __ArrayDualPivotSort1D_New($aArray, $iStart, $iEnd) Else __ArrayQuickSort1D_New($aArray, $iStart, $iEnd) EndIf If $iDescending Then _ArrayReverse($aArray, $iStart, $iEnd) Case 2 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 If $iAlternate Then ; Use TagSort algorithm Local $aTrac[$iUBound +1] For $i = $iStart To $iEnd $aTrac[$i] = $i Next __ArrayTagSort2D($aArray, $aTrac, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax) __ArrayTagSort2D_SwapSeq($aArray, $aTrac, $iStart, $iEnd) Else __ArrayQuickSort2D($aArray, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax) EndIf Case Else Return SetError(4, 0, 0) EndSwitch Return 1 EndFunc ;==>_ArraySort ; 1D Sort helper functions Func __ArrayQuickSort1D_New(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd) If $iEnd <= $iStart Then Return Local $vTmp ; InsertionSort used for small arrays - value chosen empirically If ($iEnd - $iStart) < 15 Then __ArrayInsertSort1D($aArray, $iStart, $iEnd) Return EndIf ; QuickSort Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[Int(($iStart + $iEnd) / 2)], $bNum = IsNumber($vPivot) Do If $bNum Then While ($aArray[$L] < $vPivot And IsNumber($aArray[$L])) Or (Not IsNumber($aArray[$L]) And StringCompare($aArray[$L], $vPivot) < 0) $L += 1 WEnd While ($aArray[$R] > $vPivot And IsNumber($aArray[$R])) Or (Not IsNumber($aArray[$R]) And StringCompare($aArray[$R], $vPivot) > 0) $R -= 1 WEnd Else While (StringCompare($aArray[$L], $vPivot) < 0) $L += 1 WEnd While (StringCompare($aArray[$R], $vPivot) > 0) $R -= 1 WEnd EndIf ; Swap If $L <= $R Then $vTmp = $aArray[$L] $aArray[$L] = $aArray[$R] $aArray[$R] = $vTmp $L += 1 $R -= 1 EndIf Until $L > $R __ArrayQuickSort1D($aArray, $iStart, $R) __ArrayQuickSort1D($aArray, $L, $iEnd) EndFunc ;==>__ArrayQuickSort1D Func __ArrayDualPivotSort1D_New(ByRef $aArray, $iPivot_Left, $iPivot_Right) If $iPivot_Left > $iPivot_Right Then Return Local $iLength = $iPivot_Right - $iPivot_Left + 1 ;Local $i, $j, $k, $iAi, $iAk, $iA1, $iA2, $iLast Local $k ; InsertionSort used for small arrays - value chosen empirically If $iLength < 45 Then __ArrayInsertSort1D($aArray, $iPivot_Left, $iPivot_Right) Return EndIf ; PivotSort Local $iSeventh = BitShift($iLength, 3) + BitShift($iLength, 6) + 1 Local $iE1, $iE2, $iE3, $iE4, $iE5, $t $iE3 = Ceiling(($iPivot_Left + $iPivot_Right) / 2) $iE2 = $iE3 - $iSeventh $iE1 = $iE2 - $iSeventh $iE4 = $iE3 + $iSeventh $iE5 = $iE4 + $iSeventh If $aArray[$iE2] < $aArray[$iE1] Then $t = $aArray[$iE2] $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf If $aArray[$iE3] < $aArray[$iE2] Then $t = $aArray[$iE3] $aArray[$iE3] = $aArray[$iE2] $aArray[$iE2] = $t If $t < $aArray[$iE1] Then $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf EndIf If $aArray[$iE4] < $aArray[$iE3] Then $t = $aArray[$iE4] $aArray[$iE4] = $aArray[$iE3] $aArray[$iE3] = $t If $t < $aArray[$iE2] Then $aArray[$iE3] = $aArray[$iE2] $aArray[$iE2] = $t If $t < $aArray[$iE1] Then $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf EndIf EndIf If $aArray[$iE5] < $aArray[$iE4] Then $t = $aArray[$iE5] $aArray[$iE5] = $aArray[$iE4] $aArray[$iE4] = $t If $t < $aArray[$iE3] Then $aArray[$iE4] = $aArray[$iE3] $aArray[$iE3] = $t If $t < $aArray[$iE2] Then $aArray[$iE3] = $aArray[$iE2] $aArray[$iE2] = $t If $t < $aArray[$iE1] Then $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf EndIf EndIf EndIf Local $iLess = $iPivot_Left Local $iGreater = $iPivot_Right If (($aArray[$iE1] <> $aArray[$iE2]) And ($aArray[$iE2] <> $aArray[$iE3]) And ($aArray[$iE3] <> $aArray[$iE4]) And ($aArray[$iE4] <> $aArray[$iE5])) Then Local $iPivot_1 = $aArray[$iE2] Local $iPivot_2 = $aArray[$iE4] $aArray[$iE2] = $aArray[$iPivot_Left] $aArray[$iE4] = $aArray[$iPivot_Right] Do $iLess += 1 Until $aArray[$iLess] >= $iPivot_1 Do $iGreater -= 1 Until $aArray[$iGreater] <= $iPivot_2 $k = $iLess Local $iAk While $k <= $iGreater $iAk = $aArray[$k] If $iAk < $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iAk $iLess += 1 ElseIf $iAk > $iPivot_2 Then While $aArray[$iGreater] > $iPivot_2 $iGreater -= 1 If $iGreater + 1 = $k Then ExitLoop 2 WEnd If $aArray[$iGreater] < $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $aArray[$iGreater] $iLess += 1 Else $aArray[$k] = $aArray[$iGreater] EndIf $aArray[$iGreater] = $iAk $iGreater -= 1 EndIf $k += 1 WEnd $aArray[$iPivot_Left] = $aArray[$iLess - 1] $aArray[$iLess - 1] = $iPivot_1 $aArray[$iPivot_Right] = $aArray[$iGreater + 1] $aArray[$iGreater + 1] = $iPivot_2 __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 2) __ArrayDualPivotSort1D_New($aArray, $iGreater + 2, $iPivot_Right) If ($iLess < $iE1) And ($iE5 < $iGreater) Then While $aArray[$iLess] = $iPivot_1 $iLess += 1 WEnd While $aArray[$iGreater] = $iPivot_2 $iGreater -= 1 WEnd $k = $iLess While $k <= $iGreater $iAk = $aArray[$k] If $iAk = $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iAk $iLess += 1 ElseIf $iAk = $iPivot_2 Then While $aArray[$iGreater] = $iPivot_2 $iGreater -= 1 If $iGreater + 1 = $k Then ExitLoop 2 WEnd If $aArray[$iGreater] = $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iPivot_1 $iLess += 1 Else $aArray[$k] = $aArray[$iGreater] EndIf $aArray[$iGreater] = $iAk $iGreater -= 1 EndIf $k += 1 WEnd EndIf __ArrayDualPivotSort1D_New($aArray, $iLess, $iGreater) Else Local $iPivot = $aArray[$iE3] $k = $iLess While $k <= $iGreater If $aArray[$k] = $iPivot Then $k += 1 ContinueLoop EndIf $iAk = $aArray[$k] If $iAk < $iPivot Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iAk $iLess += 1 Else While $aArray[$iGreater] > $iPivot $iGreater -= 1 WEnd If $aArray[$iGreater] < $iPivot Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $aArray[$iGreater] $iLess += 1 Else $aArray[$k] = $iPivot EndIf $aArray[$iGreater] = $iAk $iGreater -= 1 EndIf $k += 1 WEnd __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 1) __ArrayDualPivotSort1D_New($aArray, $iGreater + 1, $iPivot_Right) EndIf EndFunc ;==>__ArrayDualPivotSort1D Func __ArrayInsertSort1D(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd) Local $vCur, $vTmp For $i = $iStart + 1 To $iEnd $vTmp = $aArray[$i] If IsNumber($vTmp) Then For $j = $i - 1 To $iStart Step -1 $vCur = $aArray[$j] If ($vTmp >= $vCur And IsNumber($vCur)) Or (Not IsNumber($vCur) And StringCompare($vTmp, $vCur) >= 0) Then ExitLoop $aArray[$j + 1] = $vCur Next Else For $j = $i - 1 To $iStart Step -1 If (StringCompare($vTmp, $aArray[$j]) >= 0) Then ExitLoop $aArray[$j + 1] = $aArray[$j] Next EndIf $aArray[$j + 1] = $vTmp Next EndFunc ; 2D Sort helper functions ; Existing __ArrayQuickSort2D Func __ArrayTagSort2D(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 $vTmp ; InsertionSort (faster for smaller segments) If ($iEnd - $iStart) < 1 Then ; Force tagsort For $i = $iStart + 1 To $iEnd $vTmp = $aTrac[$i] If IsNumber($aArray[$vTmp][$iSubItem]) Then For $j = $i - 1 To $iStart Step -1 If ((($aArray[$vTmp][$iSubItem] >= $aArray[$aTrac[$j]][$iSubItem] And $iStep = 1) Or $aArray[$vTmp][$iSubItem] <= $aArray[$aTrac[$j]][$iSubItem]) And IsNumber($aArray[$aTrac[$j]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$j]][$iSubItem]) And StringCompare($aArray[$vTmp][$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[$vTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop $aTrac[$j + 1] = $aTrac[$j] Next EndIf $aTrac[$j + 1] = $vTmp Next Return EndIf ; TagSort Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[$aTrac[Int(($iStart + $iEnd) / 2)]][$iSubItem], $bNum = IsNumber($vPivot) Do If $bNum Then 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[$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 If $L <= $R Then ; Swap $vTmp = $aTrac[$L] $aTrac[$L] = $aTrac[$R] $aTrac[$R] = $vTmp $L += 1 $R -= 1 EndIf Until $L > $R __ArrayTagSort2D($aArray, $aTrac, $iStep, $iStart, $R, $iSubItem, $iSubMax) __ArrayTagSort2D($aArray, $aTrac, $iStep, $L, $iEnd, $iSubItem, $iSubMax) EndFunc ;==>__ArrayQuickSort2D_NEW2 Func __ArrayTagSort2D_SwapSeq(ByRef $aArray, ByRef $aTrac, Const ByRef $iStart, Const ByRef $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 ;==> __ArrayTagSort2D_SwapSeq Other than the insertion of your TagSort code, the main change is that I have extracted the insertionSort sections in both the __ArrayQuickSort1D_New & __ArrayDualPivotSort1D_New functions into a separate function - you may remember that we found that the existing InsertionSort code in the PivotSort algorithm gave erroneous results for empty elements. As the solution was to use the same code for both, it seemed logical to have it just the once. M23 Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind Open spoiler to see my UDFs: Spoiler ArrayMultiColSort ---- Sort arrays on multiple columnsChooseFileFolder ---- Single and multiple selections from specified path treeview listingDate_Time_Convert -- Easily convert date/time formats, including the language usedExtMsgBox --------- A highly customisable replacement for MsgBoxGUIExtender -------- Extend and retract multiple sections within a GUIGUIFrame ---------- Subdivide GUIs into many adjustable framesGUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView itemsGUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeViewMarquee ----------- Scrolling tickertape GUIsNoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxesNotify ------------- Small notifications on the edge of the displayScrollbars ----------Automatically sized scrollbars with a single commandStringSize ---------- Automatically size controls to fit textToast -------------- Small GUIs which pop out of the notification area
czardas Posted May 10, 2016 Author Posted May 10, 2016 (edited) Ha that's funny: our descriptions are almost identical. It all looks fine to me, although I haven't tested anything yet. I do remember the thread you mentioned. Edit: Some checks appear duplicated - I removed them earlier. ; 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 $iAlternate = Default Then $iAlternate = 0 ;If $iSubItem = Default Then $iSubItem = 0 @Melba23 See my edit here. Edited May 10, 2016 by czardas operator64 ArrayWorkshop
czardas Posted May 10, 2016 Author Posted May 10, 2016 (edited) Maybe you could also change this ; czardas - speed optimization for 2D arrays to this ; czardas - implemented tag sort And this line If $iAlternate Then ; Use TagSort algorithm to this If $iAlternate And $iSubMax Then ; Use TagSort algorithm because tag sort will always be slower with only 1 column ($iSubMax = 0). Edited May 10, 2016 by czardas operator64 ArrayWorkshop
czardas Posted February 5, 2018 Author Posted February 5, 2018 (edited) The inclusion of Tag Sort (for 2D arrays) could do with more testing, if any of you can give this a try. It may be added to the next beta, so please could some of you try this. I have been using it for quite a while already without problems. @Melba23 I reverted the two changes we discussed earlier. I haven't looked at any of the code for __ArrayDualPivotSort1D_New(). I'm assuming it is the same as for the current release, unless you changed something else. $iAlternate [optional] 1D array sorted with PivotSort algorithm 2D array sorted with TagSort algorithm Default: both sorted with QuickSort algorithm Return Value Success: 1. Failure: 0 and sets the @error flag to non-zero. @error: 1 - $aArray is not an array 2 - $iStart is greater than $iEnd 3 - $iSubItem is greater than subitem count 4 - $aArray is not a 1D or 2D array 5 - $aArray is empty 6 - Deprecated Remarks By default the UDF uses a QuickSort algorithm to sort both 1D and 2D arrays. For 1D arrays setting the $iAlternate parameter uses a DualPivotSort algorithm - this can be significantly faster for large arrays (> 50 elements). In each algorithm, relatively short arrays will be sorted using an insertion sort (< 15 elements with QuickSort and TagSort; < 45 elements with Dual PivotSort). For 2D arrays setting the $iAlternate parameter uses a TagSort algorithm - this is considerably faster when dealing with multiple columns. However, this algoritm uses more memory and may not be suitable for large arrays on less powerful machines. Note that there is no guarantee that a specific algorithm will be faster in a given case. CODE: - CONTAINS A BUG (fixed in post #52 below) expandcollapse popup#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 - implemented TagSort ; =============================================================================================================================== Func _ArraySort_NEW(ByRef $aArray, $iDescending = 0, $iStart = 0, $iEnd = 0, $iSubItem = 0, $iAlternate = 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 $iAlternate = Default Then $iAlternate = 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 < 1 Or $iEnd > $iUBound Then $iEnd = $iUBound If $iStart < 0 Then $iStart = 0 If $iStart > $iEnd Then Return SetError(2, 0, 0) ; Sort Switch UBound($aArray, $UBOUND_DIMENSIONS) Case 1 If $iAlternate Then ; Use PivotSort algorithm __ArrayDualPivotSort1D_New($aArray, $iStart, $iEnd) Else __ArrayQuickSort1D_New($aArray, $iStart, $iEnd) EndIf If $iDescending Then _ArrayReverse($aArray, $iStart, $iEnd) Case 2 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 If $iAlternate And $iSubMax Then ; Use TagSort algorithm Local $aTrac[$iUBound +1] For $i = $iStart To $iEnd $aTrac[$i] = $i Next __ArrayTagSort2D($aArray, $aTrac, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax) __ArrayTagSort2D_SwapSeq($aArray, $aTrac, $iStart, $iEnd) Else __ArrayQuickSort2D($aArray, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax) EndIf Case Else Return SetError(4, 0, 0) EndSwitch Return 1 EndFunc ;==>_ArraySort ; 1D Sort helper functions Func __ArrayQuickSort1D_New(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd) If $iEnd <= $iStart Then Return Local $vTmp ; InsertionSort used for small arrays - value chosen empirically If ($iEnd - $iStart) < 15 Then __ArrayInsertSort1D($aArray, $iStart, $iEnd) Return EndIf ; QuickSort Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[Int(($iStart + $iEnd) / 2)], $bNum = IsNumber($vPivot) Do If $bNum Then While ($aArray[$L] < $vPivot And IsNumber($aArray[$L])) Or (Not IsNumber($aArray[$L]) And StringCompare($aArray[$L], $vPivot) < 0) $L += 1 WEnd While ($aArray[$R] > $vPivot And IsNumber($aArray[$R])) Or (Not IsNumber($aArray[$R]) And StringCompare($aArray[$R], $vPivot) > 0) $R -= 1 WEnd Else While (StringCompare($aArray[$L], $vPivot) < 0) $L += 1 WEnd While (StringCompare($aArray[$R], $vPivot) > 0) $R -= 1 WEnd EndIf ; Swap If $L <= $R Then $vTmp = $aArray[$L] $aArray[$L] = $aArray[$R] $aArray[$R] = $vTmp $L += 1 $R -= 1 EndIf Until $L > $R __ArrayQuickSort1D($aArray, $iStart, $R) __ArrayQuickSort1D($aArray, $L, $iEnd) EndFunc ;==>__ArrayQuickSort1D Func __ArrayDualPivotSort1D_New(ByRef $aArray, $iPivot_Left, $iPivot_Right) If $iPivot_Left > $iPivot_Right Then Return Local $iLength = $iPivot_Right - $iPivot_Left + 1 ;Local $i, $j, $k, $iAi, $iAk, $iA1, $iA2, $iLast Local $k ; InsertionSort used for small arrays - value chosen empirically If $iLength < 45 Then __ArrayInsertSort1D($aArray, $iPivot_Left, $iPivot_Right) Return EndIf ; PivotSort Local $iSeventh = BitShift($iLength, 3) + BitShift($iLength, 6) + 1 Local $iE1, $iE2, $iE3, $iE4, $iE5, $t $iE3 = Ceiling(($iPivot_Left + $iPivot_Right) / 2) $iE2 = $iE3 - $iSeventh $iE1 = $iE2 - $iSeventh $iE4 = $iE3 + $iSeventh $iE5 = $iE4 + $iSeventh If $aArray[$iE2] < $aArray[$iE1] Then $t = $aArray[$iE2] $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf If $aArray[$iE3] < $aArray[$iE2] Then $t = $aArray[$iE3] $aArray[$iE3] = $aArray[$iE2] $aArray[$iE2] = $t If $t < $aArray[$iE1] Then $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf EndIf If $aArray[$iE4] < $aArray[$iE3] Then $t = $aArray[$iE4] $aArray[$iE4] = $aArray[$iE3] $aArray[$iE3] = $t If $t < $aArray[$iE2] Then $aArray[$iE3] = $aArray[$iE2] $aArray[$iE2] = $t If $t < $aArray[$iE1] Then $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf EndIf EndIf If $aArray[$iE5] < $aArray[$iE4] Then $t = $aArray[$iE5] $aArray[$iE5] = $aArray[$iE4] $aArray[$iE4] = $t If $t < $aArray[$iE3] Then $aArray[$iE4] = $aArray[$iE3] $aArray[$iE3] = $t If $t < $aArray[$iE2] Then $aArray[$iE3] = $aArray[$iE2] $aArray[$iE2] = $t If $t < $aArray[$iE1] Then $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf EndIf EndIf EndIf Local $iLess = $iPivot_Left Local $iGreater = $iPivot_Right If (($aArray[$iE1] <> $aArray[$iE2]) And ($aArray[$iE2] <> $aArray[$iE3]) And ($aArray[$iE3] <> $aArray[$iE4]) And ($aArray[$iE4] <> $aArray[$iE5])) Then Local $iPivot_1 = $aArray[$iE2] Local $iPivot_2 = $aArray[$iE4] $aArray[$iE2] = $aArray[$iPivot_Left] $aArray[$iE4] = $aArray[$iPivot_Right] Do $iLess += 1 Until $aArray[$iLess] >= $iPivot_1 Do $iGreater -= 1 Until $aArray[$iGreater] <= $iPivot_2 $k = $iLess Local $iAk While $k <= $iGreater $iAk = $aArray[$k] If $iAk < $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iAk $iLess += 1 ElseIf $iAk > $iPivot_2 Then While $aArray[$iGreater] > $iPivot_2 $iGreater -= 1 If $iGreater + 1 = $k Then ExitLoop 2 WEnd If $aArray[$iGreater] < $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $aArray[$iGreater] $iLess += 1 Else $aArray[$k] = $aArray[$iGreater] EndIf $aArray[$iGreater] = $iAk $iGreater -= 1 EndIf $k += 1 WEnd $aArray[$iPivot_Left] = $aArray[$iLess - 1] $aArray[$iLess - 1] = $iPivot_1 $aArray[$iPivot_Right] = $aArray[$iGreater + 1] $aArray[$iGreater + 1] = $iPivot_2 __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 2) __ArrayDualPivotSort1D_New($aArray, $iGreater + 2, $iPivot_Right) If ($iLess < $iE1) And ($iE5 < $iGreater) Then While $aArray[$iLess] = $iPivot_1 $iLess += 1 WEnd While $aArray[$iGreater] = $iPivot_2 $iGreater -= 1 WEnd $k = $iLess While $k <= $iGreater $iAk = $aArray[$k] If $iAk = $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iAk $iLess += 1 ElseIf $iAk = $iPivot_2 Then While $aArray[$iGreater] = $iPivot_2 $iGreater -= 1 If $iGreater + 1 = $k Then ExitLoop 2 WEnd If $aArray[$iGreater] = $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iPivot_1 $iLess += 1 Else $aArray[$k] = $aArray[$iGreater] EndIf $aArray[$iGreater] = $iAk $iGreater -= 1 EndIf $k += 1 WEnd EndIf __ArrayDualPivotSort1D_New($aArray, $iLess, $iGreater) Else Local $iPivot = $aArray[$iE3] $k = $iLess While $k <= $iGreater If $aArray[$k] = $iPivot Then $k += 1 ContinueLoop EndIf $iAk = $aArray[$k] If $iAk < $iPivot Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iAk $iLess += 1 Else While $aArray[$iGreater] > $iPivot $iGreater -= 1 WEnd If $aArray[$iGreater] < $iPivot Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $aArray[$iGreater] $iLess += 1 Else $aArray[$k] = $iPivot EndIf $aArray[$iGreater] = $iAk $iGreater -= 1 EndIf $k += 1 WEnd __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 1) __ArrayDualPivotSort1D_New($aArray, $iGreater + 1, $iPivot_Right) EndIf EndFunc ;==>__ArrayDualPivotSort1D Func __ArrayInsertSort1D(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd) Local $vCur, $vTmp For $i = $iStart + 1 To $iEnd $vTmp = $aArray[$i] If IsNumber($vTmp) Then For $j = $i - 1 To $iStart Step -1 $vCur = $aArray[$j] If ($vTmp >= $vCur And IsNumber($vCur)) Or (Not IsNumber($vCur) And StringCompare($vTmp, $vCur) >= 0) Then ExitLoop $aArray[$j + 1] = $vCur Next Else For $j = $i - 1 To $iStart Step -1 If (StringCompare($vTmp, $aArray[$j]) >= 0) Then ExitLoop $aArray[$j + 1] = $aArray[$j] Next EndIf $aArray[$j + 1] = $vTmp Next EndFunc ; 2D Sort helper functions ; Existing __ArrayQuickSort2D Func __ArrayTagSort2D(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 $vTmp ; InsertionSort (faster for smaller segments) If ($iEnd - $iStart) < 15 Then ; Force tagsort For $i = $iStart + 1 To $iEnd $vTmp = $aTrac[$i] If IsNumber($aArray[$vTmp][$iSubItem]) Then For $j = $i - 1 To $iStart Step -1 If ((($aArray[$vTmp][$iSubItem] >= $aArray[$aTrac[$j]][$iSubItem] And $iStep = 1) Or $aArray[$vTmp][$iSubItem] <= $aArray[$aTrac[$j]][$iSubItem]) And IsNumber($aArray[$aTrac[$j]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$j]][$iSubItem]) And StringCompare($aArray[$vTmp][$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[$vTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop $aTrac[$j + 1] = $aTrac[$j] Next EndIf $aTrac[$j + 1] = $vTmp Next Return EndIf ; TagSort Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[$aTrac[Int(($iStart + $iEnd) / 2)]][$iSubItem], $bNum = IsNumber($vPivot) Do If $bNum Then 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[$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 If $L <= $R Then ; Swap $vTmp = $aTrac[$L] $aTrac[$L] = $aTrac[$R] $aTrac[$R] = $vTmp $L += 1 $R -= 1 EndIf Until $L > $R __ArrayTagSort2D($aArray, $aTrac, $iStep, $iStart, $R, $iSubItem, $iSubMax) __ArrayTagSort2D($aArray, $aTrac, $iStep, $L, $iEnd, $iSubItem, $iSubMax) EndFunc ;==>__ArrayQuickSort2D_NEW2 Func __ArrayTagSort2D_SwapSeq(ByRef $aArray, ByRef $aTrac, Const ByRef $iStart, Const ByRef $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 ;==> __ArrayTagSort2D_SwapSeq Please report tests carried out. You don't need to give full details unless you discover something wrong with it. Thanks!I can't find anything wrong with it. Edited February 6, 2018 by czardas operator64 ArrayWorkshop
Moderators JLogan3o13 Posted February 5, 2018 Moderators Posted February 5, 2018 I did some testing this morning on a mid-size array (37 col by c. 200 rows), below are the averages over 10 runs of each: Current ArraySort - 68.94 New ArraySort without the $iAlternate parameter set - 103.30 New ArraySort with the $iAlternate parameter set - 22.00 "Profanity is the last vestige of the feeble mind. For the man who cannot express himself forcibly through intellect must do so through shock and awe" - Spencer W. Kimball How to get your question answered on this forum!
czardas Posted February 5, 2018 Author Posted February 5, 2018 (edited) Hmm. Not what I expected. There should essentially be no time penalty for using the default sorting method. I'll need to take a closer look. I missed a couple of duplicated error checks, but that shouldn't be slowing it down by much. Code updated in #45. Something about this doesn't add up. Edited February 5, 2018 by czardas operator64 ArrayWorkshop
czardas Posted February 5, 2018 Author Posted February 5, 2018 (edited) I'm not able to confirm your results. Here's my test: Local $aTemp[200][37] For $a = 0 To UBound($aTemp) -1 For $b = 0 To UBound($aTemp, 2) -1 $aTemp[$a][$b] = Chr(Random(97, 122, 1)) & Chr(Random(97, 122, 1)) & Chr(Random(97, 122, 1)) & Chr(Random(97, 122, 1)) Next Next Local $iTimer, $aArray, $iDiff1 = 0, $iDiff2 = 0 For $i = 1 to 10 $aArray = $aTemp $iTimer = TimerInit() _ArraySort($aArray) $iDiff1 += TimerDiff($iTimer) Next ConsoleWrite($iDiff1/10 & @LF) For $i = 1 to 10 $aArray = $aTemp $iTimer = TimerInit() _ArraySort_NEW($aArray) $iDiff2 += TimerDiff($iTimer) Next ConsoleWrite($iDiff2/10 & @LF) And the results are very close for the default sorting method (no time penalty): current version 72.973931289915 new version 72.6573964490579 Perhaps you overlooked something in your test, because the results I'm getting are quite consistent. With TagSort I get: 27.0241028812861 ms Edited February 6, 2018 by czardas operator64 ArrayWorkshop
Moderators JLogan3o13 Posted February 6, 2018 Moderators Posted February 6, 2018 I'll mess with it some more, and will try with an Array I can post "Profanity is the last vestige of the feeble mind. For the man who cannot express himself forcibly through intellect must do so through shock and awe" - Spencer W. Kimball How to get your question answered on this forum!
czardas Posted February 6, 2018 Author Posted February 6, 2018 (edited) Thanks for taking the time to look at it. Everyone seems quite busy ATM - including me. There was a suggestion in GH&S to add case sensitivity to _ArraySort() because Maps use case sensitive keys and you might want to sort them this way. This can be easily implemented with QuickSort, but not with Dual PivotSort. I think this is also worth looking into. I did a quick trial run earlier on. In this case; with an additional case sensitivity parameter set, I think it would be best to override Dual PivotSort rather than try to modify it. Otherwise default Dual PivotSort speed would be heavily compromised. Best not to combine these two things. Edited February 6, 2018 by czardas operator64 ArrayWorkshop
czardas Posted February 6, 2018 Author Posted February 6, 2018 (edited) A new bug has been introduced: numbers are no longer being sorted correctly. This bug appears to have been introduced with changes made by Melba23 to the InsertionSort section of __ArrayTagSort2D() in post #42. The problem does not occur with the earlier version: _ArraySort_Beta() in post #32. The problem has been fixed below. Edited February 6, 2018 by czardas operator64 ArrayWorkshop
czardas Posted February 6, 2018 Author Posted February 6, 2018 (edited) I reverted to the earlier version and it seems to be working again. The bug was not apparent because that section of code was being skipped after changes had been made. When I reintroduced insertion sort by changing the range limit back to what it had been previously, the bug showed itself. The logic had been modified and I was unaware of this. I hope there are no more changes I'm unaware of. I hadn't noticed it because I use my own version. Description: Sort a 1D or 2D array on a specific index using the dualpivotsort/quicksort/insertionsort/tagsort algorithms Syntax: _ArraySort ( ByRef $aArray [, $iDescending = 0 [, $iStart = 0 [, $iEnd = 0 [, $iSubItem = 0 [, $iAlternate = 0]]]]] ) $iAlternate [optional] 1D array sorted with PivotSort algorithm 2D array sorted with TagSort algorithm Default: both sorted with QuickSort algorithm Return Value Success: 1. Failure: 0 and sets the @error flag to non-zero. @error: 1 - $aArray is not an array 2 - $iStart is greater than $iEnd 3 - $iSubItem is greater than subitem count 4 - $aArray is not a 1D or 2D array 5 - $aArray is empty 6 - Deprecated Remarks By default the UDF uses a QuickSort algorithm to sort both 1D and 2D arrays. For 1D arrays setting the $iAlternate parameter uses a DualPivotSort algorithm - this can be significantly faster for large arrays (> 50 elements). In each algorithm, relatively short arrays will be sorted using an insertion sort (< 15 elements with QuickSort and TagSort; < 45 elements with Dual PivotSort). For 2D arrays setting the $iAlternate parameter uses a TagSort algorithm - this is considerably faster when dealing with multiple columns. However, this algoritm uses more memory and may not be suitable for large arrays on less powerful machines. Note that there is no guarantee that a specific algorithm will be faster in a given case. CODE: expandcollapse popup#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 - implemented TagSort ; =============================================================================================================================== Func _ArraySort_NEW(ByRef $aArray, $iDescending = 0, $iStart = 0, $iEnd = 0, $iSubItem = 0, $iAlternate = 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 $iAlternate = Default Then $iAlternate = 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 < 1 Or $iEnd > $iUBound Then $iEnd = $iUBound If $iStart < 0 Then $iStart = 0 If $iStart > $iEnd Then Return SetError(2, 0, 0) ; Sort Switch UBound($aArray, $UBOUND_DIMENSIONS) Case 1 If $iAlternate Then ; Use PivotSort algorithm __ArrayDualPivotSort1D_New($aArray, $iStart, $iEnd) Else __ArrayQuickSort1D_New($aArray, $iStart, $iEnd) EndIf If $iDescending Then _ArrayReverse($aArray, $iStart, $iEnd) Case 2 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 If $iAlternate And $iSubMax Then ; Use TagSort algorithm Local $aTrac[$iUBound +1] For $i = $iStart To $iEnd $aTrac[$i] = $i Next __ArrayTagSort2D($aArray, $aTrac, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax) __ArrayTagSort2D_SwapSeq($aArray, $aTrac, $iStart, $iEnd) Else __ArrayQuickSort2D($aArray, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax) EndIf Case Else Return SetError(4, 0, 0) EndSwitch Return 1 EndFunc ;==>_ArraySort ; 1D Sort helper functions Func __ArrayQuickSort1D_New(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd) If $iEnd <= $iStart Then Return Local $vTmp ; InsertionSort used for small arrays - value chosen empirically If ($iEnd - $iStart) < 15 Then __ArrayInsertSort1D($aArray, $iStart, $iEnd) Return EndIf ; QuickSort Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[Int(($iStart + $iEnd) / 2)], $bNum = IsNumber($vPivot) Do If $bNum Then While ($aArray[$L] < $vPivot And IsNumber($aArray[$L])) Or (Not IsNumber($aArray[$L]) And StringCompare($aArray[$L], $vPivot) < 0) $L += 1 WEnd While ($aArray[$R] > $vPivot And IsNumber($aArray[$R])) Or (Not IsNumber($aArray[$R]) And StringCompare($aArray[$R], $vPivot) > 0) $R -= 1 WEnd Else While (StringCompare($aArray[$L], $vPivot) < 0) $L += 1 WEnd While (StringCompare($aArray[$R], $vPivot) > 0) $R -= 1 WEnd EndIf ; Swap If $L <= $R Then $vTmp = $aArray[$L] $aArray[$L] = $aArray[$R] $aArray[$R] = $vTmp $L += 1 $R -= 1 EndIf Until $L > $R __ArrayQuickSort1D($aArray, $iStart, $R) __ArrayQuickSort1D($aArray, $L, $iEnd) EndFunc ;==>__ArrayQuickSort1D Func __ArrayDualPivotSort1D_New(ByRef $aArray, $iPivot_Left, $iPivot_Right) If $iPivot_Left > $iPivot_Right Then Return Local $iLength = $iPivot_Right - $iPivot_Left + 1 ;Local $i, $j, $k, $iAi, $iAk, $iA1, $iA2, $iLast Local $k ; InsertionSort used for small arrays - value chosen empirically If $iLength < 45 Then __ArrayInsertSort1D($aArray, $iPivot_Left, $iPivot_Right) Return EndIf ; PivotSort Local $iSeventh = BitShift($iLength, 3) + BitShift($iLength, 6) + 1 Local $iE1, $iE2, $iE3, $iE4, $iE5, $t $iE3 = Ceiling(($iPivot_Left + $iPivot_Right) / 2) $iE2 = $iE3 - $iSeventh $iE1 = $iE2 - $iSeventh $iE4 = $iE3 + $iSeventh $iE5 = $iE4 + $iSeventh If $aArray[$iE2] < $aArray[$iE1] Then $t = $aArray[$iE2] $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf If $aArray[$iE3] < $aArray[$iE2] Then $t = $aArray[$iE3] $aArray[$iE3] = $aArray[$iE2] $aArray[$iE2] = $t If $t < $aArray[$iE1] Then $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf EndIf If $aArray[$iE4] < $aArray[$iE3] Then $t = $aArray[$iE4] $aArray[$iE4] = $aArray[$iE3] $aArray[$iE3] = $t If $t < $aArray[$iE2] Then $aArray[$iE3] = $aArray[$iE2] $aArray[$iE2] = $t If $t < $aArray[$iE1] Then $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf EndIf EndIf If $aArray[$iE5] < $aArray[$iE4] Then $t = $aArray[$iE5] $aArray[$iE5] = $aArray[$iE4] $aArray[$iE4] = $t If $t < $aArray[$iE3] Then $aArray[$iE4] = $aArray[$iE3] $aArray[$iE3] = $t If $t < $aArray[$iE2] Then $aArray[$iE3] = $aArray[$iE2] $aArray[$iE2] = $t If $t < $aArray[$iE1] Then $aArray[$iE2] = $aArray[$iE1] $aArray[$iE1] = $t EndIf EndIf EndIf EndIf Local $iLess = $iPivot_Left Local $iGreater = $iPivot_Right If (($aArray[$iE1] <> $aArray[$iE2]) And ($aArray[$iE2] <> $aArray[$iE3]) And ($aArray[$iE3] <> $aArray[$iE4]) And ($aArray[$iE4] <> $aArray[$iE5])) Then Local $iPivot_1 = $aArray[$iE2] Local $iPivot_2 = $aArray[$iE4] $aArray[$iE2] = $aArray[$iPivot_Left] $aArray[$iE4] = $aArray[$iPivot_Right] Do $iLess += 1 Until $aArray[$iLess] >= $iPivot_1 Do $iGreater -= 1 Until $aArray[$iGreater] <= $iPivot_2 $k = $iLess Local $iAk While $k <= $iGreater $iAk = $aArray[$k] If $iAk < $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iAk $iLess += 1 ElseIf $iAk > $iPivot_2 Then While $aArray[$iGreater] > $iPivot_2 $iGreater -= 1 If $iGreater + 1 = $k Then ExitLoop 2 WEnd If $aArray[$iGreater] < $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $aArray[$iGreater] $iLess += 1 Else $aArray[$k] = $aArray[$iGreater] EndIf $aArray[$iGreater] = $iAk $iGreater -= 1 EndIf $k += 1 WEnd $aArray[$iPivot_Left] = $aArray[$iLess - 1] $aArray[$iLess - 1] = $iPivot_1 $aArray[$iPivot_Right] = $aArray[$iGreater + 1] $aArray[$iGreater + 1] = $iPivot_2 __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 2) __ArrayDualPivotSort1D_New($aArray, $iGreater + 2, $iPivot_Right) If ($iLess < $iE1) And ($iE5 < $iGreater) Then While $aArray[$iLess] = $iPivot_1 $iLess += 1 WEnd While $aArray[$iGreater] = $iPivot_2 $iGreater -= 1 WEnd $k = $iLess While $k <= $iGreater $iAk = $aArray[$k] If $iAk = $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iAk $iLess += 1 ElseIf $iAk = $iPivot_2 Then While $aArray[$iGreater] = $iPivot_2 $iGreater -= 1 If $iGreater + 1 = $k Then ExitLoop 2 WEnd If $aArray[$iGreater] = $iPivot_1 Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iPivot_1 $iLess += 1 Else $aArray[$k] = $aArray[$iGreater] EndIf $aArray[$iGreater] = $iAk $iGreater -= 1 EndIf $k += 1 WEnd EndIf __ArrayDualPivotSort1D_New($aArray, $iLess, $iGreater) Else Local $iPivot = $aArray[$iE3] $k = $iLess While $k <= $iGreater If $aArray[$k] = $iPivot Then $k += 1 ContinueLoop EndIf $iAk = $aArray[$k] If $iAk < $iPivot Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $iAk $iLess += 1 Else While $aArray[$iGreater] > $iPivot $iGreater -= 1 WEnd If $aArray[$iGreater] < $iPivot Then $aArray[$k] = $aArray[$iLess] $aArray[$iLess] = $aArray[$iGreater] $iLess += 1 Else $aArray[$k] = $iPivot EndIf $aArray[$iGreater] = $iAk $iGreater -= 1 EndIf $k += 1 WEnd __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 1) __ArrayDualPivotSort1D_New($aArray, $iGreater + 1, $iPivot_Right) EndIf EndFunc ;==>__ArrayDualPivotSort1D Func __ArrayInsertSort1D(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd) Local $vCur, $vTmp For $i = $iStart + 1 To $iEnd $vTmp = $aArray[$i] If IsNumber($vTmp) Then For $j = $i - 1 To $iStart Step -1 $vCur = $aArray[$j] If ($vTmp >= $vCur And IsNumber($vCur)) Or (Not IsNumber($vCur) And StringCompare($vTmp, $vCur) >= 0) Then ExitLoop $aArray[$j + 1] = $vCur Next Else For $j = $i - 1 To $iStart Step -1 If (StringCompare($vTmp, $aArray[$j]) >= 0) Then ExitLoop $aArray[$j + 1] = $aArray[$j] Next EndIf $aArray[$j + 1] = $vTmp Next EndFunc ; 2D Sort helper functions ; Existing __ArrayQuickSort2D Func __ArrayTagSort2D(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 $vTmp ; InsertionSort (faster for smaller segments) If ($iEnd - $iStart) < 15 Then ; Force tagsort For $i = $iStart + 1 To $iEnd $vTmp = $aTrac[$i] ; Follows the same logic as __ArrayQuickSort1D If IsNumber($aArray[$vTmp][$iSubItem]) Then For $j = $i - 1 To $iStart Step -1 If ((($aArray[$vTmp][$iSubItem] * $iStep) >= $aArray[$aTrac[$j]][$iSubItem] * $iStep) And IsNumber($aArray[$aTrac[$j]][$iSubItem])) _ Or (Not IsNumber($aArray[$aTrac[$j]][$iSubItem]) And StringCompare($aArray[$vTmp][$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[$vTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop $aTrac[$j + 1] = $aTrac[$j] Next EndIf $aTrac[$j + 1] = $vTmp Next Return EndIf ; TagSort Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[$aTrac[Int(($iStart + $iEnd) / 2)]][$iSubItem], $bNum = IsNumber($vPivot) Do If $bNum Then 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[$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 If $L <= $R Then ; Swap $vTmp = $aTrac[$L] $aTrac[$L] = $aTrac[$R] $aTrac[$R] = $vTmp $L += 1 $R -= 1 EndIf Until $L > $R __ArrayTagSort2D($aArray, $aTrac, $iStep, $iStart, $R, $iSubItem, $iSubMax) __ArrayTagSort2D($aArray, $aTrac, $iStep, $L, $iEnd, $iSubItem, $iSubMax) EndFunc ;==>__ArrayTagSort2D Func __ArrayTagSort2D_SwapSeq(ByRef $aArray, ByRef $aTrac, Const ByRef $iStart, Const ByRef $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 ;==> __ArrayTagSort2D_SwapSeq Edited February 6, 2018 by czardas iamtheky 1 operator64 ArrayWorkshop
jpm Posted February 6, 2018 Posted February 6, 2018 If I understand well no improvement if no $iAlternate Just can be use on 2D array Init : WorkingSet = 14168 Kb ReDim00 : WorkingSet = 14176 Kb ReDim : WorkingSet = 79720 Kb Test # 1 : Rows = 512 : Columns = 32768 : Penalty = 0 : WorkingSet = 1533640 Kb 106.995 Sec : _ArraySort($aArray2D, 0, 0, 0, 0) : WorkingSet = 2391728 Kb @error=0 106.071 Sec : _ArraySort_NEW($aArray2D, 0, 0, 1, 0) : WorkingSet = 2391728 Kb @error=0 Ratio = 1 0 Sec : _ArraySort($aArray2D, 0, 0, 0, 0, 1) : WorkingSet = 1565324 Kb @error=6 26.903 Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, 1, 1) : WorkingSet = 2398312 Kb @error=0 Ratio = 0 Reset : WorkingSet = 2398312 Kb I don't fully understand why the test comparison is not done on the initial generated array when using the proposed implementation If using the initial generation incase of test 8 it does not improve so much ReDim00 : WorkingSet = 1572416 Kb ReDim : WorkingSet = 1637956 Kb Test # 8 : Rows = 8388608 : Columns = 2 : Penalty = 0 : WorkingSet = 1061716 Kb 1123.279 Sec : _ArraySort($aArray2D, 0, 0, 0, 0) : WorkingSet = 1838064 Kb @error=0 1128.007 Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, 0) : WorkingSet = 1837064 Kb @error=0 Ratio = 1 0 Sec : _ArraySort($aArray2D, 0, 0, 0, 0, 1) : WorkingSet = 1353336 Kb @error=6 976.487 Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, 0, 1) : WorkingSet = 1964852 Kb @error=0 Ratio = 0 Reset : WorkingSet = 1367368 Kb here my test used with the #52 proposal expandcollapse popup;~ #AutoIt3Wrapper_UseX64=y #include <_ArraySort_New.au3> #cs ---------------------------------------------------------------------------- AutoIt Version: 3.3.14.3 Author: myName Script Function: Template AutoIt script. #ce ---------------------------------------------------------------------------- ; Script Start - Add your code below here #include <Array.au3> #include <WinAPIProc.au3> Local $bRestoreInitial = False ;~ Local $bRunNoPivot = False ;~ Local $bRestoreInitial = True Local $bRunNoPivot = True ConsoleWrite( ">>>>>>>>>>>> Restore Initial genetation = " & $bRestoreInitial & @CRLF) ConsoleWrite( ">>>>>>>>>>>> Run No Pivot = " & $bRunNoPivot & @CRLF & @CRLF) Global $iPenalty = 0 ; Caution: 1 penalty point = between 8 and 16 megabytes depending on the test number Global $iFirstTest = 1 ; lowest test number = 1 Global $iLastTest = 1 ; highest test number = 8 ; the following sleep values can be modified depending on available RAM Global $iNap = 00000 ; 30 secs - short sleep Global $iSleep = 00000 ; 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_sav, $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]] Local $iError, $iTimer, $fTimer0, $fTimer1, $fTimer2, $fTimer3 Global $sBloat = StringFormat("%0" & $iPenalty & "s", "") Local $aData = _WinAPI_GetProcessMemoryInfo() ConsoleWrite("Init : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF & @CRLF) ;~ Int($aData[2] / 1024) Local $iSecondCol = 1 If $bRestoreInitial Then $iSecondCol = 0 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] $aData = _WinAPI_GetProcessMemoryInfo() ConsoleWrite("ReDim00 : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF) ReDim $aArray2D[$aBounds[$iTestNum][0]][$aBounds[$iTestNum][1]] ; resize the array $aData = _WinAPI_GetProcessMemoryInfo() ConsoleWrite("ReDim : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF) 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) ;~ _ArrayDisplay($aArray2D, "$aArray2D Initial", "0:1000|0:" & $iSecondCol) $aArray2D_sav = $aArray2D $aData = _WinAPI_GetProcessMemoryInfo() ConsoleWrite("Test # " & $iTestNum & " : Rows = " & UBound($aArray2D) & " : Columns = " & UBound($aArray2D, 2) & " : Penalty = " & $iPenalty & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF) ; now we are ready to run tests If $bRunNoPivot Then $iTimer = TimerInit() ; for the 1st test, sort on the first column _ArraySort($aArray2D, 0, 0, 0, 0) $iError = @error $fTimer0 = Round(TimerDiff($iTimer) / 1000, 3) $aData = _WinAPI_GetProcessMemoryInfo() ConsoleWrite($fTimer0 & " Sec : _ArraySort($aArray2D, 0, 0, 0, 0)" & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb @error=" & $iError & @CRLF) ;~ Sleep($iSleep * $iTestNum) ; multiplied by the test number because each test becomes more brutal If $bRestoreInitial Then $aArray2D = $aArray2D_sav $iTimer = TimerInit() ; sort similar data on the second column _ArraySort_NEW($aArray2D, 0, 0, 0, $iSecondCol) ; the more rows, the more similar the starting conditions [lost after the 1st sort] $iError = @error $fTimer1 = Round(TimerDiff($iTimer) / 1000, 3) $aData = _WinAPI_GetProcessMemoryInfo() ConsoleWrite($fTimer1 & " Sec : _ArraySort_NEW($aArray2D, 0, 0, " & $iSecondCol & ", 0)" & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb @error=" & $iError & @CRLF) ConsoleWrite("Ratio = " & Round($fTimer0 / $fTimer1, 1) & @CRLF) EndIf ; Check $iPivot/$iAlternate $aArray2D = $aArray2D_sav ; Restore initial generation $iTimer = TimerInit() ; for the 1st test, sort on the first column _ArraySort($aArray2D, 0, 0, 0, 0, 1) ; the more rows, the more similar the starting conditions [lost after the 1st sort] $iError = @error $fTimer2 = Round(TimerDiff($iTimer) / 1000, 3) $aData = _WinAPI_GetProcessMemoryInfo() ConsoleWrite($fTimer2 & " Sec : _ArraySort($aArray2D, 0, 0, 0, 0, 1)" & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb @error=" & $iError & @CRLF) $aArray2D = $aArray2D_sav $iTimer = TimerInit() ; sort similar data on the second column _ArraySort_NEW($aArray2D, 0, 0, 0, $iSecondCol, 1) ; the more rows, the more similar the starting conditions [lost after the 1st sort] $iError = @error $fTimer3 = Round(TimerDiff($iTimer) / 1000, 3) $aData = _WinAPI_GetProcessMemoryInfo() ConsoleWrite($fTimer3 & " Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, " & $iSecondCol & ", 1)" & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb @error=" & $iError & @CRLF) ConsoleWrite("Ratio = " & Round($fTimer2 / $fTimer3, 1) & @CRLF) ;~ If $iTestNum = $iLastTest Then _ArrayDisplay($aArray2D, "$aArray2D Last", "0:1000|0:" & $iSecondCol) ;~ $aArray2D = $aArray ; patch to deal with the COM error above ??? Jpm:I don't really understand the impact <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< ;~ Sleep($iSleep * $iTestNum) Sleep($iNap) $aData = _WinAPI_GetProcessMemoryInfo() ConsoleWrite("Reset : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF & @CRLF) $iTestNum = 2 * $iTestNum - 1 ; for 1 2 4 8 only testing 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 ;==>AddMoreBloat Cheers
iamtheky Posted February 6, 2018 Posted February 6, 2018 @czardas post #52 might be the single biggest boner for sorting arrays anyone has ever exhibited czardas 1 ,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-. |(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/ (_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_) | | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) ( | | | | |)| | \ / | | | | | |)| | `--. | |) \ | | `-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_| '-' '-' (__) (__) (_) (__)
czardas Posted February 6, 2018 Author Posted February 6, 2018 41 minutes ago, jpm said: If I understand well no improvement if no $iAlternate Just can be use on 2D array Both statements are correct. 43 minutes ago, jpm said: I don't fully understand why the test comparison is not done on the initial generated array when using the proposed implementation If using the initial generation incase of test 8 it does not improve so much 1. I thought that generating the initial array, with so many calls to Random(), was taking too much time and recreating the exact same starting conditions (in a test that I could post on the forum) seemed difficult to me at the time. 2. This is to be expected. Two columns is unlikely to make much difference and may even be slightly slower depending on bloat within the array. I will try your new test and report back later. Thanks! operator64 ArrayWorkshop
Moderators Melba23 Posted February 6, 2018 Moderators Posted February 6, 2018 12 hours ago, czardas said: This bug appears to have been introduced with changes made by Melba23 Mea culpa. M23 Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind Open spoiler to see my UDFs: Spoiler ArrayMultiColSort ---- Sort arrays on multiple columnsChooseFileFolder ---- Single and multiple selections from specified path treeview listingDate_Time_Convert -- Easily convert date/time formats, including the language usedExtMsgBox --------- A highly customisable replacement for MsgBoxGUIExtender -------- Extend and retract multiple sections within a GUIGUIFrame ---------- Subdivide GUIs into many adjustable framesGUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView itemsGUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeViewMarquee ----------- Scrolling tickertape GUIsNoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxesNotify ------------- Small notifications on the edge of the displayScrollbars ----------Automatically sized scrollbars with a single commandStringSize ---------- Automatically size controls to fit textToast -------------- Small GUIs which pop out of the notification area
czardas Posted February 6, 2018 Author Posted February 6, 2018 No pasa nada! operator64 ArrayWorkshop
czardas Posted February 6, 2018 Author Posted February 6, 2018 Results for jpm's test: Init : WorkingSet = 9084 Kb ReDim00 : WorkingSet = 9096 Kb ReDim : WorkingSet = 74768 Kb Test # 1 : Rows = 512 : Columns = 32768 : Penalty = 0 : WorkingSet = 117208 Kb 170.311 Sec : _ArraySort($aArray2D, 0, 0, 0, 0) : WorkingSet = 1339188 Kb @error=0 178.93 Sec : _ArraySort_NEW($aArray2D, 0, 0, 1, 0) : WorkingSet = 1363056 Kb @error=0 Ratio = 1 0.059 Sec : _ArraySort($aArray2D, 0, 0, 0, 0, 1) : WorkingSet = 50196 Kb @error=6 47.39 Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, 1, 1) : WorkingSet = 1392908 Kb @error=0 Ratio = 0 Reset : WorkingSet = 1291008 Kb +>15:48:45 AutoIt3.exe ended.rc:0 This computer is not ideal for stress testing. operator64 ArrayWorkshop
jpm Posted February 6, 2018 Posted February 6, 2018 So I am happy that I understand. Cheers czardas 1
czardas Posted February 6, 2018 Author Posted February 6, 2018 @Melba23 Your input/code has been very helpful and it didn't take long to track where the previous code was failing. The TagSort option can easily be removed if it doesn't stand the test of time. I would not commit it to the main release just yet. I would be very happy to see it tested in a beta release though. operator64 ArrayWorkshop
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now