java - ejemplo - Diferencia entre dos mapas

hashmap java ejemplo

Question

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

Es decir, estoy buscando la forma más eficiente de 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 salida, pero un mapa de Java también estaría bien si la mejora de rendimiento fuera significativa.

Para lo que vale, mi caso de prueba básico / expectativa de comportamiento es que lo siguiente será igual (hasta la equivalencia de null = "No presente") para cualquiera de los dos mapas a y b:

a
(merge b (difference a b))

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

Answer 1

1. Los mapas de clojure estarán bien porque la lectura de mapas de clojure es muy rápida.

2. No puedo responderte, pero puedo darte algo que mirar. Brenton Ashworth hizo una herramienta de prueba donde resolvió el problema con comparaciones de mapas. Tal vez usted puede mirar su código para obtener una pista para 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 haya una mejor implementación que compare las claves y busque si son diferentes.

Answer 2

En Java, Google Commons Collections ofrece una solución bastante eficaz .

Answer 3

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

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

2. Si terminas yendo con una solución de interoperabilidad pero luego necesitas 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 necesita pasar el conjunto de claves de un mapa de Clojure a un método Java, puede usar

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

4. Si se garantiza que todas las claves involucradas sean Comparable , esto podría explotarse para un cálculo eficiente de la difference en los mapas con muchas claves (exploración de clasificación y fusión). Para las claves no restringidas, esto es, por supuesto, un no-go y para los mapas pequeños podría dañar el rendimiento.

5. Es bueno tener una versión escrita en Clojure, aunque solo sea para establecer una expectativa de rendimiento de referencia. Aquí hay 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 solo hacer (concat (keys m1) (keys m2)) y posiblemente duplicar un trabajo es probablemente más eficiente la mayor parte del tiempo que verificar una clave dada está en "el otro mapa" también en cada paso.

Para resumir la respuesta, aquí hay una versión basada en conjuntos muy simple con la bonita propiedad de que dice lo que hace: si entendí mal la especificación, debería 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 4

No estoy seguro 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)))

Utilicé :missing clave :missing para evitar la ambigüedad entre un valor nil en el mapa original y una clave faltante; por supuesto, puede cambiarlo a nil .

Answer 5

Qué pasa...

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

Answer 6

También puede utilizar el Maps.difference(..) de las bibliotecas de guayaba de Google.

Answer 7

Utilice la API de colecciones incorporadas:

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

Si necesita convertir eso de nuevo en un mapa, debe iterar. 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());
}
}