两张地图的区别 [英] Difference between two maps

问题描述

我需要非常有效地比较 Clojure/Java 中的两个映射，并返回由 Java 的 .equals(..) 确定的差异，nil/null 相当于不存在".

I need to very efficiently compare two maps in Clojure/Java, and return the difference as determined by Java's .equals(..), with nil/null equivalent to "not present".

即我正在寻找编写函数的最有效方法，例如:

i.e. I am looking for the most efficient way to a write a function like:

(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 映射也可以.

I'd prefer an immutable Clojure map as output, but a Java map would also be fine if the performance improvement would be significant.

就其价值而言，我的基本测试用例/行为预期是，对于任意两个映射 a 和 b，以下内容将相等(直到 null = "Not present" 的等价):

For what it's worth, my basic test case / expectation of behaviour is that the following will be equal (up to the equivalence of null = "Not present") for any two maps a and b:

a 
(merge b (difference a b))

实现这一目标的最佳方法是什么?

What would be the best way to implement this?

推荐答案

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

I'm not sure what the absolutely most efficient way to do this is, but here's a couple of things which may be useful:

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

1. The basic expectation of behaviour from the question text is impossible: if a and b are maps such that b contains at least one key not present in a, (merge b <sth>) cannot be equal to a.

如果您最终选择了互操作解决方案，但在某些时候又需要回到 PersistentHashMap，那么总是有

If you end up going with an interop solution but then need to go back to a PersistentHashMap at some point, there's always

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

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

If you need to pass the keyset of a Clojure map to a Java method, you can use

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

如果所有涉及的键都保证是 Comparable，那么这可以用于在具有许多键的映射上高效计算 difference(排序和合并扫描).对于不受约束的键，这当然是行不通的，对于小地图，它实际上可能会损害性能.

If all keys involved are guaranteed to be Comparable, this could be exploited for efficient computation of difference on maps with many keys (sort & merge scan). For unconstrained keys this is of course a no-go and for small maps it could actually hurt performance.

用 Clojure 编写一个版本是很好的，如果只是为了设置一个基准性能期望.这是一个:(更新)

It's good to have a version written in Clojure, if only to set a baseline performance expectation. Here is one: (updated)

(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)) 并可能重复某些工作可能比检查给定键在另一个映射中"更有效每一步也是如此.

I think that just doing (concat (keys m1) (keys m2)) and possibly duplicating some work is likely more efficient most of the time than checking a given key is in "the other map" too at every step.

总结答案，这里有一个非常简单的基于集合的版本，它具有很好的属性，它说明了它的作用——如果我误解了规范，这里应该很明显.:-)

To wrap up the answer, here's a very simple-minded set-based version with the nice property that it says what it does -- if I misunderstood the spec, it should be readily apparent here. :-)

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

这篇关于两张地图的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！