Как определить различия в двух списках данных

Это упражнение для парней из CS, чтобы осветить теорию.

Представьте, что у вас есть 2 контейнера с элементами. Папки, URL-адреса, файлы, строки, это действительно не имеет значения.

Что такое алгоритм AN для подсчета добавленного и удаленного?

Примечание: если есть много способов решить эту проблему, пожалуйста, опубликуйте по одному на ответ, чтобы его можно было проанализировать и проголосовать.

Изменить: Все ответы решить вопрос с 4 контейнерами. Можно ли использовать только начальные 2?

Источник

5 ответов

Решение

Предполагая, что у вас есть два списка уникальных предметов, и порядок не имеет значения, вы можете рассматривать их как наборы, а не списки

Если вы думаете о диаграмме Венна, со списком A в качестве одного круга и списком B в качестве другого, то пересечение этих двух является константой пула.

Удалите все элементы в этом пересечении как из A, так и из B, и все, что осталось в A, было удалено, в то время как все, что осталось в B, было добавлено.

Итак, перебираем A для поиска каждого элемента в B. Если вы найдете его, удалите его как из A, так и из B

Тогда A - это список вещей, которые были удалены, а B - это список вещей, которые были добавлены.

Я думаю...

[edit] Хорошо, с новым ограничением "только 2 контейнера", то же самое сохраняется:

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

Тогда вы не создаете новый список и не уничтожаете свои старые... но это займет больше времени, как в предыдущем примере, вы можете просто перебрать более короткий список и удалить элементы из более длинного. Здесь нужно сделать оба списка

И я бы сказал, что мое первое решение не использовало 4 контейнера, оно просто уничтожило два;-)

Источник

Я не делал этого в течение некоторого времени, но я считаю, что алгоритм идет так...

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

Что касается отношения правого списка к левому списку, удаление содержит удаленные элементы, а добавление теперь содержит новые элементы.

Источник

Что сказал Джо И, если списки слишком велики, чтобы поместиться в памяти, используйте утилиту сортировки внешних файлов или сортировку слиянием.

Источник

Отсутствующая информация: как вы определяете добавленные / удаленные? Например, если списки (A и B) показывают один и тот же каталог на сервере A и сервере B, который синхронизирован. Если я теперь подожду 10 дней, сгенерирую списки снова и сравню их, как я могу узнать, что что-то было удалено? Я не могу. Я могу только сказать, что на Сервере А есть файлы, которых нет на Сервере Б и / или наоборот. Это потому, что файл был добавлен на сервер A (таким образом, файл не найден на B) или файл был удален на сервере B (таким образом, файл больше не найден на B) - это то, что я не могу определить, просто имея список имен файлов.

Для решения, которое я предлагаю, я просто предположу, что у вас есть один список с именем OLD и один список с именем NEW. Все найденное на СТАРОМ, но не на НОВОМ было удалено. Все, что найдено в NEW, но не в OLD, было добавлено (например, содержимое одного и того же каталога на том же сервере, однако списки были созданы в разные даты).

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

В этом случае самое простое (не обязательно лучшее решение) это:

  1. Сортировка старых списков. Например, если список состоит из строк, сортируйте их по алфавиту. Сортировка необходима, потому что это означает, что я могу использовать бинарный поиск, чтобы быстро найти объект в списке, предполагая, что он там существует (или, чтобы быстро определить, его вообще нет в списке). Если список не отсортирован, поиск объекта имеет сложность O(n) (мне нужно посмотреть на каждый элемент в списке). Если список отсортирован, сложность составляет всего O(log n), так как после каждой попытки сопоставить элемент в списке я всегда могу исключить 50% элементов в списке, которые не совпадают. Даже если в списке содержится 100 элементов, для поиска элемента (или обнаружения того, что элемента нет в списке) требуется не более 7 тестов (или это 8? В любом случае, намного меньше 100). НОВЫЙ список не должен быть отсортирован.

  2. Сейчас мы выполняем удаление списка. Для каждого элемента в НОВОМ списке попробуйте найти этот элемент в СТАРОМ списке (используя бинарный поиск). Если элемент найден, удалите этот элемент из СТАРОГО списка, а также удалите его из НОВОГО списка. Это также означает, что списки уменьшаются по мере продвижения процесса исключения, и, следовательно, поиск будет выполняться все быстрее и быстрее. Поскольку удаление элемента из списка не влияет на правильный порядок сортировки списков, нет необходимости когда-либо прибегать к старому списку на этапе исключения.

  3. В конце исключения оба списка могут быть пустыми, и в этом случае они будут равны. Если они не пустые, все элементы, все еще находящиеся в старом списке, являются элементами, отсутствующими в новом списке (в противном случае мы их удалили), следовательно, это удаленные элементы. Все элементы, все еще находящиеся в списке NEW, являются элементами, которых не было в старом списке (опять же, мы удалили их в противном случае), следовательно, это добавленные элементы.

Источник

Являются ли объекты в списке "уникальными"? В этом случае я сначала построил бы две карты (hashmaps), а затем сканировал списки и просматривал каждый объект на картах.

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

Извините за ужасное смешение мета-языков Ruby и Java:-P

В конце концов, removeElements будет содержать элементы, принадлежащие списку list1, но не списку list2, а addElements будет содержать элементы, принадлежащие списку list2.

Стоимость всей операции составляет O(4*N), поскольку поиск в карте / словаре можно считать постоянным. С другой стороны, линейный / бинарный поиск каждого элемента в списках даст это O(N^2).

РЕДАКТИРОВАТЬ: после второй мысли, перемещая последнюю проверку во второй цикл, вы можете удалить один из циклов... но это ужасно...:)

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
Источник
Другие вопросы по тегам