AW: fastes way to search an array?

[Tiemo Hollmann TB]

Mark, thank you for your comments
Tiemo

-----Ursprüngliche Nachricht-----
Von: use-livecode [mailto:use-livecode-bounces at lists.runrev.com] Im Auftrag
von Mark Waddingham
Gesendet: Donnerstag, 23. April 2015 11:03
An: How to use LiveCode
Betreff: Re: fastes way to search an array?

> 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

_______________________________________________
use-livecode mailing list
use-livecode at lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode