Tuesday, August 20, 2019

#1 2003-08-29 03:08:05 am

daveyand
Member
Registered: 2003-07-14
Posts: 181

binary search, can it be doine in applescript

I have a script that at the moment checks a filename against excel rows.

It gets the filename and then scans column 1 to see if that filename exist if it does ten it moves the file.

Quite simple really.  But...

The excel sheet is sort alphabetically and uses letters.  What i would like to do is do a binary search as this would be alot quicker.

For those who dont know a binary search goes half way through the list it then sees if the value you have is either higher or lower than the current item.  If higher then it goes to the next half, which would be the 3rd quarter mark.  Does the same search.  It stops when it reaches a point where the current item is equal to the search string.

Example, using numbers:

5 < looking for 5 in a list of 1 - 20
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

On first step:
get half way point 10.

Is 5 < current item if yes get next point (half of 10)
Is 5 = current item, yes then there is the search co,mplete.

As you can see this is alot faster, only 2 checks and not 5.

Does anyone know how to do this????  Baring in mind i use an excel sheet, but i would be able to put it in a text document sorted if that would be easier.


In the land of the blind the one eyed man is king

Offline

 

#2 2019-08-09 05:01:23 pm

KniazidisR
Member
Registered: 2019-03-03
Posts: 425

Re: binary search, can it be doine in applescript

Yes, this is the fastest algorithm, but I'm sure that this search algorithm is built into both AppleScript and VBA of Excel. So, you probably should not come up with your own algorithm.

  You shouldn’t even compare the speed, because your algorithm will be in the AppleScript language, and the built-in search will be in lower-level languages.

Last edited by KniazidisR (2019-08-09 05:02:42 pm)


macOS Mojave -- version 10.14.4
Safari -- version 12.1

Offline

 

#3 2019-08-10 06:47:48 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4940

Re: binary search, can it be doine in applescript

Whether or not a binary search is faster than a linear one depends on where the item is in the list.  smile  For instance, if the item turns out to be one of the first three in a twenty-item list, a binary search will need four checks to find it. But binary does tend to be faster generally. It's quite easy to write such a search in AS — in fact I've just written this from scratch (and memory) rather than try to locate the one I wrote years ago. If the list contains multiple instances of the item, the index returned is that of the first:

Applescript:

on binarySearch(orderedList, searchItem)
   if (orderedList contains searchItem) then
       script o
           property lst : orderedList
       end script
       
       set l to 1
       set r to (count orderedList)
       repeat while (l < r)
           set m to (l + r) div 2
           if (item m of o's lst < searchItem) then
               set l to m + 1
           else
               set r to m
           end if
       end repeat
       return l
   else
       return 0
   end if
end binarySearch

set orderedList to {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
set searchItem to 13
binarySearch(orderedList, searchItem)

Since the OP posted his question sixteen years ago (you really should stop replying to obsolete threads — its creating a hell of a lot of noise on this site), it's become possible to use ASObjC methods which don't require the list to be ordered, although these will often carry a small time overhead because of the need to convert the list and search object to ASObjC equivalents:

Applescript:

use AppleScript version "2.4" -- 10.10 or later.
use framework "Foundation"
use scripting additions

on listSearch(theList, searchItem)
   set arrayEquivalent to current application's class "NSArray"'s arrayWithArray:(theList)
   if ((arrayEquivalent's containsObject:(searchItem)) as boolean) then
       return (arrayEquivalent's indexOfObject:(searchItem)) + 1
   else
       return 0
   end if
end listSearch

set orderedList to {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
set searchItem to 13
listSearch(orderedList, searchItem)


NG

Offline

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)