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

StackOverflow https://stackoverflow.com/questions/127151

Вопрос

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

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

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

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

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

Это было полезно?

Решение

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

Если вы думаете о диаграмме Венна, где список 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.Все, что было найдено на СТАРОМ, но не на НОВОМ, было удалено.Добавлено все, что есть на НОВОМ, но не на СТАРОМ (например.содержимое одного и того же каталога на одном сервере, однако списки были созданы в разное время).

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

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

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

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

  3. В конце исключения оба списка могут оказаться пустыми, и в этом случае они будут равны.Если они не пусты, все элементы, находящиеся в СТАРОМ списке, являются элементами, отсутствующими в НОВОМ списке (в противном случае мы их удалили), следовательно, это элементы удаленные элементы.Все элементы, находящиеся в НОВОМ списке, — это элементы, которых не было в СТАРОМ списке (опять же, в противном случае мы их удалили), поэтому это добавлены элементы.

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

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

В конце концов удаленоЭлементы будет содержать элементы, принадлежащие списку1, но не списку2, и добавленныеЭлементы будет содержать элементы, принадлежащие 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)
}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top