Hey Harmon,
On Tue, May 26 2020, Harmon Nine wrote:
> 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)?
I just had a look at clojure.core and found that subseq operates on a
sorted collection. Based on my quick test I think it can find the next
element in a sublinear number of comparisons:
(def ^:dynamic comparisons nil)
(defn count-comparisons [x]
(when comparisons (swap! comparisons inc))
x)
(def s (into (sorted-set-by (comp count-comparisons compare))
(range 1000)))
(= (for [i (range 1001)]
(first (subseq s > (- i 0.5))))
(concat (range 1000) [nil]))
;; true
(frequencies
(for [i (range 1001)]
(binding [comparisons (atom 0)]
(first (subseq s > (- i 0.5)))
@comparisons)))
;; => {10 256, 11 384, 12 192, 13 96, 14 56, 15 16, 16 1}
I can only confirm that this works for > and >= as the comparison,
though, which are interpreted relative to the sort order for the
collection. Switching the sort order in the collection effectively flips
the meaning of >, too.
(def s2 (into (sorted-set-by (comp - compare))
(range 1000)))
(= (for [i (range 1001)]
(first (subseq s2 > (- i 0.5))))
(cons nil (range 1000)))
;; true
Other comparisons seem to fall back to just calling take-while, which
doesn't seem right to me.
I hope that helps!
Carlo
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/clojure/87367nsl23.fsf%40gmail.com.
