两张地图之间的差异

一尘不染

两张地图之间的差异

algorithm

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

即我正在寻找最有效的方法来编写类似的函数：

(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 =“不存在”的等价关系）：

a 
(merge b (difference a b))

实施此方法的最佳方法是什么？

阅读 347

2020-07-28

共1个答案

一尘不染

我不确定执行此操作最绝对有效的方法是什么，但是以下几项可能有用：

问题文本对行为的基本期望是不可能的：如果a和b是b包含至少一个不存在的键的映射a，(merge b <sth>)则不能等于a。
如果您最终使用了互操作性解决方案，但又需要回到PersistentHashMap某个点，那么总有

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

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

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

如果保证涉及的所有键都是Comparable，则可以利用它来有效地计算difference具有多个键的地图（排序和合并扫描）。对于不受约束的键，这当然是不行的；对于小地图，它实际上可能会损害性能。

如果仅是为了设定基准性能预期，最好用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)))))

2020-07-28