Don't forget about subseq and rsubseq, the technology behind [the world's smallest time series database]( https://www.dotkam.com/2015/12/02/time-series-database-in-one-line-of-clojure/) ;)
On Monday, May 25, 2020 at 4:47:58 PM UTC-5, Harmon Nine wrote: > > Is there an optimization for sorted-maps that, when you have a given key > in the map, you can get the next key in O(log n) time? > > Given "compare" is the boolean function on which the sorted-map is based, > the following code will get the next-key given a current-key: > > (defn get-next-key [my-map current-key] > (first (filter #(compare current-key %) (keys my-map)))) > > > In the worst case, this would take O(n) time, as the "keys" function would > iterate through the n keys of the map. > > However, if it could be detected that the the filter is using the > "compare" function on which the map is based, this could speed up the > search: the "current-key" could be found first and iteration could start > from there. Then the "first" function could cut the search short, > resulting in worst-case O(log n) time to get the next key (given the > sorted-map is based on a tree). > > > Does such an optimization exist? If not, is there an means of getting the > next-key in a sorted-map given a current-key that is better than O(n)? > > Thanks :) > -- Harmon > -- 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 unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/clojure/105cdb78-e4b2-43d4-896f-91315de24760%40googlegroups.com.
