尋找與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個條目，我可以拼湊出像我想要的那樣的功能，但是我找不到任何這樣的功能。

編輯：

因此很明顯，排序的地圖是基於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方法未公開，因此自定義遍歷當前不可用。

Answer 2

我想到的第一件事就是將地圖的關鍵點拉到一個向量中，然後在其中進行二分搜索。如果沒有與您的密鑰完全匹配，那麼涉及二進制搜索的兩個指針最終將指向它的兩側的兩個元素，然後您可以在單個（可能是平局）操作中選擇更接近的元素。

Answer 3

使用Clojure contrib庫data.avl。它支持具有最近功能和其他有用功能的排序圖。

https://github.com/clojure/data.avl