Différence entre deux cartes

Question

J'ai besoin de comparer très efficacement deux cartes dans Clojure/Java, et de retourner la différence comme déterminé par .equals de Java (..), avec nil/null équivalent à "non présent".

-à-dire que je suis à la recherche de la façon la plus efficace d'une écriture fonction comme:

(map-difference 
    {:a 1, :b nil, :c 2, :d 3} 
    {:a 1, :b "Hidden", :c 3, :e 5}) 

=> {:b nil, :c 2, :d 3, :e nil} 

Je préfère une carte immuable Clojure en sortie, mais une carte Java serait aussi bien si l'amélioration des performances serait significatif.

Pour ce que ça vaut, mon cas/attente du comportement de test de base est que le suivant sera égal (jusqu'à l'équivalence de null = « Inexistant ») pour tout deux cartes a et b:

a 
(merge b (difference a b)) 

Quelle serait la meilleure façon de mettre en œuvre cela?

Answer 1

Je ne suis pas sûr de ce que la façon absolument le plus efficace de le faire est, mais voici quelques choses qui peuvent être utiles:

1. La base l'attente du comportement du texte de la question est impossible: si a et b sont des cartes telles que b contient au moins une clé non présente dans a, (merge b <sth>) ne peut pas être égale à a.

2. Si vous finissez par aller avec une solution Interop mais faut ensuite revenir à un PersistentHashMap à un moment donné, il y a toujours

   (clojure.lang.PersistentHashMap/create 
   (doto (java.util.HashMap.) 
       (.put :foo 1) 
       (.put :bar 2))) 
   ; => {:foo 1 :bar 2} 
   

3. Si vous devez passer le keyset d'une carte Clojure à un méthode Java, vous pouvez utiliser

   (.keySet {:foo 1 :bar 2}) 
   ; => #< [:foo, :bar]> 
   

4. Si toutes les clés impliquées sont garantis Comparable, cela pourrait être exploité pour le calcul efficace des difference sur les cartes avec de nombreuses clés s (tri & scan de fusion). Pour les clés non contraintes, il s'agit bien sûr d'un non-go et pour les petites cartes, cela pourrait nuire à la performance.

5. Il est bon d'avoir une version écrite en Clojure, ne serait-ce que pour définir une attente de performance de base. Voici un: (mise à jour)

   (defn map-difference [m1 m2] 
        (loop [m (transient {}) 
          ks (concat (keys m1) (keys m2))] 
         (if-let [k (first ks)] 
         (let [e1 (find m1 k) 
           e2 (find m2 k)] 
          (cond (and e1 e2 (not= (e1 1) (e2 1))) (recur (assoc! m k (e1 1)) (next ks)) 
           (not e1) (recur (assoc! m k (e2 1)) (next ks)) 
           (not e2) (recur (assoc! m k (e1 1)) (next ks)) 
           :else (recur m (next ks)))) 
         (persistent! m)))) 
   

   Je pense que tout simplement faire (concat (keys m1) (keys m2)) et peut-être double emploi avec des travaux est probablement plus efficace la plupart du temps que la vérification d'une clé donnée est dans « l'autre carte » trop à chaque étape.

Pour terminer la réponse, voici une version de configuration très simple d'esprit avec la belle propriété qu'il dit ce qu'il fait - si je mal compris la spécification, il devrait être évident ici. :-)

(defn map-difference [m1 m2] 
    (let [ks1 (set (keys m1)) 
     ks2 (set (keys m2)) 
     ks1-ks2 (set/difference ks1 ks2) 
     ks2-ks1 (set/difference ks2 ks1) 
     ks1*ks2 (set/intersection ks1 ks2)] 
    (merge (select-keys m1 ks1-ks2) 
      (select-keys m2 ks2-ks1) 
      (select-keys m1 
         (remove (fn [k] (= (m1 k) (m2 k))) 
           ks1*ks2))))) 

Answer 2

1. Les cartes de Clojure fonctionneront très bien car la lecture des cartes de clojure est très rapide.

2. Je ne peux pas vous répondre mais je peux vous donner quelque chose à regarder. Brenton Ashworth a fait un testtool où il a résolu le problème avec la carte compare. Peut-être que vous pouvez regarder son code pour obtenir un indice pour la mise en œuvre. http://formpluslogic.blogspot.com/2010/07/better-clojure-test-results-with-deview.html et http://github.com/brentonashworth/deview

3. Je ne pense pas qu'il y ait une meilleure mise en œuvre qui comparent les clés et rechercher si le sont différents.

Answer 3

En Java, Google Commons Collections offre un performant solution assez.

Answer 4

Utilisez les API intégrée des collections:

Set<Map.Entry<K,V>> difference = a.entrySet().removeAll(b.entrySet()); 

Si vous avez besoin de convertir ce retour en une carte, vous devez itérer. Dans ce cas, je propose:

Map<K,V> result = new HashMap<K,V>(Math.max(a.size()), b.size())); 
Set<Map.Entry<K,V>> filter = b.entrySet(); 
for(Map.Entry<K,V> entry : a.entrySet) { 
    if(!filter.contains(entry) { 
     result.put(entry.getKey(), entry.getValue()); 
    } 
} 

Answer 5

Je ne suis pas sûr de ses performances

(defn map-difference 
    [orig other] 
    (let [changed (set/difference (set orig) (set other)) 
     added (set/difference (set (keys other)) (set (keys orig)))] 
    (reduce (fn [acc key] 
       (assoc acc key :missing)) 
     (into {} changed) 
     added))) 

je :missing clé pour éviter toute ambiguïté entre une valeur nil dans la carte d'origine, et un manque clé - vous pouvez bien sûr changez-le en nil.

Answer 6

Vous pouvez aussi utiliser la méthode Maps.difference(..) de bibliothèques Goyave Google

Answer 7

... Qu'en est-

(defn map-diff [m1 m2] 
    ;; m1: hashmap 
    ;; m2: hashmap 
    ;; => the difference between them 
    (reduce merge 
      (map #(hash-map % (- (or (% m1) 0) (or (% m2) 0))) 
       (keys (merge m1 m2)))))