两张地图之间的差异

我需要非常有效地比较Clojure / Java中的两个映射，并返回由Java的.equals（..）确定的差异，其中nil / null等效于“not present”。

即我正在寻找一种最有效的方式来编写一个函数，如：

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

我更喜欢不可变的Clojure映射作为输出，但如果性能提升很重要，Java映射也会很好。

对于它的价值，我的基本测试用例/行为期望是对于任何两个映射a和b，以下将是相等的（最多等于null =“Not present”）：

 a (merge b (difference ab)) 

实现这个的最佳方法是什么？

Answer 1

我不确定最有效的方法是什么，但这里有一些可能有用的东西：

1. 问题文本中行为的基本期望是不可能的：如果a和b是映射使得b包含至少一个不存在于a键，则(merge b )不能等于a 。

2. 如果您最终使用互操作解决方案，但需要在某个时刻返回到PersistentHashMap ，那么总是

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

3. 如果需要将Clojure映射的键集传递给Java方法，则可以使用

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

4. 如果所有涉及的密钥都保证是可Comparable ，那么可以利用它来有效地计算具有许多密钥的映射上的difference （排序和合并扫描）。 对于无约束键，这当然是禁止的，对于小地图，它实际上可能会损害性能。

5. 如果只是为了设置基线性能预期，那么使用Clojure编写的版本是件好事。 这是一个:( 更新）

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

   我认为只是做(concat (keys m1) (keys m2))并且可能复制一些工作在大多数情况下比在每一步检查给定键在“另一个映射”中更有效。

为了总结答案，这里有一个非常简单的基于集合的版本，具有良好的属性，它说它做了什么 – 如果我误解了规范，它应该在这里很明显。 🙂

 (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

在Java中，Google Commons Collections提供了一个非常高性能的解决方案 。

Answer 3

1. Clojure地图很好，因为阅读clojure地图非常快。

2. 我不能回答你，但我可以给你一些看的东西。 Brenton Ashworth做了一个测试工具，用地图比较解决了问题。 也许您可以查看他的代码以获得实施提示。 http://formpluslogic.blogspot.com/2010/07/better-clojure-test-results-with-deview.html和http://github.com/brentonashworth/deview

3. 我不认为有更好的实现比较键和查找是否不同。

Answer 4

使用内置集合API：

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

如果需要将其转换回地图，则必须进行迭代。 在这种情况下，我建议：

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

Answer 5

我不确定它的表现

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

我使用:missing键以避免原始地图中的nil值与缺失键之间存在歧义 – 您当然可以将其更改为nil 。

Answer 6

您也可以使用Google的Guava库中的Maps.difference（..）方法

Answer 7

关于什么…

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