Sign in to follow this  
Followers 0
Spiff59

Is _Arraysort() a wimp?

31 posts in this topic

#1 ·  Posted (edited)

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 by Spiff59

Share this post


Link to post
Share on other sites



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.


If I posted any code, assume that code was written using the latest release version unless stated otherwise. Also, if it doesn't work on XP I can't help with that because I don't have access to XP, and I'm not going to.
Give a programmer the correct code and he can do his work for a day. Teach a programmer to debug and he can do his work for a lifetime - by Chirag Gude
How to ask questions the smart way!

I hereby grant any person the right to use any code I post, that I am the original author of, on the autoitscript.com forums, unless I've specifically stated otherwise in the code or the thread post. If you do use my code all I ask, as a courtesy, is to make note of where you got it from.

Back up and restore Windows user files _Array.au3 - Modified array functions that include support for 2D arrays.  -  ColorChooser - An add-on for SciTE that pops up a color dialog so you can select and paste a color code into a script.  -  Customizable Splashscreen GUI w/Progress Bar - Create a custom "splash screen" GUI with a progress bar and custom label.  -  _FileGetProperty - Retrieve the properties of a file  -  SciTE Toolbar - A toolbar demo for use with the SciTE editor  -  GUIRegisterMsg demo - Demo script to show how to use the Windows messages to interact with controls and your GUI.  -   Latin Square password generator

Share this post


Link to post
Share on other sites

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


_AdapterConnections()_AlwaysRun()_AppMon()_AppMonEx()_BinaryBin()_CheckMsgBox()_CmdLineRaw()_ContextMenu()_ConvertLHWebColor()/_ConvertSHWebColor()_DesktopDimensions()_DisplayPassword()_DotNet_Load()/_DotNet_Unload()_Fibonacci()_FileCompare()_FileCompareContents()_FileNameByHandle()_FilePrefix/SRE()_FindInFile()_GetBackgroundColor()/_SetBackgroundColor()_GetConrolID()_GetCtrlClass()_GetDirectoryFormat()_GetDriveMediaType()_GetFilename()/_GetFilenameExt()_GetHardwareID()_GetIP()_GetIP_Country()_GetOSLanguage()_GetSavedSource()_GetStringSize()_GetSystemPaths()_GetURLImage()_GIFImage()_GoogleWeather()_GUICtrlCreateGroup()_GUICtrlListBox_CreateArray()_GUICtrlListView_CreateArray()_GUICtrlListView_SaveCSV()_GUICtrlListView_SaveHTML()_GUICtrlListView_SaveTxt()_GUICtrlListView_SaveXML()_GUICtrlMenu_Recent()_GUICtrlMenu_SetItemImage()_GUICtrlTreeView_CreateArray()_GUIDisable()_GUIImageList_SetIconFromHandle()_GUIRegisterMsg()_GUISetIcon()_Icon_Clear()/_Icon_Set()_IdleTime()_InetGet()_InetGetGUI()_InetGetProgress()_IPDetails()_IsFileOlder()_IsGUID()_IsHex()_IsPalindrome()_IsRegKey()_IsStringRegExp()_IsSystemDrive()_IsUPX()_IsValidType()_IsWebColor()_Language()_Log()_MicrosoftInternetConnectivity()_MSDNDataType()_PathFull/GetRelative/Split()_PathSplitEx()_PrintFromArray()_ProgressSetMarquee()_ReDim()_RockPaperScissors()/_RockPaperScissorsLizardSpock()_ScrollingCredits_SelfDelete()_SelfRename()_SelfUpdate()_SendTo()_ShellAll()_ShellFile()_ShellFolder()_SingletonHWID()_SingletonPID()_Startup()_StringCompact()_StringIsValid()_StringRegExpMetaCharacters()_StringReplaceWholeWord()_StringStripChars()_Temperature()_TrialPeriod()_UKToUSDate()/_USToUKDate()_WinAPI_Create_CTL_CODE()_WinAPI_CreateGUID()_WMIDateStringToDate()/_DateToWMIDateString()Au3 script parsingAutoIt SearchAutoIt3 PortableAutoIt3WrapperToPragmaAutoItWinGetTitle()/AutoItWinSetTitle()CodingDirToHTML5FileInstallrFileReadLastChars()GeoIP databaseGUI - Only Close ButtonGUI ExamplesGUICtrlDeleteImage()GUICtrlGetBkColor()GUICtrlGetStyle()GUIEventsGUIGetBkColor()Int_Parse() & Int_TryParse()IsISBN()LockFile()Mapping CtrlIDsOOP in AutoItParseHeadersToSciTE()PasswordValidPasteBinPosts Per DayPreExpandProtect GlobalsQueue()Resource UpdateResourcesExSciTE JumpSettings INISHELLHOOKShunting-YardSignature CreatorStack()Stopwatch()StringAddLF()/StringStripLF()StringEOLToCRLF()VSCROLLWM_COPYDATAMore Examples...

