两张图的区别 [英] Difference between two maps
问题描述
我需要用Clojure / Java的非常有效地比较两个图,并通过Java的.equals确定返回的差异(..),与无/空等同于不present。
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}
我preFER一个不变的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.
有关它的价值,行为我的基本测试用例/意料的是,以下将是相等的(最多为null =未present的等价)的任何两个映射a和b:
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:
-
从问题文本行为的基本期望是不可能的:如果
A
和B
的地图这样B
至少包含一个关键的不是present在A
,(合并b将某物>)
不等于A
The basic expectation of behaviour from the question text is impossible: if
a
andb
are maps such thatb
contains at least one key not present ina
,(merge b <sth>)
cannot be equal toa
.
如果你结束了一个互操作的解决方案去但需要回到一个 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]>
如果参与,保证所有的键是可比
,这可以被利用为有效计算的区别
在地图上有许多键(分页和放大器;合并扫描)。对于不受约束键这当然是一个不走,并为小地图它实际上损害的表现。
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(键M1)(键2))
并有可能重复一些工作可能比检查给定的键更高效的大部分时间在其他图也步步为营。
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屋!