Alex Osborne wrote: > nchubrich wrote: >> 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). > > > That's one of the things sorted maps are for: > > (let [objects-by-price (sorted-map 0.50 :cookie, 5.0 :lunch, > 6.10 :movie, 200.0 :tv)] > (take-while #(<= (key %) 6.12) (subseq objects-by-price >= 3.27))) > > > => ([5.0 :lunch] [6.1 :movie]) > >
>> 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 Also, if you're wondering how sorted-map makes that fast, see: http://en.wikipedia.org/wiki/Binary_search_tree It just does a search and then traverses the tree from that point, so it takes O((log n) + m) time where n is the size of the tree and m is the number of items your query returns. Richard's suggestion of binary search in a sorted array is also a good option but is a bit of a pain if you need to add new items to the array. http://en.wikipedia.org/wiki/Binary_search --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
