Hi, there is no such optimization and that's not really feasible in the sorted-map impl. However there are other sorted map data structures like https://github.com/clojure/data.avl which have facilities in this area.
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/66b516c0-e4f6-46c4-9820-48fe449c885d%40googlegroups.com.
