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

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

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

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

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

Тогда А — это список вещей, которые были удалены, а Б — это список вещей, которые были добавлены.

Я думаю...

[править] Хорошо, с новым ограничением «только 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

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

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

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

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

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

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

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

В итоге removedElements будет содержать элементы, принадлежащие list1, но не list2, а addedElements будет содержать элементы, принадлежащие list2.

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

EDIT: если подумать, переместив последнюю проверку во второй цикл, вы можете удалить один из циклов... но это некрасиво... :)

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