On Mon, 19 Oct 2009, nchubrich <nicholas.chubr...@gmail.com> writes: > I need to make a data structure for a query such as "find everything > that is priced $3.27 - $6.12" (and perhaps sum up the total revenue > for all items in that price range). The naive way would be to make an > array with one slot for each increment in the entire range, and have > each slot pointing to a bucket with all items at that increment (here, > price). But this would not be terribly efficient or feasible over > very large ranges (imagine you wanted to query both large and small > ranges: think of distances on a galactic, planetary, continental, > city, human, etc. scale. Do you make multiple indices for coarse- > grained and small-grained queries? Do you have coarse-grained slots > pointing to smaller ranges, and so on ad infinitum? But that would > seem to make evaluating large ranges very inefficient). Is there a > cleverer/Clojurisher way to do it? The price example is what I'm > doing, so I don't really need a galactiscalable data structure....
I think what you are after is an interval tree[1] data structure. You might find a suitable Java library or implement yours easily. Regards. [1] http://en.wikipedia.org/wiki/Interval_tree --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
