Big array search slow, how to improve searching time?

[michaelslamet]

I have array1 that contain about 5000 records and growing.

I have another array (array2) that contain also about 5000 records and keep growing too.

For each record on array2, I search it againts array1. If found that I'm doing some operation on it.

This is the code. Is there any posibilities to improve the searching speed? Sort the array and use _ArrayBinarySearch maybe?

Thank you in advance!

For $n = 0 to Ubound($array1)-1
    $array1_split = StringSplit($array1[$n], "|")
    $what_to_search = $array1_split[1]
    $search_result_index = _ArraySearch($array2, $what_to_search, 0, 0, 0, 1)                ; for each array1, search on array2, not case sensitive
    If Not @error Then                                                                        ; if found then
        ; doing something here
    EndIf
Next

 

[water]

Are the arrays sorted?

[michaelslamet]

To water: no, they are not sorted.

[water]

Would it be a problem to sort them? I think searching would be much faster then.

[UEZ]

Or use a database instead.

Br,

UEZ

[michaelslamet]

@Water: no problem to sort them. Is there anybody here ever compare non-sorted array + _ArraySearch versus sorted-array + _ArrayBinarySearch?

@UEZ: actually I read those Array1 and Array2 data from different MySQL database (one on LAN and another on internet) and then put them into array Doing wrong?

[UEZ]

If you compare array 1 against a non sorted array 2 then you need O(n^2) whereas searching within a sorted array using _ArrayBinarySearch() should to in O(logn). Sorting an array using Quicksort takes also (n*logn).

More info at Wikipedia (section Orders of common functions)

That means sorting and comparing should give you a benefit.

Br,

UEZ

[kylomas]

michaelslamet,

Could you get the DB to do the work for you?  Something like:

1 - create the array of search arguments

2 - select * from "data to search" where "some column" =/like "search argument"

kylomas

[water]

Even an Excel workbook can be accessed like a database.

[kylomas]

michaelslamet,

Can you post an example of what $array1 and $array2 look like?

kylomas

edit:  You can adapt a technique similar to the following.  This searches a 5000 element array using the first "|" delimited string from another 5000 element array as the search argument.  The search time is appx. .13 seconds (all 5000 search elements against the searched array).

Although, It makes more sense to me to get the DB itself to do the work.

expandcollapse popup

#include<array.au3>

; generate array1 5000 elements with each element containing 1 to 20 "|" delimited strings of 3 to 10 uppercase characters

local $array1[5000], $array2[5000], $str

for $1 = 0 to ubound($array1) - 1
    for $2 = 1 to random(1,20,1)
        for $3 = 1 to random(3,10,1)
            $str &= chr(random(65,90,1))
        Next
        $str &= '|'
    Next
    $array1[$1] = $str
    $str = ''
Next

; generate array2 with 5000 elements with each element containing 3 to 10 uppercase chars

$str = ''
for $1 = 0 to ubound($array2) - 1
    for $2 = 1 to random(3,10,1)
        $str &= chr(random(65,90,1))
    Next
    $array2[$1] = $str
    $str = ''
Next

local $st = timerinit()

; create a varname = to the value of each element in array2 prepended with "a"

for $1 = 0 to ubound($array2) - 1
    assign("a" & $array2[$1],1)
next

; test if the first "|" delimited value of array 1 exists (is declared) and write output

for $1 = 0 to ubound($array1) - 1

    $aTmp = stringsplit($array1[$1],'|')

        if isdeclared(eval("a" & $aTMP[1])) then

            ; you would do your thing here...

            ConsoleWrite(stringformat('Hit at row = %04i value = %-20s',$1,$aTMP[1]) & @LF)
        EndIf

next

ConsoleWrite(stringformat('Time to search array1 against array2 = %2.4f seconds',timerdiff($st)/1000) & @LF)

Good Luck,

kylomas

Edited May 19, 2013 by kylomas

[kylomas]

michaelslamet,

This version of what I posted above is a little more "user friendly".  It is also quicker (does all 5000 searches in appx. .06 seconds)

expandcollapse popup

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

; generate array1 5000 elements with each element containing 1 to 20 "|" delimited strings of 5 uppercase characters

local $st = timerinit()
local $array1[5000], $array2[5000], $str

for $1 = 0 to ubound($array1) - 1
    for $2 = 1 to random(1,20,1)
        for $3 = 1 to 5
            $str &= chr(random(65,90,1))
        Next
        $str &= '|'
    Next
    $array1[$1] = $str
    $str = ''
Next

