Поиск ключей, ближайших к заданному значению для сортированных карт 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-ю запись на карте, я мог бы сколотить функцию, подобную той, которую я хочу, но я не могу найти такую ​​функцию.

Edit:

Таким образом, очевидно отсортировано-карта основана на классе PersistentTreeMap реализован в Java, который является красным и черным деревом. Так что действительно кажется, что это должно быть выполнимо, по крайней мере, в принципе.

Answer 1

после- и 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.avl. Он поддерживает сортированные карты с ближайшей функцией и другими полезными функциями.

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