Нахождение ключей, самых близких к данному значению для clojure отсортированных карт
Для отсортированной карты clojure, как я нахожу запись, имеющую ключ самый близкий к данному значению?
например, Предположим, что я имею
(def my-map (sorted-map
1 A
2 B
5 C))
Я хотел бы функцию как
(find-closest my-map 4)
который возвратился бы (5, C), так как это - запись с самым близким ключом. Я мог сделать линейный поиск, но так как карта отсортирована, должен быть способ найти это значение в чем-то как O (зарегистрируйте n).
Я ничего не могу найти в API, который делает это возможным. Если, например, я мог бы попросить i'th запись в карте, я мог починить функцию как та, которую я хочу, но я не могу найти никакую подобную функцию.
Править:
Таким образом, по-видимому, отсортированная карта основана на классе PersistentTreeMap, реализованном в Java, который является красно-черным деревом. Таким образом, это действительно кажется, что должно быть выполнимо по крайней мере в принципе.
2 ответа
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), но .левый и .правый методы не являются публичными, поэтому пользовательский обход в настоящее время невозможен.
.Первое, что приходит мне в голову, это вытащить ключи карты в вектор, а затем выполнить двоичный поиск в нем. Если нет точного совпадения с Вашим ключом, то два указателя, участвующие в двоичном поиске, в конечном итоге будут указывать на два элемента по обе стороны от него, а затем Вы можете выбрать более близкий в единственной (возможно, срыва связки) операции.
.