Big array search slow, how to improve searching time?

[jchd]

Yes, if you have access to the LAN DB, just import the other data from the remote DB by query: ODBC will get you a 2D array which you can store in a [temporary] table in the LAN DB then work on the LAN DB.

Yet another possibility, depending on the data structure and computational needs: use a scripting dictionary.

[BrewManNH]

_ArrayBinarySearch may be the fastest method to search a sorted array, but what is the fastest method to sort the array?

You're pulling the information from a DB, have the information sorted when you pull it out of the DB and put it into the array

[kylomas]

michaelslamet,

F.W.I.W,

The following will search a 1D or 2D array and return a 2D array (see notes in code)

expandcollapse popup

#include<array.au3>
#include<userudfs.au3>

Local $st = TimerInit()

;=================================================================================
;
; generate array1 as 5000 X 3 random elements (A-Z||0-9)
;
; ucomment the following code to generate a 2D array for testing
;
;=================================================================================

;~ Local $st = TimerInit()
;~ Local $array2[26 * 10], $str

;~ Local $array1[5000][3]
;~ For $1 = 0 To UBound($array1) - 1
;~  For $2 = 0 To ubound($array1,2) - 1
;~      $array1[$1][$2] = Chr(Random(65, 90, 1)) & Random(0, 9, 1)
;~  Next
;~ Next

;=================================================================================
;
; generate array1 as 5000 X 1 random elements (A-Z||0-9)
;
;=================================================================================

Local $array1[5000]
For $1 = 0 To UBound($array1) - 1
        $array1[$1] = Chr(Random(65, 90, 1)) & Random(0, 9, 1)
Next

;=================================================================================
;
; generate array2 as 5000 X 1 random elements (A-Y||0-9)
;
;=================================================================================

;~ Local $ele = 0, $array2[26 * 10]
;~ For $1 = 1 To 25
;~  For $2 = 0 To 9
;~      $array2[$ele] = Chr($1 + 64) & $2
;~      $ele += 1
;~  Next
;~ Next

Local $array2[5000]
For $1 = 0 To UBound($array2) - 1
        $array2[$1] = Chr(Random(65, 90, 1)) & Random(0, 9, 1)
Next

ConsoleWrite(StringFormat('> %-40s %2.4f seconds', 'Time to generate arrays ', TimerDiff($st) / 1000) & @LF)

;=================================================================================
;
; Initialize PsuedoSearch with array to be searched.  Can be 1D or 2D
;
;=================================================================================

$st = TimerInit()
_PsuedoSearchInit($array1)
If @error <> 0 Then
    ConsoleWrite('PsuedoSearch Initialization Error...Exiting...' & @LF)
    Exit
EndIf
ConsoleWrite(StringFormat('> %-40s %2.4f seconds', 'Time to initialize PsuedoSearch ', TimerDiff($st) / 1000) & @LF)

;=================================================================================
;
; Search array2 for all elements in array1
;
;=================================================================================

Local $st = TimerInit(), $str

For $1 = 0 To UBound($array2) - 1

    switch ubound($array2,0)
        case 1
            $Ret = _PsuedoSearch($array2[$1])
        case 2
            for $2 = 0 to ubound($array2,2)- 1
                $Ret = _PsuedoSearch($array2[$1][$2])
            next
    endswitch

    If IsArray($Ret) Then

        ; returns a 2D array as
        ;    [0][0] = # of times found
        ;    [0][1] = String searched for
        ;    [n][0] = row found in
        ;    [n][1] = column found in
        ;
        ; if the array to search is a 1D array then [n][1] will be blank

        $str &= $Ret[0][1]
        For $d = 1 To $Ret[0][0]
            $str &= @TAB & StringFormat('found at row [%04i] col [%04i]', $Ret[$d][0], $Ret[$d][1]) & @LF
        Next

    Else

        $str &= $array2[$1] & ' not found' & @LF

    EndIf

Next