Updated: 04/09/2015

Share this post


Link to post
Share on other sites

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


My UDFs and Tutorials:

Spoiler

UDFs:
Active Directory (NEW 2017-04-18 - Version 1.4.8.0) - Download - General Help & Support - Example Scripts - Wiki
OutlookEX (NEW 2017-02-27 - Version 1.3.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2015-04-01 - Version 0.4.0.0) - Download - General Help & Support - Example Scripts
Excel - Example Scripts - Wiki
Word - Wiki
PowerPoint (2015-06-06 - Version 0.0.5.0) - Download - General Help & Support

Tutorials:
ADO - Wiki

 

Share this post


Link to post
Share on other sites

water,

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

M23


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

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 :)


My UDFs and Tutorials:

Spoiler

UDFs:
Active Directory (NEW 2017-04-18 - Version 1.4.8.0) - Download - General Help & Support - Example Scripts - Wiki
OutlookEX (NEW 2017-02-27 - Version 1.3.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2015-04-01 - Version 0.4.0.0) - Download - General Help & Support - Example Scripts
Excel - Example Scripts - Wiki
Word - Wiki
PowerPoint (2015-06-06 - Version 0.0.5.0) - Download - General Help & Support

Tutorials:
ADO - Wiki

 

Share this post


Link to post
Share on other sites

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. :)

; 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.


If I posted any code, assume that code was written using the latest release version unless stated otherwise. Also, if it doesn't work on XP I can't help with that because I don't have access to XP, and I'm not going to.
Give a programmer the correct code and he can do his work for a day. Teach a programmer to debug and he can do his work for a lifetime - by Chirag Gude
How to ask questions the smart way!

I hereby grant any person the right to use any code I post, that I am the original author of, on the autoitscript.com forums, unless I've specifically stated otherwise in the code or the thread post. If you do use my code all I ask, as a courtesy, is to make note of where you got it from.

Back up and restore Windows user files _Array.au3 - Modified array functions that include support for 2D arrays.  -  ColorChooser - An add-on for SciTE that pops up a color dialog so you can select and paste a color code into a script.  -  Customizable Splashscreen GUI w/Progress Bar - Create a custom "splash screen" GUI with a progress bar and custom label.  -  _FileGetProperty - Retrieve the properties of a file  -  SciTE Toolbar - A toolbar demo for use with the SciTE editor  -  GUIRegisterMsg demo - Demo script to show how to use the Windows messages to interact with controls and your GUI.  -   Latin Square password generator

Share this post


Link to post
Share on other sites

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

See:


Visit the SciTE4AutoIt3 Download page for the latest versions        Beta files                                                          Forum Rules
 
Live for the present,
Dream of the future,
Learn from the past.
  :)

Share this post


Link to post
Share on other sites

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 :)

Visit the SciTE4AutoIt3 Download page for the latest versions        Beta files                                                          Forum Rules
 
Live for the present,
Dream of the future,
Learn from the past.
  :)

Share this post


Link to post
Share on other sites

#11 ·  Posted (edited)

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 by guinness

