Développement Java
  1. Développement Java
  3. Différence entre deux cartes
Intereting Posts
L’initialisation d’object de style C # peut-elle être utilisée en Java? Quelle est la différence entre Handler, Runnable et Threads? Précision vs précision de System.nanoTime () Pourquoi JUnit TemporaryFolder n’est-il pas supprimé? À quoi sert ? Quand l’utiliser et quand ne pas l’utiliser? Faire correspondre (par exemple) une lettre Unicode avec une expression rationnelle Java Qu’est-ce qui est construit par convention dans l’explication détaillée de Gradle? Obtenir les coordonnées de la scène de l’acteur dans la table dans libGDX L’utilisation de jBCrypt pour saler les mots de passe dans l’application Android provoque un blocage long ‘Reentrancy’ en java Pourquoi LinkedList et Arraylist étendent AbstractList en Java? Comment faire une ArrayList en utilisant Javassist Aligner le paragraphe au centre de la page Implémenter une fonctionnalité d’accusé de lecture dans l’application de messagerie du groupe Firebase HtmlUnit télécharger les pièces jointes

Différence entre deux cartes

J’ai besoin de comparer très efficacement deux cartes dans Clojure / Java et de retourner la différence telle que déterminée par les .equals de Java (..), avec un équivalent nul / nul à “non présent”.

c’est à dire que je cherche le moyen le plus efficace d’écrire une 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érerais une carte immuable de Clojure en sortie, mais une carte Java serait également correcte si l’amélioration des performances était significative.

Pour ce que cela vaut, mon test élémentaire / l’attente de comportement est que ce qui suit sera égal (jusqu’à l’équivalence de null = “Non présent”) pour deux mappes a et b: 

 a (merge b (difference ab))

Quel serait le meilleur moyen de mettre en œuvre cela?

Je ne suis pas sûr de la manière la plus efficace de le faire, mais voici quelques éléments qui peuvent être utiles:

  1. L’attente de base du comportement à partir du texte de la question est impossible: si a et b sont des cartes telles que b contient au moins une clé absente dans a , (merge b ) ne peut pas être égale à a .

  2. Si vous vous retrouvez avec une solution d’interopérabilité, mais que vous devez 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 transmettre le jeu de clés d’une mappe Clojure à une méthode Java, vous pouvez utiliser 

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

  4. Si toutes les clés impliquées sont Comparable , cela pourrait être exploité pour un calcul efficace de la difference sur des cartes à plusieurs clés (parsing de sorting et fusion). Pour les clés non contraintes, il s’agit bien sûr d’une solution inacceptable et pour les petites cartes, les performances pourraient en souffrir.

  5. Il est bon d’avoir une version écrite en Clojure, ne serait-ce que pour définir une attente de performance de base. En voici un: (mis à 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! mk (e1 1)) (next ks)) (not e1) (recur (assoc! mk (e2 1)) (next ks)) (not e2) (recur (assoc! mk (e1 1)) (next ks)) :else (recur m (next ks)))) (persistent! m))))

    Je pense que le simple fait de faire (concat (keys m1) (keys m2)) et éventuellement de dupliquer certains travaux est probablement plus efficace que de vérifier qu’une clé donnée se trouve également dans «l’autre carte» à chaque étape.

Pour conclure, voici une version basée sur des ensembles très simple avec la propriété gentille qu’elle dit ce qu’elle fait – si j’ai mal compris la spécification, elle devrait être facilement visible 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)))))

En Java, Google Commons Collections offre une solution assez performante .

  1. Les cartes Clojure conviendront, 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 créé un outil de test où il a résolu le problème de la comparaison des cartes. Peut-être que vous pouvez regarder son code pour obtenir des conseils pour l’implémentation. 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 existe une meilleure implémentation qui compare les clés et regarde si elles sont différentes.

Utilisez l’API de collections intégrée: 

 Set> difference = a.entrySet().removeAll(b.entrySet());

Si vous devez le reconvertir en carte, vous devez l’itérer. Dans ce cas, je suggère: 

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

Je ne suis pas sûr de sa performance 

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

J’ai utilisé :missing touche :missing pour éviter toute ambiguïté entre une valeur nil dans la carte d’origine et une clé manquante – vous pouvez bien sûr la changer à nil .

Vous pouvez également utiliser la méthode Maps.difference (..) des bibliothèques Google de guava.

Qu’en est-il de… 

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