Jump to content
czardas

Parallel Exponential Search Algorithm

Recommended Posts

czardas

Haven't had much time to code recently. However the following thread inspired me.

The debate about linear, parallel and binary search methods was rather interesting and, in an attempt to be diplomatic, I decided to combine @jchd's suggestion with @LarsJ's binary search example. I decided that the binary search algorithm required modification to make it more linear. As usual, 'if you invent something, it probably already exists and if it already exists, it exists for a reason'. My first attempt was not all that good. The code worked but was really a mess. I blame peer pressure (to post an example of a parallel search method). :D I will delete that old code in due course.

With a little memory jogging and a glance at the help file, the solution turned out to be quite easy: I just needed a better understanding of Euler. Further modification will be needed to work with more complicated unicode strings. The output could be returned as an array or a delimitered string. I'm not so interested in those details. I'm just going to post the algorithm for now and anyone, who wants to, can modify it to suit their needs. Both arrays must contain at least 1 element.

Local $aFoo = [0,1,2,3,4,5,6,7,9,10,11,12,13,14,15,16,19,20,23,24,26,30,35,39,40,41]
Local $aBar = [0,1,5,6,7,8,9,10,11,12,13,14,17,18,19,21,24,25,26,27,34,35,38,40]

ParallelExponetialSearch($aFoo, $aBar)

; Compares two lists - returning positive matches. Each input array must be unique (individually) and in alphabetical order.

Func ParallelExponetialSearch($aFoo, $aBar)
    Local $sFind, _
    $iMin_F = -1, $iMax_F = UBound($aFoo) -1, $Lo_F = $iMin_F, $Hi_F, _
    $iMin_B = -1, $iMax_B = UBound($aBar) -1, $Lo_B = $iMin_B, $Hi_B

    While $iMin_F < $iMax_F And $iMin_B < $iMax_B
        ; Toggle Arrays - Which array has most untested elements? This is the one we want to search next,
        ; so we can bypass more comparisons because (in theory) mismatches have a greater chance of being skipped.

        If $iMax_F - $iMin_F >= $iMax_B - $iMin_B Then ; $aFoo has more (or an equal number of) untested elements

            $Hi_F = $iMax_F
            $iMin_B += 1
            $sFind = $aBar[$iMin_B]

            While $Lo_F < $Hi_F ; search $aFoo
                For $i = 0 To Floor(Log($Hi_F - $Lo_F) / Log(2))
                    $Lo_F = $iMin_F + 2^$i

                    If $aFoo[$Lo_F] = $sFind Then
                        $iMin_F = $Lo_F

                        ; each match should be added to the output [perhaps an array]
                        ConsoleWrite($sFind & " found at $aFoo[" & $Lo_F & "] = $aBar[" & $iMin_B & "]" & @LF)
                        ExitLoop 2

                    ElseIf $aFoo[$Lo_F] > $sFind Then
                        $Hi_F = $Lo_F -1
                        $iMin_F += Floor(2^($i -1))
                        $Lo_F = $iMin_F
                        ContinueLoop 2
                    EndIf
                Next
                $iMin_F = $Lo_F ; minimum increment is one
            WEnd

        Else ; $aBar has more untested elements

            $Hi_B = $iMax_B
            $iMin_F += 1
            $sFind = $aFoo[$iMin_F]

            While $Lo_B < $Hi_B ; search $aBar
                For $i = 0 To Floor(Log($Hi_B - $Lo_B) / Log(2))
                    $Lo_B = $iMin_B + 2^$i

                    If $aBar[$Lo_B] = $sFind Then
                        $iMin_B = $Lo_B

                        ; each match should be added to the output [perhaps an array]
                        ConsoleWrite($sFind & " found at $aFoo[" & $iMin_F & "] = $aBar[" & $Lo_B & "]" & @LF)
                        ExitLoop 2

                    ElseIf $aBar[$Lo_B] > $sFind Then
                        $Hi_B = $Lo_B -1
                        $iMin_B += Floor(2^($i -1))
                        $Lo_B = $iMin_B
                        ContinueLoop 2
                    EndIf
                Next
                $iMin_B = $Lo_B ; minimum increment is one
            WEnd
        EndIf

    WEnd