_AdapterConnections()_AlwaysRun()_AppMon()_AppMonEx()_BinaryBin()_CheckMsgBox()_CmdLineRaw()_ContextMenu()_ConvertLHWebColor()/_ConvertSHWebColor()_DesktopDimensions()_DisplayPassword()_DotNet_Load()/_DotNet_Unload()_Fibonacci()_FileCompare()_FileCompareContents()_FileNameByHandle()_FilePrefix/SRE()_FindInFile()_GetBackgroundColor()/_SetBackgroundColor()_GetConrolID()_GetCtrlClass()_GetDirectoryFormat()_GetDriveMediaType()_GetFilename()/_GetFilenameExt()_GetHardwareID()_GetIP()_GetIP_Country()_GetOSLanguage()_GetSavedSource()_GetStringSize()_GetSystemPaths()_GetURLImage()_GIFImage()_GoogleWeather()_GUICtrlCreateGroup()_GUICtrlListBox_CreateArray()_GUICtrlListView_CreateArray()_GUICtrlListView_SaveCSV()_GUICtrlListView_SaveHTML()_GUICtrlListView_SaveTxt()_GUICtrlListView_SaveXML()_GUICtrlMenu_Recent()_GUICtrlMenu_SetItemImage()_GUICtrlTreeView_CreateArray()_GUIDisable()_GUIImageList_SetIconFromHandle()_GUIRegisterMsg()_GUISetIcon()_Icon_Clear()/_Icon_Set()_IdleTime()_InetGet()_InetGetGUI()_InetGetProgress()_IPDetails()_IsFileOlder()_IsGUID()_IsHex()_IsPalindrome()_IsRegKey()_IsStringRegExp()_IsSystemDrive()_IsUPX()_IsValidType()_IsWebColor()_Language()_Log()_MicrosoftInternetConnectivity()_MSDNDataType()_PathFull/GetRelative/Split()_PathSplitEx()_PrintFromArray()_ProgressSetMarquee()_ReDim()_RockPaperScissors()/_RockPaperScissorsLizardSpock()_ScrollingCredits_SelfDelete()_SelfRename()_SelfUpdate()_SendTo()_ShellAll()_ShellFile()_ShellFolder()_SingletonHWID()_SingletonPID()_Startup()_StringCompact()_StringIsValid()_StringRegExpMetaCharacters()_StringReplaceWholeWord()_StringStripChars()_Temperature()_TrialPeriod()_UKToUSDate()/_USToUKDate()_WinAPI_Create_CTL_CODE()_WinAPI_CreateGUID()_WMIDateStringToDate()/_DateToWMIDateString()Au3 script parsingAutoIt SearchAutoIt3 PortableAutoIt3WrapperToPragmaAutoItWinGetTitle()/AutoItWinSetTitle()CodingDirToHTML5FileInstallrFileReadLastChars()GeoIP databaseGUI - Only Close ButtonGUI ExamplesGUICtrlDeleteImage()GUICtrlGetBkColor()GUICtrlGetStyle()GUIEventsGUIGetBkColor()Int_Parse() & Int_TryParse()IsISBN()LockFile()Mapping CtrlIDsOOP in AutoItParseHeadersToSciTE()PasswordValidPasteBinPosts Per DayPreExpandProtect GlobalsQueue()Resource UpdateResourcesExSciTE JumpSettings INISHELLHOOKShunting-YardSignature CreatorStack()Stopwatch()StringAddLF()/StringStripLF()StringEOLToCRLF()VSCROLLWM_COPYDATAMore Examples...

Updated: 04/09/2015

Share this post


Link to post
Share on other sites

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


Visit the SciTE4AutoIt3 Download page for the latest versions        Beta files                                                          Forum Rules
 
Live for the present,
Dream of the future,
Learn from the past.
  :)

Share this post


Link to post
Share on other sites

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

Thanks

Jos

I have access already.

_AdapterConnections()_AlwaysRun()_AppMon()_AppMonEx()_BinaryBin()_CheckMsgBox()_CmdLineRaw()_ContextMenu()_ConvertLHWebColor()/_ConvertSHWebColor()_DesktopDimensions()_DisplayPassword()_DotNet_Load()/_DotNet_Unload()_Fibonacci()_FileCompare()_FileCompareContents()_FileNameByHandle()_FilePrefix/SRE()_FindInFile()_GetBackgroundColor()/_SetBackgroundColor()_GetConrolID()_GetCtrlClass()_GetDirectoryFormat()_GetDriveMediaType()_GetFilename()/_GetFilenameExt()_GetHardwareID()_GetIP()_GetIP_Country()_GetOSLanguage()_GetSavedSource()_GetStringSize()_GetSystemPaths()_GetURLImage()_GIFImage()_GoogleWeather()_GUICtrlCreateGroup()_GUICtrlListBox_CreateArray()_GUICtrlListView_CreateArray()_GUICtrlListView_SaveCSV()_GUICtrlListView_SaveHTML()_GUICtrlListView_SaveTxt()_GUICtrlListView_SaveXML()_GUICtrlMenu_Recent()_GUICtrlMenu_SetItemImage()_GUICtrlTreeView_CreateArray()_GUIDisable()_GUIImageList_SetIconFromHandle()_GUIRegisterMsg()_GUISetIcon()_Icon_Clear()/_Icon_Set()_IdleTime()_InetGet()_InetGetGUI()_InetGetProgress()_IPDetails()_IsFileOlder()_IsGUID()_IsHex()_IsPalindrome()_IsRegKey()_IsStringRegExp()_IsSystemDrive()_IsUPX()_IsValidType()_IsWebColor()_Language()_Log()_MicrosoftInternetConnectivity()_MSDNDataType()_PathFull/GetRelative/Split()_PathSplitEx()_PrintFromArray()_ProgressSetMarquee()_ReDim()_RockPaperScissors()/_RockPaperScissorsLizardSpock()_ScrollingCredits_SelfDelete()_SelfRename()_SelfUpdate()_SendTo()_ShellAll()_ShellFile()_ShellFolder()_SingletonHWID()_SingletonPID()_Startup()_StringCompact()_StringIsValid()_StringRegExpMetaCharacters()_StringReplaceWholeWord()_StringStripChars()_Temperature()_TrialPeriod()_UKToUSDate()/_USToUKDate()_WinAPI_Create_CTL_CODE()_WinAPI_CreateGUID()_WMIDateStringToDate()/_DateToWMIDateString()Au3 script parsingAutoIt SearchAutoIt3 PortableAutoIt3WrapperToPragmaAutoItWinGetTitle()/AutoItWinSetTitle()CodingDirToHTML5FileInstallrFileReadLastChars()GeoIP databaseGUI - Only Close ButtonGUI ExamplesGUICtrlDeleteImage()GUICtrlGetBkColor()GUICtrlGetStyle()GUIEventsGUIGetBkColor()Int_Parse() & Int_TryParse()IsISBN()LockFile()Mapping CtrlIDsOOP in AutoItParseHeadersToSciTE()PasswordValidPasteBinPosts Per DayPreExpandProtect GlobalsQueue()Resource UpdateResourcesExSciTE JumpSettings INISHELLHOOKShunting-YardSignature CreatorStack()Stopwatch()StringAddLF()/StringStripLF()StringEOLToCRLF()VSCROLLWM_COPYDATAMore Examples...

