Jump to content
Sign in to follow this  
czardas

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

Share this post


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

Share this post


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

Share this post


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.;)

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
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

  • Similar Content

    • By Jangal
      Hello friends
      This app is slow
      How to increase its speed?
       
      #include <Array.au3> #include <StringConstants.au3> #include <File.au3> #include <String.au3> Global $aWord[][2]  = [[1, "google"],[2,"hello"]]


        Global $sFileName = @ScriptDir & "\1.txt" ; 2MB Text File Local $sFileRead = FileRead($sFileName) Local $res = StringRegExp($sFileRead, "(*UCP)\b[\pL\d]{2,}", 3) _ArrayDisplay($res)   for $sWord in $res     $iIndex = _ArraySearch($aWord, $sWord, 0, 0, 0, 0, 1, 2)     ;MsgBox(0,0,$iIndex)     if $iIndex == -1 Then         Local $aFill = [[0,$sWord]]         _ArrayAdd($aWord,$aFill)        ;      Else         $aWord[$iIndex][0] +=1     EndIf   Next _ArrayDisplay($aWord)

      1.txt
    • By Colduction
      Hi dear friends!, i'm sorry for creating a new thread (a new problem), i have over than 9 lists that i want to combine them to be this (in this example, there are 3 test files):


      I've written a little code for splitting main information, but i really confused how to make results as "Output.txt", here is that code:
       
      $sRegex_1 = StringRegExp(FileRead("1.txt"), '(?s:(?<=\=\=\r\n)(.*?)(?=\r\n\=\=))', 3) $sRegex_2 = StringRegExp(FileRead("2.txt"), '(?s:(?<=\=\=\r\n)(.*?)(?=\r\n\=\=))', 3) $sRegex_3 = StringRegExp(FileRead("3.txt"), '(?s:(?<=\=\=\r\n)(.*?)(?=\r\n\=\=))', 3) For $i = 0 To UBound($sRegex_1) - 1 ConsoleWrite($sRegex_1[$i] & @CRLF) For $j = 0 To UBound($sRegex_2) - 1 ConsoleWrite($sRegex_2[$j] & @CRLF) For $k = 0 To UBound($sRegex_3) - 1 ConsoleWrite($sRegex_3[$k] & @CRLF) Next Next Next  
    • By nacerbaaziz
      hello evrybody
      here is an example about how to split your texts using a delimiter with the ability to select how much of delimiters shows in each colum  with $i_number
      e.g
      you have a long text and you want to split it in an array
      that evry colum have a number (n) of lines
      i made a function that do that for you
      just call it with a three params
      $s_text
      your text
      $i_number
      the number that you want to put in each col
      $s_siparator
      the siparator
      default is "|"
      here is the function with example
      i hope that it will be useful for you
       
      ****
       
      #include <Array.au3> $s_txt = "some text1some text2|some text3|some text4|some text5|some text6" $array = splitText($s_txt, 2) _ArrayDisplay($array) Func splitText($s_text, $i_number, $s_siparator = "|") Local $a_TXT = StringSplit($s_text, $s_siparator) Local $a_Return[$a_TXT[0] + 1] If ($a_TXT[0] <= $i_number) Or ($i_number <= 0) Then ReDim $a_Return[2] $a_Return[0] = 1 $a_Return[1] = $s_text Return $a_Return EndIf Local $i_Processed = 1, $i_arrayProcessed = 1 Do For $i = $i_Processed To ($i_Processed + $i_number) - 1 If ($a_TXT[0] < $i) Then ExitLoop If Not ($a_Return[$i_arrayProcessed]) Then $a_Return[$i_arrayProcessed] = $a_TXT[$i] Else $a_Return[$i_arrayProcessed] &= $s_siparator & $a_TXT[$i] EndIf $i_Processed += 1 Next $i_arrayProcessed += 1 Until ($a_TXT[0] < $i_Processed) ReDim $a_Return[$i_arrayProcessed] $a_Return[0] = $i_arrayProcessed - 1 Return $a_Return EndFunc ;==>splitText
      accept my greetings
      thanks to
      @Dan_555
      for his notes
       
    • By MesterPerfect
      good morning
      this is the first post here in the autoit forums
      i hope that you can help me in my problem
      i have a JSON encoded
      it a map of my forums
      where i want to make a treeview that have the same type of map
      e.g
      a system (as category)
      windows (as sub category)
      software (as an child item in the windows category)
      .....
      i don't know how to do that
      so, i know that i can do that using the json functions
      but i need your help about how we can do it as the type that i told you
      by the way i need to put the sub info for each item in an array that give me the ability to manage my items
      e.g
      can post thread
      can reply
      message cound ...
      you just give me a small example and i can continue.
      am sorry if this against the rules of the forum.
      but i realy searched a lot but i couldn't
      i hope some one give me the way.
      thank you very much in advance
       
      here is the link of json forum
      https://www.autoitscript.com/forum/topic/148114-a-non-strict-json-udf-jsmn/
      and here is my encoded json file
       
      { "tree_map": { "0": [ 1, 5, 6, 7 ], "1": [ 2 ], "2": [ 4 ], "5": [ 3 ], "6": [ 8 ], "8": [ 9, 10 ] }, "nodes": [ { "breadcrumbs": [], "description": "", "display_in_list": true, "display_order": 1, "node_id": 1, "node_name": null, "node_type_id": "Category", "parent_node_id": 0, "title": "Main category", "type_data": {} }, { "breadcrumbs": [ { "node_id": 1, "title": "Main category", "node_type_id": "Category" } ], "description": "", "display_in_list": true, "display_order": 1, "node_id": 2, "node_name": null, "node_type_id": "Forum", "parent_node_id": 1, "title": "Main forum", "type_data": { "allow_poll": true, "allow_posting": true, "can_create_thread": true, "can_upload_attachment": true, "discussion_count": 0, "last_post_date": 0, "last_post_id": 0, "last_post_username": "", "last_thread_id": 0, "last_thread_prefix_id": 0, "last_thread_title": "", "message_count": 0, "min_tags": 0, "require_prefix": false } }, { "breadcrumbs": [ { "node_id": 1, "title": "Main category", "node_type_id": "Category" }, { "node_id": 2, "title": "Main forum", "node_type_id": "Forum" } ], "description": "", "display_in_list": true, "display_order": 1, "node_id": 4, "node_name": null, "node_type_id": "Forum", "parent_node_id": 2, "title": "my forums1", "type_data": { "allow_poll": true, "allow_posting": true, "can_create_thread": true, "can_upload_attachment": true, "discussion_count": 0, "last_post_date": 0, "last_post_id": 0, "last_post_username": "", "last_thread_id": 0, "last_thread_prefix_id": 0, "last_thread_title": "", "message_count": 0, "min_tags": 0, "require_prefix": false } }, { "breadcrumbs": [], "description": "", "display_in_list": true, "display_order": 2, "node_id": 5, "node_name": null, "node_type_id": "Category", "parent_node_id": 0, "title": "Perfect", "type_data": {} }, { "breadcrumbs": [ { "node_id": 5, "title": "Perfect", "node_type_id": "Category" } ], "description": "", "display_in_list": true, "display_order": 2, "node_id": 3, "node_name": null, "node_type_id": "Forum", "parent_node_id": 5, "title": "ahmed", "type_data": { "allow_poll": true, "allow_posting": true, "can_create_thread": true, "can_upload_attachment": true, "discussion_count": 0, "last_post_date": 0, "last_post_id": 0, "last_post_username": "", "last_thread_id": 0, "last_thread_prefix_id": 0, "last_thread_title": "", "message_count": 0, "min_tags": 0, "require_prefix": false } }, { "breadcrumbs": [], "description": "", "display_in_list": true, "display_order": 3, "node_id": 6, "node_name": null, "node_type_id": "Forum", "parent_node_id": 0, "title": "autoit", "type_data": { "allow_poll": true, "allow_posting": true, "can_create_thread": true, "can_upload_attachment": true, "discussion_count": 0, "last_post_date": 0, "last_post_id": 0, "last_post_username": "", "last_thread_id": 0, "last_thread_prefix_id": 0, "last_thread_title": "", "message_count": 0, "min_tags": 0, "require_prefix": false } }, { "breadcrumbs": [ { "node_id": 6, "title": "autoit", "node_type_id": "Forum" } ], "description": "", "display_in_list": true, "display_order": 3, "node_id": 8, "node_name": null, "node_type_id": "Forum", "parent_node_id": 6, "title": "examples", "type_data": { "allow_poll": true, "allow_posting": true, "can_create_thread": true, "can_upload_attachment": true, "discussion_count": 0, "last_post_date": 0, "last_post_id": 0, "last_post_username": "", "last_thread_id": 0, "last_thread_prefix_id": 0, "last_thread_title": "", "message_count": 0, "min_tags": 0, "require_prefix": false } }, { "breadcrumbs": [ { "node_id": 6, "title": "autoit", "node_type_id": "Forum" }, { "node_id": 8, "title": "examples", "node_type_id": "Forum" } ], "description": "", "display_in_list": true, "display_order": 3, "node_id": 9, "node_name": null, "node_type_id": "Forum", "parent_node_id": 8, "title": "GUI", "type_data": { "allow_poll": true, "allow_posting": true, "can_create_thread": true, "can_upload_attachment": true, "discussion_count": 0, "last_post_date": 0, "last_post_id": 0, "last_post_username": "", "last_thread_id": 0, "last_thread_prefix_id": 0, "last_thread_title": "", "message_count": 0, "min_tags": 0, "require_prefix": false } }, { "breadcrumbs": [ { "node_id": 6, "title": "autoit", "node_type_id": "Forum" }, { "node_id": 8, "title": "examples", "node_type_id": "Forum" } ], "description": "", "display_in_list": true, "display_order": 31, "node_id": 10, "node_name": null, "node_type_id": "Forum", "parent_node_id": 8, "title": "windowEX", "type_data": { "allow_poll": true, "allow_posting": true, "can_create_thread": true, "can_upload_attachment": true, "discussion_count": 0, "last_post_date": 0, "last_post_id": 0, "last_post_username": "", "last_thread_id": 0, "last_thread_prefix_id": 0, "last_thread_title": "", "message_count": 0, "min_tags": 0, "require_prefix": false } }, { "breadcrumbs": [], "description": "", "display_in_list": true, "display_order": 4, "node_id": 7, "node_name": null, "node_type_id": "Category", "parent_node_id": 0, "title": "vbs", "type_data": {} } ] }  
    • By nooneclose
      I need to dynamically resize my 2d array while looping. 
      I know this code:
      ReDim $rArray[UBound($rArray) + 1] works for the rows, however, I also need to increase the columns. How would i go about increasing both rows and columns while looping? 
×
×
  • Create New...