Agreed, an rtree was not what I was balking about and loading into an rtree is an expensive one time process but it can be serialized to the device storage for quick loading.
I was balking at using a full on database solution :D Although I did just find out that the device OS uses SQLite for preferences storage, so maybe there is room for a DB in there. FYI this is just a RAD app that, like you mentioned is a list of stores and we want to hit the user with the closest store when they open the app. Imagine pressing a button on your phone and being presented with the nearest gas station to your current location already loaded into GPS & nav. That's pretty close to what I'm trying to achieve here. On Wed, Mar 19, 2014 at 7:30 AM, Joshua Marsh <[email protected]>wrote: > On Wed, Mar 19, 2014 at 12:39 AM, Tod Hansmann <[email protected] > >wrote: > > > I wasn't suggesting a database, that's just silly. I also work in > > resource constrained environments (sometimes as constrained as a PIC18), > > but that doesn't mean I wouldn't setup an in-memory tree of some sort > > (instead of the array/vector) if I needed to do a search a lot of times. > > Even a linked list could be sorted in various ways. Anyway, if it's an > > array/vector there's really no avoiding checking every single item, > because > > there's nothing saying the next item can't have a shorter distance > result. > > It's an easy calculation and all that, but it's still going to be O(n) > > regardless of the approach. > > > > > I think Tod has some good points about this. If the processing speed isn't > up to snuff, an O(n) loop could be very time consuming even with just a > thousand iterations. You probably won't have issues at a hundred, but you > should test the speed. Threads may help, but only if you actually have > multiple processors/cores to do the work. Otherwise, the threading will > just consume extra resources. > > R-Tree and it's variants are all fairly common for this task. If the data > points change infrequently (think a list of stores for an app that may only > be updated weekly), you should be able to serialize the R-Tree so you don't > have to rebuild it every time you load the application. > > Again, though, I'd suggest you do some real testing on a system that has > the resources you expect. On my laptop, the difference between R-Tree and > iterating over an array is unnoticeable for hundreds of records. If I do > millions of records though, it starts to become clear that the R-Tree is > faster. Just like most optimizations, it's a trade-off between the pain > your customers might feel and the pain you'll feel. I think though you > should wait to make a decision until you can empirically say that your > vector iteration is going to be a pain point for the average/worst case > scenarios. > > /* > PLUG: http://plug.org, #utah on irc.freenode.net > Unsubscribe: http://plug.org/mailman/options/plug > Don't fear the penguin. > */ > /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