EndFunc ;==> ParallelExponetialSearch

I hope this will be useful to someone. I believe it deserved a thread of its own! :)

Edited by czardas
  • Like 1

Share this post


Link to post
Share on other sites
czardas

Time for a comparison. Searching within $aBar (for each element in $aFoo) using the standard binary search algorithm, is certain to involve many more comparisons when there are numerous positive matches. In the following test, 3/4 of the elements happen to occur in both arrays. The standard binary search method requires about eight times as many comparisons as the parallel exponential search. If these comparisons were more complex - such as StringComare() - then latency will become obvious.

#include <Array.au3>

Global $iComparisons = 0

ConsoleWrite("generating arrays" & @LF)

Local $aFoo[5000]
For $i = 0 To 4999
    $aFoo[$i] = Hex($i, 8)
Next
_ArrayShuffle($aFoo)

Local $aBar = $aFoo
_ArrayReverse($aBar)

ReDim $aFoo[4000]
ReDim $aBar[4000]

_ArraySort($aFoo)
_ArraySort($aBar)

ConsoleWrite("running tests" & @LF)

ParallelExponetialSearch($aFoo, $aBar)
ConsoleWrite("ParallelExponetialSearch ==> $iComparisons = " & $iComparisons & @LF)

$iComparisons = 0
StandardBinarySearch($aFoo, $aBar)
ConsoleWrite("StandardBinarySearch ==> $iComparisons = " & $iComparisons & @LF)

Func ParallelExponetialSearch($aFoo, $aBar)
    Local $sFind, _
    $iMin_F = -1, $iMax_F = UBound($aFoo) -1, $Lo_F = $iMin_F, $Hi_F, _
    $iMin_B = -1, $iMax_B = UBound($aBar) -1, $Lo_B = $iMin_B, $Hi_B

    While $iMin_F < $iMax_F And $iMin_B < $iMax_B
        ; Toggle Arrays - Which array has most untested elements? This is the one we want to search next,
        ; so we can bypass more comparisons because (in theory) mismatches have a greater chance of being skipped.

        If $iMax_F - $iMin_F >= $iMax_B - $iMin_B Then ; $aFoo has more (or an equal number of) untested elements

            $Hi_F = $iMax_F
            $iMin_B += 1
            $sFind = $aBar[$iMin_B]

            While $Lo_F < $Hi_F ; search $aFoo
                For $i = 0 To Floor(Log($Hi_F - $Lo_F) / Log(2))
                    $Lo_F = $iMin_F + 2^$i

                    $iComparisons += 1

                    If $aFoo[$Lo_F] = $sFind Then
                        $iMin_F = $Lo_F

                        ; each match should be added to the output [perhaps an array]
                        ;ConsoleWrite($sFind & " found at $aFoo[" & $Lo_F & "] = $aBar[" & $iMin_B & "]" & @LF)
                        ExitLoop 2

                    ElseIf $aFoo[$Lo_F] > $sFind Then
                        $Hi_F = $Lo_F -1
                        $iMin_F += Floor(2^($i -1))
                        $Lo_F = $iMin_F
                        ContinueLoop 2
                    EndIf
                Next
                $iMin_F = $Lo_F ; minimum increment is one
            WEnd

        Else ; $aBar has more untested elements

            $Hi_B = $iMax_B
            $iMin_F += 1
            $sFind = $aFoo[$iMin_F]

            While $Lo_B < $Hi_B ; search $aBar
                For $i = 0 To Floor(Log($Hi_B - $Lo_B) / Log(2))
                    $Lo_B = $iMin_B + 2^$i

                    $iComparisons += 1

                    If $aBar[$Lo_B] = $sFind Then
                        $iMin_B = $Lo_B

                        ; each match should be added to the output [perhaps an array]
                        ;ConsoleWrite($sFind & " found at $aFoo[" & $iMin_F & "] = $aBar[" & $Lo_B & "]" & @LF)
                        ExitLoop 2

                    ElseIf $aBar[$Lo_B] > $sFind Then
                        $Hi_B = $Lo_B -1
                        $iMin_B += Floor(2^($i -1))
                        $Lo_B = $iMin_B
                        ContinueLoop 2
                    EndIf
                Next
                $iMin_B = $Lo_B ; minimum increment is one
            WEnd
        EndIf

    WEnd
