Sign in to follow this  
Followers 0
Siao

Yet another array sort topic

12 posts in this topic

#1 ·  Posted (edited)

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

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 < 2) Then Return SetError(2, 0, 0)
    If $iArrayDims = 2 And ($iColumnMax - $iColumn < 0) Then Return SetError(2, 0, 0)
    If $iStrMax < 1 Then Return SetError(2, 0, 0)
    Local $i, $j, $iCount = $iEnd - $iStart + 1, $fNumeric, $aRet, $sZero = ChrW(0), $sStrCmp, $sBufType = 'byte[', $hDll = DllOpen('msvcrt.dll'), $tSource, $tIndex, $tFloatCmp, $tCmpWrap = DllStructCreate('byte[64]'), $tEnumProc = DllStructCreate('byte[64]')
    If $hDll = -1 Then Return SetError(3, 0, 0)
    ;; initialize compare proc
    Switch $iMode
        Case 0
            $fNumeric = True
            $tFloatCmp = DllStructCreate('byte[36]')
            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('kernel32.dll','ptr','GetModuleHandle', 'str','msvcrt.dll')
            $aRet = DllCall('kernel32.dll','ptr','GetProcAddress', 'ptr',$aRet[0], 'str',$sStrCmp)
            If $aRet[0] = 0 Then Return SetError(3, 0, 0*DllClose($hDll))
            DllStructSetData($tCmpWrap, 1, '0xBA' & Hex(Binary($aRet[0]), 8) & '8B4424088B4C2404FF30FF31FFD283C408C3')
            DllStructSetData($tEnumProc, 1, '0x8B7424048B7C24088B4C240C8B542410893789570483C7088A064684C075F9424975EDC21000')
        Case 3
            $sBufType = 'wchar['
            $aRet = DllCall('kernel32.dll','ptr','GetModuleHandle', 'str','kernel32.dll')
            $aRet = DllCall('kernel32.dll','ptr','GetProcAddress', 'ptr',$aRet[0], 'str','CompareStringW')
            If $aRet[0] = 0 Then Return SetError(3, 0, 0*DllClose($hDll))
            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('user32.dll','uint','CallWindowProc', 'ptr',DllStructGetPtr($tEnumProc), 'ptr',DllStructGetPtr($tSource), 'ptr',DllStructGetPtr($tIndex), 'int',$iCount, 'int',$iStart)
    ;; sort
    DllCall($hDll,'none:cdecl','qsort', 'ptr',DllStructGetPtr($tIndex), 'int',$iCount, 'int',8, 'ptr',DllStructGetPtr($tCmpWrap))
    DllClose($hDll)
    ;; 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

Edited by Siao

"be smart, drink your wine"

Share this post


Link to post
Share on other sites



Hi

Looks great so far!

I still have comments and queries;

1. Can I confirm that you would expect still to be able to "setup" the sort, without getting the array back?; it seems to work, and quite a bit quicker?

2. I still need the vbs sort for my "subsort", so other columns can be subsorted at the same time on items that match in the first sort; I guess I could just do another vbs/or autoit sort and run it again on your sorted array...

3. I have now some motivation to check the speed of vbs if truly done as 2D sort rather than delimited strings; I had thought it would be slower, but maybe the recurrent stingsplits were the problem.. [and, of course, the time converting it from 2D in the first place! - previously listview usually was going to need the delimited strings, but no longer!]

[off topic, I still haven't tried the cache issue for column display in arraydisplay; were those commented lines of yours a good hint, or did you decide it would not work? - Did the "search 1D" using keyboard work?]

Best, Randall

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

1) If you mean, disabling the code that modifies the actual array and reading from the memory struct outside the function like you tried before, then yes it should work the same.

2) Haven't thought about subsorting dupes. I guess it would be possible to incorporate such functionality one way or another. Which reminds me that I should probably fix the code that writes from array to memory, to write only items from $iStart to $iEnd. Right now it writes all of the array, which doesn't make any noticeable difference in most cases because usually the whole array is to be sorted anyway (except 0-item for StringSplit arrays), but makes it really uncompetitive in cases when you need to sort only a small part of a big array.

Regarding virtual array display.

I still think that cache notification isn't useful there in its real purpose (that is, letting you know the range of items you need to prepare). But I think it could serve some side purpose. Maybe. Lets say that visible columns checking idea. Doing that during LVN_GETDISPINFO would defeat its purpose, it should be done only when columns visibility can possibly change (horizontal scroll notification, column resize, window resize notification...). If these events consistently trigger the cache notification too, you could do the checking in there, instead of multiple places (although this way you still would be doing the check more often than it's necessary, but, maybe worth consideration).

Keyboard typing search functionality - theoretically it should work. I haven't actually tested it in the example I posted, maybe there's some bug left (I just copy/pasted from my app). It should also work regardless if it's 1D or 2D, if you have a function which can search first column of 2D (I assume _ArraySearch was improved in beta to handle 2D). Although I suppose linear search on large array should be pretty slow. Too slow to work properly maybe?

Oh, and the search must be partial. When user types "m" for example, you get that find notification that searchstring is "m", and should search the array for the first item which begins with "m". And so on.

