fastes way to search an array?

Mark Waddingham mark at livecode.com
Thu Apr 23 05:03:11 EDT 2015


> I have an array with 20000 records, where I want to extract all 
> records,
> which either "begins with" or "contains" a search string.

 From your description I presume your array is of the form:

tArray[<key_1>] = <some string>
tArray[<key_2>] = <some string>
...
tArray[<key_n>] = <some string>

 From this you want to do this:

repeat for each key tKey in tArray
   if tArray[tKey] begins with tSearchString or \
      tArray[tKey] contains tSearchString then
     put tKey & return after tResults
   end if
end repeat

If this is the case, then the above is pretty much the best you can do. 
The critical step (the one which dominates any execution time) will be 
the 'begins with' and 'contains' operation - and there is little you can 
do to speed these up *unless* there are constraints on the search 
string.

For example, if you are actually just wanting to search for single 
'words' in the records then you can pre-index all the words in the 
array:

-- Build Index
repeat for each key tKey in tArray
   repeat for each word tWord in tArray[tKey]
     put tKey & return after tIndex[tWord]
   end repeat
end repeat

-- Search for word tSearchWord
put tIndex[tSearchWord]

One thing to note is that 20000 records isn't all that many in the 
modern context - so a linear search is probably not going to cause you 
too many problems. However, if you are looking at this figure increasing 
in orders of magnitude then at some point you should probably consider 
moving to an SQLite database or something similar to store the data. 
SQLite supports a 'full text search' index system, which enables fast 
searches for (albeit somewhat restricted) input strings and patterns.

Warmest Regards,

Mark.

-- 
Mark Waddingham ~ mark at livecode.com ~ http://www.livecode.com/
LiveCode: Everyone can create apps




More information about the use-livecode mailing list