Encontrar las teclas más cercanas a un valor dado para los mapas clasificados de Clojure

Question

Para el mapa ordenado de clojure, ¿cómo puedo encontrar la entrada que tiene la clave más cercana a un valor dado?

p. Ej. Supongamos que tengo

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

me gustaría una función como

(find-closest my-map 4) 

que volver (5, C), ya que es la entrada con la tecla más cercano. Podría hacer una búsqueda lineal, pero dado que el mapa está ordenado, debería haber una manera de encontrar este valor en algo como O (log n).

No puedo encontrar nada en la API que lo haga posible. Si, por ejemplo, pudiera solicitar la entrada número i en el mapa, podría improvisar una función como la que yo quiero, pero no puedo encontrar ninguna de esas funciones.

Editar:

Por tanto, aparentemente ordenados-mapa se basa en una clase PersistentTreeMap implementado en Java, que es un árbol de color rojo y negro. Así que esto realmente parece que debería ser factible, al menos en principio.

Answer 1

subseq y rsubseq son muy rápidos porque explotan la estructura de árbol:

(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 

Esto lo hace un poco más de trabajo que ideal, en el escenario ideal nos acaba de hacer una < = búsqueda a continuación, busque en el nodo de el derecho de verificar si hay algo más cerca en esa dirección. Puede acceder al árbol (.tree m) pero los métodos .left y .right no son públicos, por lo que no es posible realizar un recorrido personalizado.

Answer 2

Lo primero que me viene a la mente es sacar las claves del mapa en un vector y luego hacer una búsqueda binaria en eso. Si no hay una coincidencia exacta con su clave, los dos punteros implicados en una búsqueda binaria terminarán apuntando a los dos elementos a cada lado, y luego puede elegir el más cercano en una sola operación (posiblemente de desempate).

Answer 3

Utilice la biblioteca de contribucios Clojure data.avl. Admite mapas ordenados con la función más cercana y otras funciones útiles.

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