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

Question

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

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

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

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

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

Answer 1

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

Если вы думаете о диаграмме Венна, со списком 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 контейнера, оно просто уничтожило два; -)

Answer 2

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

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

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

Answer 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

В конце removeElements будет содержать элементы, принадлежащие list1, но не list2, а AddedElements будет содержать элементы, принадлежащие 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)
}

Answer 4

Отсутствует информация: как вы определяете добавленные / удаленные? Например. если списки (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. В конце исключения оба списка могут быть пустыми, и в этом случае они будут равны. Если они не пустые, все элементы, все еще находящиеся в старом списке, являются элементами, отсутствующими в новом списке (в противном случае мы их удалили), следовательно, это удаленные элементы . Все элементы, все еще находящиеся в НОВОМ списке, - это элементы, которых не было в СТАРОМ списке (опять же, мы удалили их в противном случае), следовательно, это добавленные элементы .

Answer 5

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