Yet another array sort topic

[Siao]

expandcollapse popup

;===============================================================================
; 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 June 5, 2008 by Siao

[randallc]

Hi,

Wow, I'll have a look again.

I had always hoped someone would take on this task; An improved ArraySort is very welcome for me.

Best, Randall

[randallc]

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

[Siao]

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 February 3, 2008 by Siao

[Siao]

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

[Siao]

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

[randallc]

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

[Siao]

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 June 4, 2008 by Siao

[SmOke_N]

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

[eson]

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.

[Siao]

Because in theory, quicksort is not a stable sorting algo (see http://en.wikipedia.org/wiki/Stable_sort#Stability). That's just the way it is.

Edited June 25, 2008 by Siao

[WeMartiansAreFriendly]

Hi, This is considerably faster than _ArraySort().

expandcollapse popup

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