Jump to content

Parallel Exponential Search Algorithm


Recommended Posts

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
Link to post
Share on other sites

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
Link to post
Share on other sites

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
Link to post
Share on other sites
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.;)

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
  • Recently Browsing   0 members

    No registered users viewing this page.

  • Similar Content

    • By vinnyMS
      #Include <Array.au3> #include <Constants.au3> $s = FileRead("2.txt") Local $w = StringRegExp($s, '(?is)(\b\w+\b)(?!.*\b\1\b)', 3) _ArrayColInsert($w, 1) For $i = 0 to UBound($w)-1 StringRegExpReplace($s, '(?i)\b' & $w[$i][0] & '\b', $w[$i][0]) $w[$i][1] = @extended Next _ArraySort($w, 1, 0, 0, 1) _ArrayDisplay($w) i have this script that returns 3 columns  
       
      i need to copy the  Col 0 and Col 1 as text to paste on notepad or excel
      you will have to create a "copy" button if possible
      array.au3 2.txt
    • By DannyJ
      I have a dataset like this, (a strubg)
      Username: User1 Type: Admin RegDate: 1999 Username: User2 Type: User RegDate: 2000 How to make a 2 dimensional array that I can display with _ArrayDisplay?
      This would be a perfect 2D array to represent my data:
      Username           Tpye RegDate User1              Admin 1999 User2              User 2000   If you run this Powershell this powershell command, you can get this dataset that I am talking about:
      Get-LocalUser | Select * With this code you can try it to read into a string:
      #include <GuiConstantsEx.au3> #include <WindowsConstants.au3> #include "GUIListViewEx.au3" #include <Array.au3> ; Just for display in example #RequireAdmin #Region ;**** Directives created by AutoIt3Wrapper_GUI **** #AutoIt3Wrapper_UseX64=y #EndRegion $sCommand = "powershell.exe Get-LocalUser | Select *" Local $iPid = Run($sCommand, @WorkingDir , @SW_SHOW , $STDOUT_CHILD) ProcessWaitClose($iPid) Local $sOutput = StdoutRead($iPID) ConsoleWrite($sOutput) How can I correctly split $sOutput into a 2D array (with the above mentioned layout) that I can display and I work with?
    • By kovlad
      My solution is to write nested arrays without copying.
      The problem was described hier.
       
      Function:
      #include <Array.au3> ; #FUNCTION# ==================================================================================================================== ; Name ..........: _ArrayNestedSet ; Description ...: Assigns a value to an element of a nested 1D array. ; Syntax ........: _ArrayNestedSet(ByRef $aArray, $vIndex, $vValue) ; Parameters ....: $aArray - an array of arrays. ; $vIndex - an index or 1d-array of indexes; ; a size if $vValue not defined (zero to delete). ; $vValue - a value (create, resize or delete if not defined). ; ; Return values .: on success - 1 ; @extended - nesting level of operation ; on failure - 0 ; @extended - nesting level of error ; @error = 1 - invalid array ; @error = 2 - invalid index ; Author ........: ; Modified ......: kovlad ; Remarks .......: ; Related .......: ; Link ..........: https://www.autoitscript.com/forum/topic/185638-assign-a-value-to-an-array-in-array-element/ ; https://www.autoitscript.com/trac/autoit/ticket/3515?replyto=description ; Example .......: Yes ; =============================================================================================================================== Func _ArrayNestedSet(ByRef $aArray, $vIndex, $vValue = Default) Local $extended = @extended + 1 If IsArray($vIndex) Then If UBound($vIndex, 0) <> 1 Then _ Return SetError(2, $extended) If UBound($vIndex) > 1 Then If UBound($aArray, 0) <> 1 Then _ Return SetError(1, $extended) ; keep index for this array Local $i = $vIndex[0] If $i < 0 Or UBound($aArray) <= $i Then _ Return SetError(2, $extended) ; delete index of this array _ArrayDelete($vIndex, 0) ; recursive function call Local $return = _ArrayNestedSet($aArray[$i], $vIndex, $vValue) If @error Then Return SetError(@error, @extended + 1, 0) Else Return SetExtended(@extended + 1, 1) EndIf Else $vIndex = $vIndex[0] EndIf EndIf If $vValue = Default Then If $vIndex < 0 Then _ Return SetError(2, $extended) If $vIndex = 0 Then ; delete array and free memory $aArray = 0 Return SetExtended($extended, 1) EndIf If UBound($aArray, 0) = 1 Then ; resize array keeping data ReDim $aArray[$vIndex] Return SetExtended($extended, 1) Else ; create new nested array Local $aTmp[$vIndex] $aArray = $aTmp Return SetExtended($extended, 1) EndIf Else If UBound($aArray) <= $vIndex Then _ Return SetError(2, $extended + 1) ; set value of array entry $aArray[$vIndex] = $vValue Return SetExtended($extended, 1) EndIf EndFunc  
      Examples:
      ; write value to 1st nested array ConsoleWrite("@@ Debug(" & @ScriptLineNumber & ") : write value to 1st nested array" & @CRLF) Local $aTmp1[4] = [1,2,3,4] _ArrayDisplay($aTmp1, "$aTmp1") Local $aArray[2] = [$aTmp1] ConsoleWrite( _ "_ArrayNestedSet($aArray[0], 3, 14) = " & _ArrayNestedSet($aArray[0], 3, 14) & @CRLF & _ " @error = " & @error & @CRLF & _ " @extended = " & @extended & @CRLF & @CRLF) _ArrayDisplay($aArray[0], "$aArray[0]") ; resize 1st nested array ConsoleWrite("@@ Debug(" & @ScriptLineNumber & ") : resize 1st nested array" & @CRLF) ConsoleWrite( _ "_ArrayNestedSet($aArray[0], 8) = " & _ArrayNestedSet($aArray[0], 8) & @CRLF & _ " @error = " & @error & @CRLF & _ " @extended = " & @extended & @CRLF & @CRLF) _ArrayDisplay($aArray[0], "$aArray[0]") ; write array to 1st nested array ConsoleWrite("@@ Debug(" & @ScriptLineNumber & ") : write array to 1st nested array" & @CRLF) Local $aTmp11[4] = [11,12,13,14] _ArrayDisplay($aTmp11, "$aTmp11") ConsoleWrite( _ "_ArrayNestedSet($aArray[0], 2, $aTmp11) = " & _ArrayNestedSet($aArray[0], 2, $aTmp11) & @CRLF & _ " @error = " & @error & @CRLF & _ " @extended = " & @extended & @CRLF & @CRLF) _ArrayDisplay(($aArray[0])[2], "($aArray[0])[2]") ; write value to 2nd nested array using index array ConsoleWrite("@@ Debug(" & @ScriptLineNumber & ") : write value to 2nd nested array using index array" & @CRLF) Local $aIndex1[2] = [2,3] _ArrayDisplay($aIndex1, "$aIndex1") ConsoleWrite( _ "_ArrayNestedSet($aArray[0], $aIndex1, 140) = " & _ArrayNestedSet($aArray[0], $aIndex1, 140) & @CRLF & _ " @error = " & @error & @CRLF & _ " @extended = " & @extended & @CRLF & @CRLF) _ArrayDisplay(($aArray[0])[2], "($aArray[0])[2]") ; resize 2nd nested array ConsoleWrite("@@ Debug(" & @ScriptLineNumber & ") : resize 2nd nested array" & @CRLF) Local $aIndex1[2] = [2,8] _ArrayDisplay($aIndex1, "$aIndex1") ConsoleWrite( _ "_ArrayNestedSet($aArray[0], $aIndex1) = " & _ArrayNestedSet($aArray[0], $aIndex1) & @CRLF & _ " @error = " & @error & @CRLF & _ " @extended = " & @extended & @CRLF & @CRLF) _ArrayDisplay(($aArray[0])[2], "($aArray[0])[2]") ; create new 3rd nested array ConsoleWrite("@@ Debug(" & @ScriptLineNumber & ") : create new 3rd nested array" & @CRLF) Local $aIndex2[3] = [2,7,6] _ArrayDisplay($aIndex2, "$aIndex2") ConsoleWrite( _ "_ArrayNestedSet($aArray[0], $aIndex2) = " & _ArrayNestedSet($aArray[0], $aIndex2) & @CRLF & _ " @error = " & @error & @CRLF & _ " @extended = " & @extended & @CRLF & @CRLF) _ArrayDisplay((($aArray[0])[2])[7], ")($aArray[0])[2])[7]") ; delete 3rd nested array ConsoleWrite("@@ Debug(" & @ScriptLineNumber & ") : delete 3rd nested array" & @CRLF) Local $aIndex3[3] = [2,7,0] _ArrayDisplay($aIndex3, "$aIndex2") ConsoleWrite( _ "_ArrayNestedSet($aArray[0], $aIndex3) = " & _ArrayNestedSet($aArray[0], $aIndex3) & @CRLF & _ " @error = " & @error & @CRLF & _ " @extended = " & @extended & @CRLF) ConsoleWrite("IsArray((($aArray[0])[2])[7]) = " & IsArray((($aArray[0])[2])[7]) & @CRLF & @CRLF) ; write 0 in 1st nested array to delete the 2nd nested array ConsoleWrite("@@ Debug(" & @ScriptLineNumber & ") : write 0 in 1st nested array to delete the 2nd nested array" & @CRLF) Local $aIndex4[1] = [2] _ArrayDisplay($aIndex4, "$aIndex4") ConsoleWrite( _ "_ArrayNestedSet($aArray[0], $aIndex4, 0) = " & _ArrayNestedSet($aArray[0], $aIndex4, 0) & @CRLF & _ " @error = " & @error & @CRLF & _ " @extended = " & @extended & @CRLF) ConsoleWrite("IsArray(($aArray[0])[2]) = " & IsArray(($aArray[0])[2]) & @CRLF & @CRLF) ; delete 1st nested array (same as '$aArray[0] = 0') ConsoleWrite("@@ Debug(" & @ScriptLineNumber & ") : delete 1st nested array (same as '$aArray[0] = 0')" & @CRLF) Local $aIndex5[1] = [0] _ArrayDisplay($aIndex5, "$aIndex5") ConsoleWrite( _ "_ArrayNestedSet($aArray[0], $aIndex5) = " & _ArrayNestedSet($aArray[0], $aIndex5) & @CRLF & _ " @error = " & @error & @CRLF & _ " @extended = " & @extended & @CRLF) ConsoleWrite("IsArray($aArray[0]) = " & IsArray($aArray[0]) & @CRLF & @CRLF)  
    • By DannyJ
      $sCommands1 = 'powershell.exe Get-ChildItem' $iPid = run($sCommands1   , @WorkingDir , @SW_SHOW , 0x2) $sOutput = ""  While 1     $sOutput &= StdoutRead($iPID)         If @error Then             ExitLoop         EndIf  WEnd ;~ msgbox(0, '' , $sOutput) ConsoleWrite("$sOutput") ConsoleWrite($sOutput) ConsoleWrite(@CRLF) $aOutput = stringsplit($sOutput ,@LF , 2) For $i=0 To  UBound($aOutput) - 1 Step 1     ConsoleWrite($aOutput[$i]) Next The script above reads the whole directory into a one dimensional array, but I need to work with the array, so I need to split the array into multiple dimensions.
      I have already read some forum answers here, and I have already tried these commands:
       
      Are there any way to use the $aOutput variable like in PowerShell:
      PowerShell:
      $a = Get-ChildItem $a.Mode I imagine this in AutoIt  $aOutput
      ConsoleWrite($aOutput[i].Mode) Or if I split this command into 2 dimension like:
      For $i To UBound($aOutput)-1 Step 1 ConsoleWrite($aOutput[$i][1]) ConsoleWrite($aOutput[$i][2]) Next  
    • By Mannyfresh31
      Please help with this 3D Array the first example works the secound doesn't.
      Need help to understand how Arrays work.
      Many thanks in advance
      ;First Example Dim $aArray[2][2][2] $aArray[0][0][0] = 1 $aArray[0][0][1] = 2 $aArray[0][1][0] = 3 $aArray[0][1][1] = 4 $aArray[1][0][0] = 5 $aArray[1][0][1] = 6 $aArray[1][1][0] = 7 $aArray[1][1][1] = 8 For $a = 0 to 1 for $b = 0 to 1 for $c = 0 to 1 ConsoleWrite($aArray[$a][$b][$c] & @CRLF) Next Next Next ;Secound Example Local $aArraym [2][2][2]=[[[1,2,],[3,4],[5,6],[7,8]]] For $a = 0 to 1 for $b = 0 to 1 for $c = 0 to 1 ConsoleWrite($aArraym[$a][$b][$c] & @CRLF) Next Next Next  
×
×
  • Create New...