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

Question

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

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

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

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

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

Answer 1

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

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

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

Итак, Перебрать ищем для каждого элемента в B. Если вы ее нашли, удалить его из А и В

Тогда А список вещей, которые были удалены, и B представляет собой список вещей которые были добавлены

Я думаю ...

[править] Хорошо, с новым ограничением «только 2 контейнера», то же самое по-прежнему имеет место

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

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

Я бы поспорил мое первое решение не использовать 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

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

Answer 4

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

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

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

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

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

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

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

Answer 5

Являются ли перечисленные объекты в списке уникальными? В этом случае я бы сначала построил две карты (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) 
} 

Извините за ужасный метаязыка смесительной Руби и Java :-P

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

Стоимость всей операции - 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) 
}