; generate array2 with 5000 elements with each element containing 5 uppercase chars

$str = ''
for $1 = 0 to ubound($array2) - 1
    for $2 = 1 to 5
        $str &= chr(random(65,90,1))
    Next
    $array2[$1] = $str
    $str = ''
Next

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

; initialize PsuedoSearch with array to search

$st = timerinit()
_PsuedoSearchInit($array2)
ConsoleWrite(stringformat('> %-40s %2.4f seconds','Time to initialize PsuedoSearch ' ,timerdiff($st)/1000) & @LF)

; find all occurences of the first '|' delimited string from the source array

local $sSearchArg = '', $st = timerinit()

for $1 = 0 to ubound($array1) - 1

    $sSearchArg = stringleft($array1[$1],stringinstr($array1[$1],'|')-1)

    if _PsuedoSearch($sSearchArg) then

        ; you would do your thing here...

        ConsoleWrite(stringformat('Hit at row = %04i value = %-20s',$1,$sSearchArg) & @LF)

    EndIf

next

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

func _PsuedoSearchInit(byref $aTargetArray)
    for $1 = 0 to ubound($aTargetArray) - 1
        assign("a" & $aTargetArray[$1],1,2)
    next
endfunc

func _PsuedoSearch($str)
    if isdeclared("a" & $str) then
        return true
    Else
        return false
    endif
endfunc

kylomas

edit: corrected isdeclared statement

Edited May 19, 2013 by kylomas

[jchd]

Another possible route: read the table (or query resultset) from the remote DB into a local array, import it to the local DB in a separate table then work on the lan DB with SQL.

I don't believe you can attach both tables to avoid extracting one of the table.

Might be faster than copying both tables into arrays then work painfully from there, specially if your tables are expected to grow: SQL will scale gracefully and offer all power you may need to process your data.

[michaelslamet]

@kylomas: thanks a lot for the code example. Really appreciated it

I have tried that, but on the "doing something here" part is i need to StringSplit a string which is the index I got from _ArraySearch

This is my code:

For $n = 0 to Ubound($array1)-1
    $array1_split = StringSplit($array1[$n], "|")
    $what_to_search = $array1_split[1]
    $search_result_index = _ArraySearch($array2, $what_to_search, 0, 0, 0, 1)                ; for each array1, search on array2, not case sensitive
    If Not @error Then                                                                       ; if found then
        $array1_split = StringSplit($Array1[$n], "|")
        $array2_split = StringSplit($Array2[$search_result_index], "|")
        ; compare the value of $array1_split and $array2_split and doing something here
    EndIf
Next

Your example code doesn't returning $search_result_index so I cant do the compare.

I implemented your example code into my code and it works so fast! (136 seconds versus 0.2 seconds), but I think the one that make it slow is _ArraySearch,

so without your code get the $search_result_index, I cant really compare them.

Thanks again!

Edited May 20, 2013 by michaelslamet

[michaelslamet]

@jchd: thanks for offering another solution!

This script should be run on a machine that dont have any database service running, so I dont think it's possible for now.

Anyway, does SQLite need to be installed and run as a service?

Or we can just put the file(s) in to the same dir with our script and execute the SQLite exe file everytime our script need it?

[michaelslamet]

@UEZ: thanks for the info and wiki link, this is a new knowledge for me!

I read the filehelp that _ArraySort is using QuickSearch Algorithm, is there any faster function to do a search an array on AutoIT?

[jchd]

If you don't even have an ODBC (ADO rather) driver on your machine then how do you query/extract remote data and LAN data from both DBs?

I must miss something.

No, SQLite doesn't need any install/setup/maintainance, just a non-registered DLL which you can very well FileInstall within your script if you need a self-contained solution. If your input data is in fact a couple of CSV-style files (depending on which "standard" they use) then SQLite.exe can import them into a permanent or temporary local SQLite DB and perform queries on it.

[BrewManNH]

ArrayBinarySearch is probably the fastest method you'll find to search sorted arrays. You can cut the time by 100 times over a non-binary search depending on the data.

[michaelslamet]

I have ODBC installed on the machine But I dont have MySQL installed on the machine (well, i have it on development machine, but not in the production machine),

so we cant store the data on the local MySQL database

Or you mean store it on the LAN MySQL database? Oh gosh, I miss your point

SQLite really seems great, I should take a time to learn it. Thanks jchd!

[michaelslamet]

@BrewManNH: so you said instead of using _ArraySearch on a non-sorted array, I should sort the array using _ArraySort and doing _ArrayBinarySearch on it?

[michaelslamet]

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