两张地图之间的差异

我不确定做这件事最有效的方法是什么,但这里有一些可能有用的东西:

1. 从问题文本中对行为的基本期望是不可能的:如果 a 和 b 地图是这样的吗 乙 包含至少一个不在中的键 一 , (merge b <sth>) 不能等于 一 .

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

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

3. 如果需要将Culjule映射的密钥集传递给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! 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))))
   

   我想这只是在做 (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)))))

在爪哇,谷歌公共收藏提供了一个相当 performant solution .

1. Clojure地图会很好,因为阅读Clojure地图很快。

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

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

使用内置集合API:

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

如果需要将其转换回映射,则必须迭代。在这种情况下,我建议:

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

我不确定它的性能

(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 原始映射中的值和缺少的键——当然可以将其更改为 零 .

你也可以用 Maps.difference(..) 来自Google的guava库的方法

那……怎么样?

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