ConsoleWrite(StringFormat('> %-40s %2.4f seconds', 'Total time for search ', TimerDiff($st) / 1000) & @LF)
ConsoleWrite($str & @LF)


; #FUNCTION# ====================================================================================================================
; Name ..........: _PsuedoSearchInit
; Description ...: Creates Global vars to be used to search against.  Vars contain row-column info.
; Syntax ........: _PsuedoSearchInit(Byref $aTargetArray)
; Parameters ....: $aTargetArray        - The array to be searched, either 1D or 2D
; Return values .:                      - @error = 1 parameter is not an array
;                                      |- @error = 2 parameter is not a 1D or 2D array
; Author ........: kylomas
; Modified ......: 5/18/2013
; Remarks .......: Created V1.1.0
; Related .......: _PsuedoSearch
; Link ..........:
; Example .......: Yes
; ===============================================================================================================================
Func _PsuedoSearchInit(ByRef $aTargetArray)

    If Not IsArray($aTargetArray) Then Return SetError(1)
    If UBound($aTargetArray, 0) > 2 Then Return SetError(2)

    Local $instance = 0

    Switch UBound($aTargetArray, 0)
        Case 1
            For $1 = 0 To UBound($aTargetArray, 1) - 1
                $instance = 1
                While 1
                    If IsDeclared("a" & $aTargetArray[$1] & '_' & $instance) Then
                        $instance += 1
                    Else
                        Assign("a" & $aTargetArray[$1] & '_' & $instance, $1, 2)
                        ExitLoop
                    EndIf
                WEnd
            Next
        Case 2
            For $1 = 0 To UBound($aTargetArray, 1) - 1
                For $2 = 0 To UBound($aTargetArray, 2) - 1
                    $instance = 1
                    While 1
                        If IsDeclared("a" & $aTargetArray[$1][$2] & '_' & $instance) Then
                            $instance += 1
                        Else
                            Assign("a" & $aTargetArray[$1][$2] & '_' & $instance, $1 & '_' & $2, 2)
                            ExitLoop
                        EndIf
                    WEnd
                Next
            Next
    EndSwitch
EndFunc   ;==>_PsuedoSearchInit

; #FUNCTION# ====================================================================================================================
; Name ..........: _PsuedoSearch
; Description ...: Search the array specified in _PsuedosearchInit()
; Syntax ........: _PsuedoSearch($str)
; Parameters ....: $str                 - The string to search for
; Return values .:                      - "0" = search argument not found
;                                      |- If the search argument is found then return a 2D array as
;                                      |        [0][0] = # of times found
;                                      |        [0][1] = String searched for
;                                      |        [n][0] = row found in
;                                      |        [n][1] = column found in
; Author ........: kylomas
; Modified ......: 5/18/2013
; Remarks .......: Created V1.1.0
; Related .......: _PsuedoSearchInit
; Link ..........:
; Example .......: Yes
; ===============================================================================================================================

Func _PsuedoSearch($str)

    Local $instance = 1, $aRet[1][2] = [[0, 0]]

    While IsDeclared("a" & $str & '_' & $instance)
        $aTmp = StringSplit(Eval("a" & $str & '_' & $instance), '_')
        $aRet[0][0] = $instance
        $aRet[0][1] = $str
        $instance += 1
        ReDim $aRet[UBound($aRet) + 1][2]
        switch ubound($aTmp)
            case 2
                $aRet[UBound($aRet) - 1][0] = $aTmp[1]
            case 3
                $aRet[UBound($aRet) - 1][0] = $aTmp[1]
                $aRet[UBound($aRet) - 1][1] = $aTmp[2]
        endswitch
    WEnd
    If $aRet[0][0] = 0 Then
        Return 0
    Else
        Return $aRet
    EndIf
EndFunc   ;==>_PsuedoSearch

Searching a 5000 element array against a 5000 element array takes appx. 5 secs.

As you increase the dimensions of the array, the run times increase, of course.  E.G.  a 5000X1 array searched against a 5000 x 3 array takes about 25 seconds.

