两张地图之间的差异

2022-09-02 20:58:51

我需要非常有效地比较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))

实现此目的的最佳方法是什么?


答案 1

我不确定这样做的绝对最有效的方法是什么,但这里有几件事可能是有用的:

  1. 从问题文本中对行为的基本期望是不可能的:如果 和 是这样的映射,则包含至少一个不存在于 中的键,则 不能等于 。abba(merge b <sth>)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. 如果涉及的所有键都保证是,则可以利用这一点在具有许多键的地图上进行有效计算(排序和合并扫描)。对于无约束的键,这当然是行不通的,对于小地图,它实际上可能会损害性能。Comparabledifference

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

答案 2

在Java中,Google Commons Collections提供了一个相当高性能的解决方案