2009-12-30 8 views
9

Pour la carte triée de clojure, comment trouver l'entrée ayant la clé la plus proche d'une valeur donnée?Recherche des clés les plus proches d'une valeur donnée pour les cartes triées clojure

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.

Répondre

12

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.

+0

+1. Merci, c'est très utile. –

0

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).

+0

Depuis la carte est déjà triée, je (je l'espère) ne devrait pas avoir à tirer toutes les clés de la carte. –

+0

D'accord; mais je ne vois pas d'autre moyen d'obtenir un accès aléatoire aux touches. Si vous faites une recherche séquentielle, en moyenne vous devez comparer 50% des clés, alors que ma solution nécessite une copie à 100% - c'est horrible - et ALORS une recherche de log2 (n). Ma solution n'est bonne que si vous effectuez plusieurs recherches sur les mêmes données. Peut-être que quelqu'un de plus intelligent se présentera et affichera une solution qui nous étonnera tous. –