AW: fastes way to search an array?
Hi Mike, my first description wasn't very exact. Actually these are two different cases, which occur not together. One time I need a search with "begins" and another time with "contains". And I decided to stay with such a standard repeat loop thru the array, without extracting the keys before or using any extra commands like filter. Thanks for caring Tiemo -Ursprüngliche Nachricht- Von: use-livecode [mailto:use-livecode-boun...@lists.runrev.com] Im Auftrag von Mike Bonner Gesendet: Freitag, 24. April 2015 00:39 An: How to use LiveCode Betreff: Re: fastes way to search an array? Did some testing out of curiosity, and WOW this is fast. 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 The only question I have is.. why search for the same thing twice? If it "contains" it also "begins with" so its a redundant check. (making it faster) Am I missing something here? On Thu, Apr 23, 2015 at 4:01 PM, Geoff Canyon wrote: > On Wed, Apr 22, 2015 at 6:22 PM, Peter Haworth wrote: > > > Out of interest, I added a test which used combine and filter. It > > took around 3 times longer than the other two tests. > > > > Yeah, I didn't expect this to be competitive except under specific > circumstances -- if the filter command happens to be suited to the > (relatively complex) search performed, for example. I didn't see 3x, > more like 1.5x to 2x, but still, iterating is generally the way to go. > ___ > use-livecode mailing list > use-livecode@lists.runrev.com > Please visit this url to subscribe, unsubscribe and manage your > subscription preferences: > http://lists.runrev.com/mailman/listinfo/use-livecode > ___ use-livecode mailing list use-livecode@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-livecode ___ use-livecode mailing list use-livecode@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-livecode
AW: fastes way to search an array?
Mark, thank you for your comments Tiemo -Ursprüngliche Nachricht- Von: use-livecode [mailto:use-livecode-boun...@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 2 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[] = tArray[] = ... tArray[] = 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 2 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 ~ m...@livecode.com ~ http://www.livecode.com/ LiveCode: Everyone can create apps ___ use-livecode mailing list use-livecode@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-livecode ___ use-livecode mailing list use-livecode@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-livecode
AW: fastes way to search an array?
Thanks Richard and others for you helpful remarks Tiemo -Ursprüngliche Nachricht- Von: use-livecode [mailto:use-livecode-boun...@lists.runrev.com] Im Auftrag von Richard Gaskin Gesendet: Mittwoch, 22. April 2015 18:04 An: use-livecode@lists.runrev.com Betreff: Re: fastes way to search an array? Tiemo wrote: > I have an array with 2 records, where I want to extract all > records, which either "begins with" or "contains" a search string. > > Up to now I just loop thru the whole array, do the compare and > extract the result records. I wonder, if there is a way to speed > up this search? E.g., does it makes a difference, if I compare the > string in the key or the data of the array while looping thru? I > mean, would it make a difference, if I would create an "associative" > array, where my search looks up in the keys of the array, either by > looping thru the array, or by extracting first the keys of the array > into a separate variable, instead in the data of the original array? > > Would it make a difference looping thru a variable, which just > contains the keys of the array, instead of looping thru the complete > array, because of the smaller "footprint" in the memory? > > Or shouldn't I care about these differences and just let LC makes its > job? > > Any experiences welcome, I'm not entirely sure I understand the options you've described, but hopefully this will at least either help or be mildly amusing: go url "http://fourthworld.net/lc/array_access_speeds.livecode"; -- Richard Gaskin Fourth World Systems Software Design and Development for the Desktop, Mobile, and the Web ambassa...@fourthworld.comhttp://www.FourthWorld.com ___ use-livecode mailing list use-livecode@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-livecode ___ use-livecode mailing list use-livecode@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-livecode
AW: fastes way to search an array?
Hi Rick, On my new and fast development machine the search is pretty fast and optimization wouldn't be necessary. But I am not sure, how it behaves on old and weak computers out there in the wild. Perhaps I have to reactivate one of my old ones for testing. Splitting into alphabetical parts is in my case not possible, because of the "contains" search. Thanks for your ideas Tiemo -Ursprüngliche Nachricht- Von: use-livecode [mailto:use-livecode-boun...@lists.runrev.com] Im Auftrag von Rick Harrison Gesendet: Mittwoch, 22. April 2015 15:44 An: How to use LiveCode Betreff: Re: fastes way to search an array? Hi Tiemo, What is the average and worst time that it takes to search your 20,000 record array now? Are there users other than you involved? Is it worth the time it will take you to optimize the code for the faster execution? Now that you’ve hopefully answered these questions for yourself, and decided it’s worth the effort, let’s more things forward a little more. Is your array pre-sorted alphabetically? (Assuming you are aiming for that order.) If so, it might make sense to split your big array into smaller alphabetically sorted arrays. Then you can test for which array to search based on the first letter of the element you are searching for in the array, and search the smaller array. Do a few timed tests with your array search so you can measure how much of an improvement you have achieved. Good luck! Rick > On Apr 22, 2015, at 9:20 AM, Tiemo Hollmann TB wrote: > > Hello, > > I have an array with 2 records, where I want to extract all > records, which either "begins with" or "contains" a search string. > > Up to now I just loop thru the whole array, do the compare and extract > the result records. I wonder, if there is a way to speed up this > search? E.g., does it makes a difference, if I compare the string in > the key or the data of the array while looping thru? I mean, would it > make a difference, if I would create an "associative" array, where my > search looks up in the keys of the array, either by looping thru the > array, or by extracting first the keys of the array into a separate > variable, instead in the data of the original array? > > Would it make a difference looping thru a variable, which just > contains the keys of the array, instead of looping thru the complete > array, because of the smaller "footprint" in the memory? > > Or shouldn't I care about these differences and just let LC makes its job? > > Any experiences welcome, > > Tiemo > > ___ use-livecode mailing list use-livecode@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-livecode ___ use-livecode mailing list use-livecode@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-livecode