Recherche des clés les plus proches d'une valeur donnée pour les cartes triées clojure

Question

Pour la carte triée de clojure, comment trouver l'entrée ayant la clé la plus proche d'une valeur donnée?

par exemple. Supposons que je

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

Je voudrais une fonction comme

(find-closest my-map 4) 

qui renverrait (5, C), puisque c'est l'entrée avec la clé la plus proche. Je pourrais faire une recherche linéaire, mais puisque la carte est triée, il devrait y avoir un moyen de trouver cette valeur dans quelque chose comme O (log n).

Je ne trouve rien dans l'API qui rende cela possible. Si, par exemple, je pouvais demander la cinquième entrée sur la carte, je pourrais concocter une fonction comme celle que je veux, mais je ne peux pas trouver une telle fonction.

Edit:

donc apparemment trié-carte est basée sur une classe PersistentTreeMap implémenté en Java, qui est un arbre rouge et noir. Donc, cela semble vraiment être faisable, au moins en principe.

Answer 1

subseq et rsubseq sont très rapides car ils exploitent la structure arborescente:

(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 

Cela fait un peu plus de travail que idéal, dans le scénario idéal, nous suffit de faire une < = recherche regarder alors au noeud le droit de vérifier s'il y a quelque chose de plus proche dans cette direction. Vous pouvez accéder à l'arborescence (.tree m) mais les méthodes .left et .right ne sont pas publiques, donc la traversée personnalisée n'est actuellement pas possible.

Answer 2

La première chose qui me vient à l'esprit est de tirer les clés de la carte dans un vecteur, puis d'y faire une recherche binaire. S'il n'y a pas de correspondance exacte avec votre clé, les deux pointeurs impliqués dans une recherche binaire finiront par pointer vers les deux éléments de chaque côté, et vous pourrez alors choisir le plus proche dans une seule opération (éventuellement rupture de lien).

Answer 3

Utilisez la bibliothèque contrib Clojure data.avl. Il prend en charge les cartes triées avec une fonction la plus proche et d'autres fonctionnalités utiles.

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