EndFunc ;==> ParallelExponetialSearch


Func StandardBinarySearch($aFoo, $aBar)
    Local $Lo = 0, $Hi, $iMax_F = UBound($aFoo) -1, $sFind, $iMax_B = UBound($aBar) -1, $iMid
    For $i = 0 To $iMax_F
        $Hi = $iMax_B
        $sFind = $aFoo[$i]

        $iMid = Int(($Hi + $Lo) / 2)

        $iComparisons += 1

        If $aBar[$Lo] > $sFind Or $aBar[$Hi] < $sFind Then ContinueLoop
        ; Search
        While $Lo <= $iMid And $sFind <> $aBar[$iMid]

            $iComparisons += 1

            If $sFind < $aBar[$iMid] Then
                $Hi = $iMid - 1
            Else
                $Lo = $iMid + 1
            EndIf
            $iMid = Int(($Hi + $Lo) / 2)
        WEnd
        If $Lo > $Hi Then ContinueLoop

        ;ConsoleWrite($sFind & " found at $aFoo[" & $i & "] = $aBar[" & $iMid & "]" & @LF)
    Next
EndFunc

The ParallelExponentialSearch() algorithm is frequently going to be a super-efficient method (regardless of language).

Results (may vary slightly on subsequent runs):

ParallelExponetialSearch ==> $iComparisons = 5109
StandardBinarySearch ==> $iComparisons = 39397

This test is a little rough and ready, but the results are as I would expect. A more accurate test would not make much difference to these results.

Edited by czardas

Share this post


Link to post
Share on other sites
czardas

Unfortunately there was a bug in the code (implementation), which I believe I have now fixed: using a While loop (instead of Do Until). Both the above examples have been modified. Please report if you encounter any problems running this code - thanks.

Edited by czardas

Share this post


Link to post
Share on other sites
RTFC
On 9/12/2017 at 10:25 PM, czardas said:

I hope this will be useful to someone.

Definitely, many thanks for this.:D

On 9/12/2017 at 10:25 PM, czardas said:

I just needed a better understanding of Euler.