As before, the more work you can get out of the DB engine the better off you'll be (I know it's obvious but if speed is your concern this is the best place to get it).

kylomas

edit: additional info

If you are just dealing with 1D arrays then _arraysort followed by _arraybinarysearch ran the same arrays as above in 3.4 seconds.

Edited May 20, 2013 by kylomas

[kylomas]

michaelslamet,

I don't know if this matters to you but _arraybinarysearch returns the first ocurrence of a search argument within an array whereas the code that I posted returns index numbers for all elements.  They both run in appx the same time, see code below for comparison.

expandcollapse popup

#include<array.au3>
#include<userudfs.au3>

Local $st = TimerInit()

local $array1[15] = ['A4','B3','A0','Z9','Q2','A0','A2','D3','A0','A0','Z9','B3','A0','Z9','B3']

local $array2[4] = ['A0','A4','Z9','B3']

ConsoleWrite(StringFormat('> %-40s %2.4f seconds', 'Time to generate arrays ', TimerDiff($st) / 1000) & @LF)

;=================================================================================
;
; Initialize PsuedoSearch with array to be searched.  Can be 1D or 2D
;
;=================================================================================

$st = TimerInit()
_PsuedoSearchInit($array1)
If @error <> 0 Then
    ConsoleWrite('PsuedoSearch Initialization Error...Exiting...' & @LF)
    Exit
EndIf
ConsoleWrite(StringFormat('> %-40s %2.4f seconds', 'Time to initialize PsuedoSearch ', TimerDiff($st) / 1000) & @LF)

;=================================================================================
;
; Search array2 for all elements in array1 using PsuedoSearch
;
;=================================================================================

local $str = ''

$st = timerinit()

For $1 = 0 To UBound($array2) - 1

    switch ubound($array2,0)
        case 1
            $Ret = _PsuedoSearch($array2[$1])
        case 2
            for $2 = 0 to ubound($array2,2)- 1
                $Ret = _PsuedoSearch($array2[$1][$2])
            next
    endswitch

    If IsArray($Ret) Then

        ; returns a 2D array as
        ;    [0][0] = # of times found
        ;    [0][1] = String searched for
        ;    [n][0] = row found in
        ;    [n][1] = column found in
        ;
        ; if the array to search is a 1D array then [n][1] will be blank

        $str &= $Ret[0][1]
        For $d = 1 To $Ret[0][0]
            $str &= @TAB & StringFormat('found at row [%04i] col [%04i]', $Ret[$d][0], $Ret[$d][1]) & @LF
        Next

    Else

        $str &= $array2[$1] & ' not found' & @LF

    EndIf

Next

ConsoleWrite(StringFormat('> %-40s %2.4f seconds', 'Total time for search ', TimerDiff($st) / 1000) & @LF)
ConsoleWrite($str & @LF)

;=================================================================================
;
; Search array2 for all elements in array1 using _arraysort and _arraybinarysearch
;
;=================================================================================

Local $st = TimerInit(), $str

_arraysort($array1)

For $1 = 0 To UBound($array2) - 1

    $Ret = _arraybinarysearch($array1,$array2[$1])

    switch $Ret
        case -1
            ConsoleWrite($array2[$1] & ' not found' & @LF)
        case else
            ConsoleWrite($array2[$1] & ' found at ' & $ret  & @LF)
    endswitch

Next

ConsoleWrite(StringFormat('> %-40s %2.4f seconds', 'Total time for search ', TimerDiff($st) / 1000) & @LF)


