Разница между двумя картами

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 также подойдет, если повышение производительности будет значительным.

Для чего бы это ни стоило, мой основной тестовый пример / ожидание поведения состоит в том, что следующее будет равным (вплоть до эквивалентности null = "Не присутствует") для любых двух карт a и b:

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 предлагают довольно эффективное решение .

Answer 3

Я не уверен в его производительности

(defn map-difference
  [orig other]
  (let [changed (set/difference (set orig) (set other))
        added (set/difference (set (keys other)) (set (keys orig)))]
    (reduce (fn [acc key]
              (assoc acc key :missing))
      (into {} changed)
      added)))

Я использовал ключ :missing, чтобы избежать неоднозначности между значением nil в исходной карте и отсутствующим ключом - вы, конечно, можете изменитьэто к nil.

Answer 4

Используйте API встроенных коллекций:

Set<Map.Entry<K,V>> difference = a.entrySet().removeAll(b.entrySet());

Если вам нужно преобразовать это обратно в карту, вы должны выполнить итерацию.В этом случае я предлагаю:

Map<K,V> result = new HashMap<K,V>(Math.max(a.size()), b.size()));
Set<Map.Entry<K,V>> filter = b.entrySet();
for( Map.Entry<K,V> entry : a.entrySet ) {
    if( !filter.contains( entry ) {
        result.put(entry.getKey(), entry.getValue());
    }
}

Answer 5

1. Карты Clojure будут в порядке, поскольку чтение карт Clojure выполняется очень быстро.

2. Я не могу ответить вам, но могу дать вам на что посмотреть. Брентон Эшворт создал тестовый инструмент, где решил проблему с сопоставлением карт. Может быть, вы можете посмотреть на его код, чтобы получить подсказку для реализации. http://formpluslogic.blogspot.com/2010/07/better-clojure-test-results-with-deview.html а также http://github.com/brentonashworth/deview

3. Я не думаю, что есть лучшая реализация, которая сравнивает ключи и смотрит, если они разные.

Answer 6

Вы также можете просто использовать Maps.difference (..) метод из библиотек Google Guava

Answer 7

А как же ...

(defn map-diff [m1 m2]
  ;; m1: hashmap
  ;; m2: hashmap
  ;; => the difference between them
  (reduce merge
          (map #(hash-map % (- (or (% m1) 0) (or (% m2) 0)))
               (keys (merge m1 m2)))))