Вопросы Теги

Различие между двумя картами

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

т.е. Я ищу самый эффективный путь к записи функция как:

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

a 
(merge b (difference a b))

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

17
задан S.L. Barth - Reinstate Monica 17 July 2012 в 16:39
поделиться

5 ответов

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

  1. Базовое ожидание поведения из текста вопроса невозможно: if a и b - это карты, такие что b содержит по крайней мере один ключ, отсутствующий в a , (объединить b ) не может быть равным a .

  2. Если вы в конечном итоге выберете решение для взаимодействия, но в какой-то момент вам потребуется вернуться к PersistentHashMap , всегда будет 

     (clojure.lang.PersistentHashMap / create
 (doto (java.util.HashMap.)
 (.put: foo 1)
 (.put: бар 2)))
; => {: foo 1: bar 2}

  3. Если вам нужно передать набор ключей карты Clojure в метод Java, вы можете использовать 

     (. KeySet {: foo 1: bar 2})
; => # <[: foo,: bar]>

  4. Если все задействованные ключи гарантированно Сопоставимые , это может быть использовано для эффективного вычисления разницы на картах с множеством ключей (сканирование сортировки и слияния). Для неограниченных клавиш это, конечно же, недопустимо, а для небольших карт это может действительно снизить производительность.

  5. Хорошо иметь версию, написанную на Clojure, хотя бы для того, чтобы установить базовую ожидаемую производительность.Вот один: (обновлено) 

     (defn map-difference [m1 m2]
 (цикл [м (переходный {})
ks (concat (ключи m1) (ключи m2))]
 (if-let [k (first ks)]
 (пусть [e1 (найдите m1 k)
e2 (найти m2 k)]
 (cond (и e1 e2 (not = (e1 1) (e2 1))) (recur (assoc! m k (e1 1)) (next ks))
 (не e1) (recur (assoc! m k (e2 1)) (следующий ks))
 (не e2) (recur (assoc! m k (e1 1)) (следующий ks))
 : else (recur m (следующий ks))))
 (упорный! м))))

    Я думаю, что простое выполнение (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)))))
11
ответ дан 30 November 2019 в 12:50
поделиться

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

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

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

3
ответ дан 30 November 2019 в 12:50
поделиться

Используйте встроенный 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());
    }
}
3
ответ дан 30 November 2019 в 12:50
поделиться

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

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

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

3
ответ дан 30 November 2019 в 12:50
поделиться

В Java Коллекции Google Commons предлагают весьма производительное решение .

6
ответ дан 30 November 2019 в 12:50
поделиться
Другие вопросы по тегам:

Похожие вопросы: