Trovare le chiavi più vicine ad un dato valore per le mappe ordinate del clojure

Question

Per la mappa ordinata del clojure, come trovo la voce che ha la chiave più vicina ad un dato valore?

ad es. Supponiamo che io sono

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

Vorrei una funzione come

(find-closest my-map 4) 

che sarebbe tornato (5, C), dato che è la voce con la chiave più vicina. Potrei fare una ricerca lineare, ma poiché la mappa è ordinata, dovrebbe esserci un modo per trovare questo valore in qualcosa come O (log n).

Non riesco a trovare nulla nell'API che lo rende possibile. Se, ad esempio, potessi chiedere l'entrata della mappa sulla mappa, potrei mettere insieme una funzione come quella che desidero, ma non riesco a trovare nessuna di tali funzioni.

Edit:

Quindi, apparentemente ordinato-mappa è basata su una classe PersistentTreeMap implementato in Java, che è un albero rosso e nero. Quindi sembra proprio che dovrebbe essere fattibile, almeno in linea di principio.

Answer 1

subseq e rsubseq sono molto veloci perché sfruttano la struttura ad albero:

(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 

Questo fa un po 'più di lavoro che ideale, nello scenario ideale avremmo basta fare una < = ricerca poi guardare il nodo il diritto di verificare se c'è qualcosa di più vicino in quella direzione. È possibile accedere all'albero (.tree m) ma i metodi .left e .right non sono pubblici, quindi non è attualmente possibile effettuare il traversal personalizzato.

Answer 2

La prima cosa che mi viene in mente è tirare le chiavi della mappa in un vettore e poi fare una ricerca binaria. Se non c'è corrispondenza esatta con la tua chiave, i due puntatori coinvolti in una ricerca binaria finiranno per indicare i due elementi su entrambi i lati della stessa, e potrai quindi scegliere quella più vicina in una singola operazione (possibilmente in pareggio).

Answer 3

Utilizzare la libreria contrib Clojure data.avl. Supporta mappe ordinate con una funzione più vicina e altre utili funzioni.

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