查找最接近给定值的密钥,用于clojure排序映射

Question

对于clojure的排序映射,如何找到具有最接近给定值的键的条目？

例如,假设我有

(def my-map (sorted-map 
                      1 A 
                      2 B
                      5 C))

我想要一个像这样的功能

(find-closest my-map 4)

这将返回(5,C),因为那是具有最近键的条目.我可以做一个线性搜索,但由于地图已经排序,应该有一种方法可以找到像O(log n)这样的值.

我无法在API中找到使这成为可能的任何内容.例如,如果我可以在地图中询问第i个条目,我可以拼凑一个我想要的功能,但我找不到任何这样的功能.

编辑:

所以sort-map基于在java中实现的PersistentTreeMap类,它是一个红色和黑色的树.所以这看起来应该是可行的,至少在原则上是这样.

Answer 1

subseq和rsubseq非常快,因为它们利用树结构:

(def m (sorted-map 1 :a, 2 :b, 5 :c)) 

(defn abs [x] (if (neg? x) (- x) x))
(defn find-closest [sm k]
  (if-let [a (key (first (rsubseq sm <= k)))]
    (if (= a k)
      a
      (if-let [b (key (first (subseq sm >= k)))]
        (if (< (abs (- k b)) (abs (- k a)))
          b
          a)))
    (key (first (subseq sm >= k)))))

user=> (find-closest m 4)
5
user=> (find-closest m 3)
2

这比理想工作略多,在理想情况下我们只需要做<=搜索,然后查看右边的节点,检查是否有更接近该方向的信息.您可以访问树(.tree m),但.left和.right方法不公开,因此目前无法进行自定义遍历.