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

Мне нужно очень эффективно сравнивать две карты в Clojure/Java и возвращать разницу, как определено Java.equals(..), с нулевым/нулевым эквивалентом "нет".

то есть. Я ищу наиболее эффективный способ написать такую ​​функцию, как:

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

Каким будет лучший способ реализовать это?

Ответы

Ответ 1

Я не уверен, что самый эффективный способ сделать это, но вот несколько вещей, которые могут быть полезны:

  • Основное ожидание поведения из текста вопроса невозможно: если a и b являются такими картами, что b содержит хотя бы один ключ, отсутствующий в a, (merge b <sth>) не может быть равным a.

  • Если вы закончите работу с interop-решением, но в какой-то момент вам нужно вернуться к 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 на картах со многими ключами (сортировка и слияние). Для неограниченных ключей это, конечно, не-go и для небольших карт, это может реально повредить производительность.

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

Ответ 3

  • Clojure карты будут точными, потому что чтение карт clojure происходит очень быстро.

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

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

Ответ 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());
    }
}

Ответ 5

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

(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.

Ответ 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)))))