Updated: 04/09/2015

Share this post


Link to post
Share on other sites

#14 ·  Posted (edited)

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

What's the highest and lowest number in this column? Edited by water

My UDFs and Tutorials:

Spoiler

UDFs:
Active Directory (NEW 2017-04-18 - Version 1.4.8.0) - Download - General Help & Support - Example Scripts - Wiki
OutlookEX (NEW 2017-02-27 - Version 1.3.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2015-04-01 - Version 0.4.0.0) - Download - General Help & Support - Example Scripts
Excel - Example Scripts - Wiki
Word - Wiki
PowerPoint (2015-06-06 - Version 0.0.5.0) - Download - General Help & Support

Tutorials:
ADO - Wiki

 

Share this post


Link to post
Share on other sites

#15 ·  Posted (edited)

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 by Spiff59

Share this post


Link to post
Share on other sites

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. :)


If I posted any code, assume that code was written using the latest release version unless stated otherwise. Also, if it doesn't work on XP I can't help with that because I don't have access to XP, and I'm not going to.
Give a programmer the correct code and he can do his work for a day. Teach a programmer to debug and he can do his work for a lifetime - by Chirag Gude
How to ask questions the smart way!

I hereby grant any person the right to use any code I post, that I am the original author of, on the autoitscript.com forums, unless I've specifically stated otherwise in the code or the thread post. If you do use my code all I ask, as a courtesy, is to make note of where you got it from.

Back up and restore Windows user files _Array.au3 - Modified array functions that include support for 2D arrays.  -  ColorChooser - An add-on for SciTE that pops up a color dialog so you can select and paste a color code into a script.  -  Customizable Splashscreen GUI w/Progress Bar - Create a custom "splash screen" GUI with a progress bar and custom label.  -  _FileGetProperty - Retrieve the properties of a file  -  SciTE Toolbar - A toolbar demo for use with the SciTE editor  -  GUIRegisterMsg demo - Demo script to show how to use the Windows messages to interact with controls and your GUI.  -   Latin Square password generator

Share this post


Link to post
Share on other sites

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


My UDFs and Tutorials:

Spoiler

UDFs:
Active Directory (NEW 2017-04-18 - Version 1.4.8.0) - Download - General Help & Support - Example Scripts - Wiki
OutlookEX (NEW 2017-02-27 - Version 1.3.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2015-04-01 - Version 0.4.0.0) - Download - General Help & Support - Example Scripts
Excel - Example Scripts - Wiki
Word - Wiki
PowerPoint (2015-06-06 - Version 0.0.5.0) - Download - General Help & Support

Tutorials:
ADO - Wiki

 

Share this post


Link to post
Share on other sites

#18 ·  Posted (edited)

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

#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 by KaFu

Share this post


Link to post
Share on other sites

#19 ·  Posted (edited)

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 by Spiff59

Share this post


Link to post
Share on other sites

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

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...

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
Sign in to follow this  
Followers 0