We all do.;)

  • Like 1

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

  • Similar Content

    • corz
      By corz
      Associative Array Functions
      I've seen a couple of UDFs for this on the forum. One of them I quite like. But it's still nearly not as good as this method, IMHO.
      I don't recall if I discovered the "Scripting.Dictionary" COM object myself or if I got the original base code from somewhere online. I have recently searched the web (and here) hard for any AutoIt references to this, other than my own over the years I've been using this (in ffe, etc..), and I can find nothing, so I dunno. If anyone does, I'd love to give credit where it's due; this is some cute stuff! It could actually be all my own work! lol
      At any rate, it's too useful to not have posted somewhere at autoitscript.com, so I've put together a wee demo.
      For those who haven't heard of the COM "Scripting.Dictionary".. 
      If you've ever coded in Perl or PHP (and many other languages), you know how useful associative arrays are. Basically, rather than having to iterate through an array to discover it's values, with an associative array you simply pluck values out by their key "names".
      I've added a few functions over the years, tweaked and tuned, and this now represent pretty much everything you need to easily work with associative arrays in AutoIt. En-joy!
      The main selling point of this approach is its simplicity and weight. I mean, look at how much code it takes to work with associative arrays! The demo is bigger than all the functions put together! The other selling point is that we are using Windows' built-in COM object functions which are at least theoretically, fast and robust.
      I've used it many times without issues, anyhow, here goes..
      ; Associative arrays in AutoIt? Hells yeah! ; Initialize your array ... global $oMyError = ObjEvent("AutoIt.Error", "AAError") ; Initialize a COM error handler ; first example, simple. global $simple AAInit($simple) AAAdd($simple, "John", "Baptist") AAAdd($simple, "Mary", "Lady Of The Night") AAAdd($simple, "Trump", "Silly Man-Child") AAList($simple) debug("It is said that Trump is a " & AAGetItem($simple, "Trump") & ".", @ScriptLineNumber);debug debug("") ; slightly more interesting.. $ini_path = "AA_Test.ini" ; Put this prefs section in your ini file.. ; [test] ; foo=foo value ; foo2=foo2 value ; bar=bar value ; bar2=bar2 value global $associative_array AAInit($associative_array) ; We are going to convert this 2D array into a cute associative array where we ; can access the values by simply using their respective key names.. $test_array = IniReadSection($ini_path, "test") for $z = 1 to 2 ; do it twice, to show that the items are *really* there! for $i = 1 to $test_array[0][0] $key_name = $test_array[$i][0] debug("Adding '" & $key_name & "'..");debug ; key already exists in "$associative_array", use the pre-determined value.. if AAExists($associative_array, $key_name) then $this_value = AAGetItem($associative_array, $key_name) debug("key_name ALREADY EXISTS! : =>" & $key_name & "<=" , @ScriptLineNumber);debug else $this_value = $test_array[$i][1] ; store left=right value pair in AA if $this_value then AAAdd($associative_array, $key_name, $this_value) endif endif next next debug(@CRLF & "Array Count: =>" & AACount($associative_array) & "<=" , @ScriptLineNumber);debug AAList($associative_array) debug(@CRLF & "Removing 'foo'..");debug AARemove($associative_array, "foo") debug(@CRLF & "Array Count: =>" & AACount($associative_array) & "<=" , @ScriptLineNumber);debug AAList($associative_array) debug(@CRLF & "Removing 'bar'..");debug AARemove($associative_array, "bar") debug(@CRLF & "Array Count: =>" & AACount($associative_array) & "<=" , @ScriptLineNumber);debug AAList($associative_array) quit() func quit() AAWipe($associative_array) AAWipe($simple) endfunc ;; Begin AA Functions func AAInit(ByRef $dict_obj) $dict_obj = ObjCreate("Scripting.Dictionary") endfunc ; Adds a key and item pair to a Dictionary object.. func AAAdd(ByRef $dict_obj, $key, $val) $dict_obj.Add($key, $val) If @error Then return SetError(1, 1, -1) endfunc ; Removes a key and item pair from a Dictionary object.. func AARemove(ByRef $dict_obj, $key) $dict_obj.Remove($key) If @error Then return SetError(1, 1, -1) endfunc ; Returns true if a specified key exists in the associative array, false if not.. func AAExists(ByRef $dict_obj, $key) return $dict_obj.Exists($key) endfunc ; Returns a value for a specified key name in the associative array.. func AAGetItem(ByRef $dict_obj, $key) return $dict_obj.Item($key) endfunc ; Returns the total number of keys in the array.. func AACount(ByRef $dict_obj) return $dict_obj.Count endfunc ; List all the "Key" > "Item" pairs in the array.. func AAList(ByRef $dict_obj) debug("AAList: =>", @ScriptLineNumber);debug local $k = $dict_obj.Keys ; Get the keys ; local $a = $dict_obj.Items ; Get the items for $i = 0 to AACount($dict_obj) -1 ; Iterate the array debug($k[$i] & " ==> " & AAGetItem($dict_obj, $k[$i])) next endfunc ; Wipe the array, obviously. func AAWipe(ByRef $dict_obj) $dict_obj.RemoveAll() endfunc ; Oh oh! func AAError() Local $err = $oMyError.number If $err = 0 Then $err = -1 SetError($err) ; to check for after this function returns endfunc ;; End AA Functions. ; debug() (trimmed-down version) ; ; provides quick debug report in your console.. func debug($d_string, $ln=false) local $pre ; For Jump-to-Line in Notepad++ if $ln then $pre = "(" & $ln & ") " & @Tab ConsoleWrite($pre & $d_string & @CRLF) endfunc  
      ;o) Cor
    • Eminence
      By Eminence
      Hello,
      Is there a way wherein I can access the data from an array coming from an Excel file then have it assigned on to a variable?
      Below is a snippet of my current code. For now, it just reads and outputs the data from the excel file and have it displayed via an array.
      #include <Array.au3> #include <Excel.au3> #include <MsgBoxConstants.au3> Local $oExcel = _Excel_Open(False) If @error Then Exit MsgBox(0, "Error", "Error creating application object." & @CRLF & "Error: " & @error & " Extends: " & @extended) ; Open Excel Woorkbook and return object Local $sWorkbook = @ScriptDir & "\Excel Files\Test Data.xlsx" Local $oWorkbook = _Excel_BookOpen($oExcel, $sWorkbook, False, True) If @error Then MsgBox(0, "Error", "Error opening workbook'" & $sWorkbook & ".'" & @CRLF & "Error: " & @error & "Extends: " & @extended) _Excel_Close($oExcel) Exit EndIf Local $aResult = _Excel_RangeRead($oWorkbook) ; Error Trapping If @error Then MsgBox(0, "Error", "Error reading data from '" & $sWorkbook & ".'" & @CRLF & "Error: " & @error & " Extends: " & @extended) _Excel_Close($oExcel) Exit EndIf _ArrayDisplay($aResult) My Excel file has values from Column A to H with values from 1 to 30, what I desired to do is have the value in "A7" assigned on to a variable. 
       
      Any help is appreciated. Thanks in advance.
    • Abdulla060
      By Abdulla060
      i have a 3d array that is [10][20][6] for now lets assume that its [3][3][3] so it looks something like this 
      [[[1,2,3],[1,2,3],[1,2,3]], [[1,2,3],[1,2,3],[1,2,3]], [[1,2,3],[1,2,3],[1,2,3]]] i need to add another 1d  array to the position [2][3] ( i hope its clear) so it becomes like this 
      [[[1,2,3],[1,2,3],[1,2,3]], [[1,2,3],[1,2,3],[1,2,3]], [[1,2,3],[1,2,3],[1,2,3],[4,5,6]]] and i have no idea how  
    • NizonRox
      By NizonRox
      Hi, i'm currently facing problems with understanding how arrays work, or atleast a few commands that alter arrays.
      My current situation is:
      1. I'm taking the process list and putting it all in an array
      2. I want to remove the boring common windows processes
      3. Profit
      And i'm currently stuck on step 2, while i already found this thread it dosn't seem that i can make it do what i want.
      Current code:
      Local $PList = ProcessList() Local $RL[6] = ["smss.exe", "csrss.exe", "svchost.exe", "iexplore.exe", "chrome.exe", "conhost.exe"] Sleep(1) For $i=1 To Ubound($RL)-1 Sleep(1) While Not @Error $iIndex = _ArraySearch($PList, $RL[$i], 1, 0, 0, 1) _ArrayDelete($PList, $iIndex) WEnd Next It seems to remove all but smss.exe from the array list unless i have it two times in the array.
       
      Note: The sleep(1) is there to clear the error else the command wont fire for the rest of the array, any other way of doing it?
    • Randwulf
      By Randwulf
      To save myself a "search" nightmare, I'm trying to wrap my head around 3D arrays.
      Example: In "No Limit Hold'em", if I only play kings "KK" and queens "QQ"
      and I only play them from the positions of the "Button" or "Blinds"
      and do one thing if it's raised ahead or another if not raised.
      I know that this example would be simple as a 2D array but if I'm dealing with 77 possible hands in 9 possible positions and 6 possible conditions then I'm dealing with almost 700 data lines.
      Lastly, if I have a variables to represent the hand like $hand = "QQ"
      and $position = "Button" and $ahead = "Raised", could the 3D array simplify my search, or should I just stick to the 2D array ??
      Thank you in advance for any thoughts...
×

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.