Edited by Siao

"be smart, drink your wine"

Share this post


Link to post
Share on other sites

Small update, fixed issue mentioned in my post above. Sorting small part of a big array should be fast now.


"be smart, drink your wine"

Share this post


Link to post
Share on other sites

Bah, pretty big update.

Decided to rewrite memory related code, seeing that it's pretty expensive to create many elements in DllStructCreate. Since I was using some ASM anyway, might as well make a better use of it. This way finally achieved my initial goal to get 100000 element x 150 char array sorted in less than 10 secs (on my oldie system). That is quite a bit faster than previous version which wasn't too shabby to begin with :)


"be smart, drink your wine"

Share this post


Link to post
Share on other sites

Bah, pretty big update.

Decided to rewrite memory related code, seeing that it's pretty expensive to create many elements in DllStructCreate. Since I was using some ASM anyway, might as well make a better use of it. This way finally achieved my initial goal to get 100000 element x 150 char array sorted in less than 10 secs (on my oldie system). That is quite a bit faster than previous version which wasn't too shabby to begin with :)

Wow! Every increment of speed-up is much appreciated here!

I'll check it out, thanks..

Randall

Share this post


Link to post
Share on other sites

#8 ·  Posted (edited)

Update - added 1 sort mode, which is intended for (hopefully) max compatibility with AutoIt's string compare (useful with _ArrayBinarySearch); string length option; and some other minor changes.

Edited by Siao

"be smart, drink your wine"

Share this post


Link to post
Share on other sites

I don't know how I missed this originally, but it was great to read.


Common sense plays a role in the basics of understanding AutoIt... If you're lacking in that, do us all a favor, and step away from the computer.

Share this post


Link to post
Share on other sites

Update - added 1 sort mode, which is intended for (hopefully) max compatibility with AutoIt's string compare (useful with _ArrayBinarySearch); string length option; and some other minor changes.

Hello,

I'm having some problems with your function.

I have the following 2d array (col1 = names; col2 = numbers). I use TAB as the separator.

JULIETA 2

STEFANY 1

ROGERIO 1

CLARICE 1

JOAO 1

LUIZ 2

MATEU 2

LUCAS 1

FRANCO 1

MARIA 1

ADRIANA 1

I want to sort (ascendant) by the second column (the numbers). After sort, the first line of the array should be "STEFANY 1" as it is the first line with the number 1.

But your function gives me "MARIA 1" as the first line! Why?

Thank you.

Share this post


Link to post
Share on other sites

Hi, This is considerably faster than _ArraySort().

#include <array.au3>
#include <timers.au3>

Local $iIncrement = 5 ;repeat nth times
Local $iAmount = 9999 ;index of arrays

Local $_Number1 = 0
Local $_Number2 = 0
Local $avArray1[$iAmount + 1]
Local $avArray2[$iAmount + 1]

For $i = 0 to $iIncrement
    ConsoleWrite('> ==========================' &@LF)
    ConsoleWrite('>[ Initialising Array (Index: '&$iAmount& ', Increment ' & $i &'\'& $iIncrement &')' &@LF)
    For $x = 0 to $iAmount
        $iNumber = Random(1, 999)
        If Random(0, 1) > 0.5 Then $iNumber = ChrW($iNumber) ;random mix of numbers and characters
        $avArray1[$x] = $iNumber
        $avArray2[$x] = $iNumber
    Next

    ConsoleWrite('+> _ArraySortClib -> Sorting' &@LF)
    $iStart = _Timer_Init()
    _ArraySortClib($avArray1, 0, False, 0, 0, 0, 4095)
    $iDiff1 = _Timer_Diff($iStart)
    ConsoleWrite('-> _ArraySortClib -> Time: '& $iDiff1 &@LF)
    
    ConsoleWrite('+> _ArraySort -> Sorting' &@LF)
    $iStart = _Timer_Init()
    _ArraySort($avArray2, 0, 0, 0, 0)
    $iDiff2 = _Timer_Diff($iStart)
    ConsoleWrite('-> _ArraySort -> Time: '& $iDiff2 &@LF)

    $_Number1 += $iDiff1 
    $_Number2 += $iDiff2
Next

$ms1 = ($_Number1 / $iAmount)
$sec1 = $ms1/1000 &' sec'
$ms1 = $ms1 &' ms'

$ms2 = ($_Number2 / $iAmount)
$sec2 = $ms2/1000 &' sec'
$ms2 = $ms2 &' ms'

ConsoleWrite( _
'> ==========================' &@LF& _
'>[ ArraySort Average'&@LF& _
'+> _ArraySortClib: ' & _
@LF&@TAB& '-> Milliseconds: ' & $ms1 & _
@LF&@TAB& '-> Seconds: '& $sec1 & _
@LF & _
'+> _ArraySort: ' & _
@LF&@TAB& '-> Milliseconds: ' & $ms2 & _
@LF&@TAB& '-> Seconds: '& $sec2 & _
@LF)

Could you describe the logic behind your algo? That would awesome If everything could be written to use this faster method of embeding asm and calling it. I assume.


Don't bother, It's inside your monitor!------GUISetOnEvent should behave more like HotKeySet()

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