两张地图之间的差异

Question

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

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

Answer 1

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

1. 问题文本中对行为的基本期望是不可能的:如果a和b是b包含至少一个不存在的密钥的映射a,(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. 如果保证所涉及的所有密钥都是可用的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)))))

Answer 2

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