If you are happy with sorting the data already, then put the pairs into a sorted set, and use `subseq` and `rsubseq` to query.
Depending on the size of the data (i.e. how many coordinate pairs you have) and the specifics of your usage (i.e. mostly, how dynamic the dataset is), using a specialized data structure like an interval tree (or k-d or R*/R+ tree if you end up working with multidimensional data) is a must. Cheers, - Chas On Oct 20, 2012, at 10:27 PM, Brian Craft wrote: > I have a vector of maps representing intervals with (start, end) coords in > one dimension, that are non-overlapping, and sorted. At the moment I'm not > using a sorted data type, just a vector. > > The bottleneck in my code is in searching for intervals that overlap a > region, like so: > > (defn filter-probe-range [probes start end] > (filter #(and (> (:end %) start) (< (:start %) end)) probes)) > > My first thought to speed it up was to add a binary search on the vector, > since it's sorted. However, that is wildly slower than doing a full scan with > filter. I'm not sure why that is, or how to investigate it. I've looked over > the section on performance in "The Joy of..", but nothing is really popping > out. Should I start with jvisualvm? Is there something better that would > identify what I'm doing that's so slow? > > Also wondering if sorted data types would do this for me for free. Is there a > way to do a binary search on a sorted collection? > > -- > 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 -- 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
