New topic: fastest method for Key paired values lookup
<http://forums.realsoftware.com/viewtopic.php?t=44042> Page 1 of 2 [ 20 posts ] Go to page 1, 2 Next Previous topic | Next topic Author Message Poco Post subject: fastest method for Key paired values lookupPosted: Thu May 17, 2012 3:50 am Joined: Sun Oct 04, 2009 1:05 pm Posts: 65 Location: FRANCE Hi All, In my app I receive data from USB. Every time a data is posted (I use a Timer.period = 100 for the moment), I need to read that value and correct it with an associated value in a table. For instance : I USB sends "1,000"; then I need to find in a "table/dictionary/...." the value "1,000" and correct it with the associated value in that table. This needs to be as fast as possible. What would you recomand? _________________ TIA, Configuration : MBA Mac OS Snow Real Studio 2010 r5 Top DaveS Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 8:40 am Joined: Sun Aug 05, 2007 10:46 am Posts: 3700 Location: San Diego, CA If your entries are unique ... you only have ONE entry for "1,000" as the key then use a Dictionary look up HASKEY function _________________ Dave Sisemore MacPro, OSX 10.7.3 RB2011r3 Note : I am not interested in any solutions that involve custom Plug-ins of any kind Top Poco Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 8:48 am Joined: Sun Oct 04, 2009 1:05 pm Posts: 65 Location: FRANCE The first "row" is a list of 8,000 ordered integer. The second "row is Integer. Is my strategy ok for speed? - At startup read the text file containing the values and store it in a dictionay. Thus it will be stored in RAM (yes?) and the access will be quicker Thanks for your help. _________________ TIA, Configuration : MBA Mac OS Snow Real Studio 2010 r5 Top Jason_Adams Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 9:25 am Joined: Fri Nov 10, 2006 4:10 pm Posts: 1570 Location: Michigan, USA It doesn't really matter what the key-value types are, so long as the keys remain unique. Yes, this keeps everything in memory (so be mindful of this), but that will yield the fastest solution. Hope this helps. _________________ Windows 7 Ultimate x64 Windows XP Pro SP3 Ubuntu 11.04 via Virtual Box RS Enterprise 2011r4 Programming Tutorials & Free Projects: http://www.JasonTheAdams.com "Christianity has not been tried and found wanting; it has been found difficult and not tried." - G.K. Chesterton Top Jym Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 9:35 am Joined: Sat Oct 01, 2005 5:19 pm Posts: 3048 Really? A dictionary is faster than in-memory database? I find that hard to believe. I can get an array of classes to 'find' faster than dictionary (or at least it was that way in 2008 ish) Top Jason_Adams Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 9:46 am Joined: Fri Nov 10, 2006 4:10 pm Posts: 1570 Location: Michigan, USA Jym wrote:Really? A dictionary is faster than in-memory database? I find that hard to believe. I can get an array of classes to 'find' faster than dictionary (or at least it was that way in 2008 ish) I honestly don't know. That'd be an interesting test. I suspect it depends on the size and complexity of what's being stored. The dictionary has the immediate advantage of not having to serialize/de-serialize class types. I believe what would eventually do in the Dictionary is how quickly it will consume memory in comparison to the database which will work with memory and disk. So, in true programmer fashion, my response will be: it depends. _________________ Windows 7 Ultimate x64 Windows XP Pro SP3 Ubuntu 11.04 via Virtual Box RS Enterprise 2011r4 Programming Tutorials & Free Projects: http://www.JasonTheAdams.com "Christianity has not been tried and found wanting; it has been found difficult and not tried." - G.K. Chesterton Top Poco Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 10:48 am Joined: Sun Oct 04, 2009 1:05 pm Posts: 65 Location: FRANCE Jym wrote:Really? A dictionary is faster than in-memory database? I find that hard to believe. I can get an array of classes to 'find' faster than dictionary (or at least it was that way in 2008 ish) How do you program an in-memory database? DB are usually stored on files on disk? _________________ TIA, Configuration : MBA Mac OS Snow Real Studio 2010 r5 Top DaveS Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 10:55 am Joined: Sun Aug 05, 2007 10:46 am Posts: 3700 Location: San Diego, CA For a list of 8,000 ordered pairs of integers... I would say a Dictionary would be much faster. and if that 8000 is actually 1 to 8000 then an ARRAY of 8000 items would be faster still.... but ONLY if the keys were consecutive and sequential. for that matter.... depending on the lowest/highest value.. a sparsely populated array might even be a possiblity. _________________ Dave Sisemore MacPro, OSX 10.7.3 RB2011r3 Note : I am not interested in any solutions that involve custom Plug-ins of any kind Top Jym Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 11:57 am Joined: Sat Oct 01, 2005 5:19 pm Posts: 3048 I agree that if the integers are sequential then an array is your best bet but if they aren't an In-Memory database is much faster than a dictionary, but it depends on what your idea of fast is. An in-memory database on an i7 can return a recordset from 8000 records in about .02 seconds and a dictionary is .06 seconds a loop through an array of classes is .05 seconds. Top Poco Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 11:58 am Joined: Sun Oct 04, 2009 1:05 pm Posts: 65 Location: FRANCE Key is ALL integer from 0 to 8,000 (1, 2, 3, 4 5,............,79999, 8000) _________________ TIA, Configuration : MBA Mac OS Snow Real Studio 2010 r5 Top taylor-design Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 12:06 pm Joined: Wed Mar 22, 2006 11:15 am Posts: 293 Location: Southern California Poco wrote:Key is ALL integer from 0 to 8,000 (1, 2, 3, 4 5,............,79999, 8000) Create an integer array of your values where Key is your index into the array to retrieve Value. Make sure you use the following pragmas in the function(s) which need to "run as fast as possible", making sure of course that you do not completely block up the UI and framework. #Pragma BackgroundTasks False #Pragma BoundsChecking False _________________ Daniel L. Taylor Taylor Design Computer Consulting & Software Development [email protected] http://www.taylor-design.com Top taylor-design Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 1:05 pm Joined: Wed Mar 22, 2006 11:15 am Posts: 293 Location: Southern California Jym wrote:I agree that if the integers are sequential then an array is your best bet but if they aren't an In-Memory database is much faster than a dictionary, but it depends on what your idea of fast is. An in-memory database on an i7 can return a recordset from 8000 records in about .02 seconds and a dictionary is .06 seconds a loop through an array of classes is .05 seconds. I'm guessing that you're timing single record access without pragmas and that background tasks or timing resolution are throwing off the results. Looping through an array is the worst possible solution and shouldn't even be in the same ballpark as Dictionary. That said, a single record retrieved via any of these methods should be faster than 0.0x seconds. Out of curiosity I created a quick test app which tests the following: Direct array lookup Array search loop Array binary (half interval) search Dictionary search RAM REALSQLDatabase indexed table search The app creates records 0-8000 for each storage medium (array, dictionary, sql). It then finds every single value once, with BackgroundTasks and BoundsChecking off, timed using Microseconds. Machine is a MacBook Pro 2.7 GHz i7. Below is the average of 5 runs in a Carbon compiled application followed by the estimated time for a single access (total / 8,001). Times are in Microseconds. Direct array lookup: 916 / <1 Array search loop: 2,063,726 (2 seconds) / 258* Array binary (half interval) search: 4,000 / <1 Dictionary search: 10,089 / 1 RAM REALSQLDatabase indexed table search: 209,331 / 26 * Looping through an array and comparing values will yield drastically different times for a single access depending on the size of the array and the final result. A match at index 0 will come back much faster then a match at index 8,000. The larger the array, the greater the worst possible time will be. The result that surprised me the most was the binary search. In the debugger this took twice as long as Dictionary. In compiled code it's more than twice as fast. _________________ Daniel L. Taylor Taylor Design Computer Consulting & Software Development [email protected] http://www.taylor-design.com Top Poco Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 1:41 pm Joined: Sun Oct 04, 2009 1:05 pm Posts: 65 Location: FRANCE Then direct Array lookup is the fastest way to do this? I was trying to imagine a quikest way and I thought that if I had less values in my Array/Dictionary... lookup would faster, yes? Then what if I had larger" intervals? Instead of : 1, 2, 3, 4, 5...... 8,000 I had keys : 1, 5, 10, 15, ....... 8,000 Would it be 5x faster? Is it linear? But if I could do this I would have for every values between keys (ie. 2, 3, 4, 6, 7, 8...) to find the closest key and apply the corresponding correction factor. If experimentally I find the possibility to reduce the keys, would it be still faster this way? _________________ TIA, Configuration : MBA Mac OS Snow Real Studio 2010 r5 Top taylor-design Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 2:24 pm Joined: Wed Mar 22, 2006 11:15 am Posts: 293 Location: Southern California Poco wrote:Then direct Array lookup is the fastest way to do this? In the case where your Keys are 0-8000 and can therefore serve as indexes into the array, yes, by far. Quote:I was trying to imagine a quikest way and I thought that if I had less values in my Array/Dictionary... lookup would faster, yes? Size won't matter if the Key is the index. myArray(0), myArray(8000), and myArray(8000000) will take the same amount of time. Perhaps the confusion is because you're thinking of IndexOf. We're not telling you to use IndexOf, but to treat the input value/Key as the actual array index. (Note: I didn't test IndexOf. The array search loop was designed to simulate looping through an array of classes and comparing properties. I might test IndexOf as well, but my guess is that it will be one of the slower options.) In a situation where you have to search, where the Keys are not 0-8000 but are random, then reducing the size of the set will speed up IndexOf and Dictionary.Lookup. I'm guessing IndexOf will be linear, i.e. half the size will double the speed. But it would not dramatically alter Dictionary.Lookup, a binary search, or a RAM database. But again, if your Key can serve as an index into the array, then the array size will not matter. You are not actually searching anything in that case. That's why it's so much faster. You're just telling the compiler to return a value at an offset in memory. Quote:But if I could do this I would have for every values between keys (ie. 2, 3, 4, 6, 7, 8...) to find the closest key and apply the corresponding correction factor. If experimentally I find the possibility to reduce the keys, would it be still faster this way? No. The code to correct for values between intervals of 5 would only add time. By the way, if your output values can be determined by a single mathematical operation, that would probably be even faster. If your USB device is giving you 0-8000 and you need to return the input value + 10000, then just add 10000 to get your output value. (I'm guessing that's not the case, but if it ever is...) _________________ Daniel L. Taylor Taylor Design Computer Consulting & Software Development [email protected] http://www.taylor-design.com Top Jym Post subject: Re: fastest method for Key paired values lookupPosted: Thu May 17, 2012 2:26 pm Joined: Sat Oct 01, 2005 5:19 pm Posts: 3048 taylor-design wrote:Times are in Microseconds. Direct array lookup: 916 / <1 Array search loop: 2,063,726 (2 seconds) / 258* Array binary (half interval) search: 4,000 / <1 Dictionary search: 10,089 / 1 RAM REALSQLDatabase indexed table search: 209,331 / 26 * Looping through an array and comparing values will yield drastically different times for a single access depending on the size of the array and the final result. A match at index 0 will come back much faster then a match at index 8,000. The larger the array, the greater the worst possible time will be. Is that a Mac issue? Just using 8,000 entries in a Class Array on a PC I get 1100 ms to find where myKey = 7999. 2080 ms In Memory SQLite where s = 7999 790 ms using a direct array 6300 ms using a dictionary What code are you using? Last edited by Jym on Thu May 17, 2012 2:39 pm, edited 1 time in total. Top Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending Page 1 of 2 [ 20 posts ] Go to page 1, 2 Next -- Over 1500 classes with 29000 functions in one REALbasic plug-in collection. The Monkeybread Software Realbasic Plugin v9.3. http://www.monkeybreadsoftware.de/realbasic/plugins.shtml [email protected]
