Diferencia entre dos mapas

Question

Necesito comparar muy eficientemente dos mapas en Clojure/Java, y devolver la diferencia según lo determinado por los .equals de Java (..), con nil/null equivalente a "no presente".

es decir, Busco la manera más eficiente para un escribir una función como:

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

preferiría un mapa de Clojure inmutable como de salida, pero un mapa Java también estaría bien si la mejora del rendimiento sería significativo.

Por lo que vale la pena, mi básico de casos de prueba/expectativa de comportamiento es que el siguiente será igual (hasta la equivalencia de null = "Ausente") para cualquier dos mapas A y B:

a 
(merge b (difference a b)) 

¿Cuál sería la mejor manera de implementar esto?

Answer 1

No estoy seguro de cuál es la forma absolutamente más eficiente para hacer esto es, pero aquí hay un par de cosas que pueden ser útiles:

1. El básico La expectativa de comportamiento del texto de la pregunta es imposible: si a y b son mapas tales que b contiene al menos una clave no presente en a, (merge b <sth>) no puede ser igual a a.

2. Si usted termina yendo con una solución de interoperabilidad pero luego tiene que volver a un PersistentHashMap en algún momento, siempre hay

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

3. Si tiene que pasar el conjunto de claves de un mapa Clojure a una método Java, puede utilizar

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

4. Si todas las claves involucradas están garantizados para ser Comparable, esto podría ser explotado para el cálculo eficiente de difference en los mapas con muchos clave s (ordena & merge scan). Para las claves sin restricciones esto es, por supuesto, un no-go y para los mapas pequeños realmente podría perjudicar el rendimiento.

5. Es bueno tener una versión escrita en Clojure, aunque solo sea para establecer una expectativa de rendimiento de referencia. He aquí uno: (actualizado)

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

   Creo que sólo haciendo (concat (keys m1) (keys m2)) y, posiblemente, la duplicación de un trabajo que es probable más eficiente la mayor parte del tiempo que la comprobación de una clave dada se encuentra en "el otro mapa" demasiado en cada paso.

para concluir la respuesta, he aquí una versión muy simplista basada en conjunto con la propiedad agradable que dice lo que hace - si no he entendido bien la especificación, debe ser fácilmente evidente aquí. :-)

(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. Clojure maps estará bien porque la lectura de los mapas de clojure es muy rápida.

2. No puedo responderle, pero puedo darle algo para ver. Brenton Ashworth hizo una prueba donde resolvió el problema con el mapa se compara. Tal vez puedas mirar su código para obtener una pista sobre la implementación. http://formpluslogic.blogspot.com/2010/07/better-clojure-test-results-with-deview.html y http://github.com/brentonashworth/deview

3. No creo que hay una mejor aplicación que compara las llaves y mirar hacia arriba si el son diferentes.

Answer 3

En Java, Google Commons Collections ofrece un bastante performant solution.

Answer 4

utiliza el incorporado en las colecciones API:

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

Si necesita convertir ese nuevo en un mapa, se debe repetir. En ese caso, sugiero:

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

No estoy seguro acerca de su rendimiento

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

Solía ​​:missing clave para evitar la ambigüedad entre un valor nil en el mapa original, y una falta fundamental - por supuesto puede cámbielo a nil.

Answer 6

También puedes, simplemente utilizar Maps.difference(..) método de bibliotecas de Google Guava

Answer 7

... ¿Qué hay 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)))))