; #FUNCTION# ====================================================================================================================
; Name ..........: _PsuedoSearchInit
; Description ...: Creates Global vars to be used to search against.  Vars contain row-column info.
; Syntax ........: _PsuedoSearchInit(Byref $aTargetArray)
; Parameters ....: $aTargetArray        - The array to be searched, either 1D or 2D
; Return values .:                      - @error = 1 parameter is not an array
;                                      |- @error = 2 parameter is not a 1D or 2D array
; Author ........: kylomas
; Modified ......: 5/18/2013
; Remarks .......: Created V1.1.0
; Related .......: _PsuedoSearch
; Link ..........:
; Example .......: Yes
; ===============================================================================================================================
Func _PsuedoSearchInit(ByRef $aTargetArray)

    If Not IsArray($aTargetArray) Then Return SetError(1)
    If UBound($aTargetArray, 0) > 2 Then Return SetError(2)

    Local $instance = 0

    Switch UBound($aTargetArray, 0)
        Case 1
            For $1 = 0 To UBound($aTargetArray, 1) - 1
                $instance = 1
                While 1
                    If IsDeclared("a" & $aTargetArray[$1] & '_' & $instance) Then
                        $instance += 1
                    Else
                        Assign("a" & $aTargetArray[$1] & '_' & $instance, $1, 2)
                        ExitLoop
                    EndIf
                WEnd
            Next
        Case 2
            For $1 = 0 To UBound($aTargetArray, 1) - 1
                For $2 = 0 To UBound($aTargetArray, 2) - 1
                    $instance = 1
                    While 1
                        If IsDeclared("a" & $aTargetArray[$1][$2] & '_' & $instance) Then
                            $instance += 1
                        Else
                            Assign("a" & $aTargetArray[$1][$2] & '_' & $instance, $1 & '_' & $2, 2)
                            ExitLoop
                        EndIf
                    WEnd
                Next
            Next
    EndSwitch
EndFunc   ;==>_PsuedoSearchInit

; #FUNCTION# ====================================================================================================================
; Name ..........: _PsuedoSearch
; Description ...: Search the array specified in _PsuedosearchInit()
; Syntax ........: _PsuedoSearch($str)
; Parameters ....: $str                 - The string to search for
; Return values .:                      - "0" = search argument not found
;                                      |- If the search argument is found then return a 2D array as
;                                      |        [0][0] = # of times found
;                                      |        [0][1] = String searched for
;                                      |        [n][0] = row found in
;                                      |        [n][1] = column found in
; Author ........: kylomas
; Modified ......: 5/18/2013
; Remarks .......: Created V1.1.0
; Related .......: _PsuedoSearchInit
; Link ..........:
; Example .......: Yes
; ===============================================================================================================================

Func _PsuedoSearch($str)

    Local $instance = 1, $aRet[1][2] = [[0, 0]]

    While IsDeclared("a" & $str & '_' & $instance)
        $aTmp = StringSplit(Eval("a" & $str & '_' & $instance), '_')
        $aRet[0][0] = $instance
        $aRet[0][1] = $str
        $instance += 1
        ReDim $aRet[UBound($aRet) + 1][2]
        switch ubound($aTmp)
            case 2
                $aRet[UBound($aRet) - 1][0] = $aTmp[1]
            case 3
                $aRet[UBound($aRet) - 1][0] = $aTmp[1]
                $aRet[UBound($aRet) - 1][1] = $aTmp[2]
        endswitch
    WEnd
    If $aRet[0][0] = 0 Then
        Return 0
    Else
        Return $aRet
    EndIf
EndFunc   ;==>_PsuedoSearch

kylomas

edit: as the searched array gets larger the comparison widens.  At 50000 randomly generated entries the binary search runs in 3.8 seconds and mine runs in 21 seconds.  If you only need the first ocurrence of a match then this is the way to go.

Edited May 20, 2013 by kylomas

[michaelslamet]

@Kylomas and BrewManNH: thanks a lot for the example code!

I modified my code to pull the data from MySQL in a sorted form, then I search it using _ArrayBinarySearch.

Guess what?

Amazing to see the search time change from 136 secs to 1 secs

Thanks a lot for helping!

[kylomas]

The perfect outcome...take suggestions and example code and derive your own solution, good job!

kylomas

[michaelslamet]

Thanks, Kylomas

I will never accomplish this without help from you and from another friends here. Thanks for this great community!