Какой самый быстрый способ сравнить два списка предметов?

Question

У меня есть две папки с примерно 10000 файлов в каждой. Я хотел бы написать скрипт или программу, которая может сказать мне, синхронизируются ли эти папки, а затем сказать, какие файлы отсутствуют в каждой из них, чтобы сделать их синхронизированными.

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

Есть ли более быстрый алгоритм, чем этот?

Answer 1

diff -s [путь1] [путь2]

Answer 2

Если вы находитесь в C, используйте qsort() для сортировки списков файлов в порядке возрастания, а затем используйте вид "слияния:

Имейте два указателя, начинающиеся в начале каждого списка. Сделайте следующее:

• если имена совпадают, то это имя существует в обоих списках - продвигайте оба указателя
• если имя в списке list1 > name в списке list2, то оно есть только в списке 2 - указатель предварительного списка list2
• в противном случае имя в списке list1 находится только в списке list1 - указатель предварительного списка list1
• повторение

Когда вы находитесь в конце одного из списков, все элементы, оставшиеся в другом, явно отсутствуют в первом.

Кроме того, вы можете объединить оба списка, отслеживая, из какого списка поступает каждый элемент. Затем отсортируйте объединенный список. Сканирование отсортированного списка. Если вы видите два экземпляра одинакового значения, значит, это было в обоих списках. В противном случае вы будете знать, из какого он списка.

Answer 3

Кроме того, другой подход, который вы можете использовать,

Если нет ограничений по пространству, я бы пошел помещать файлы одной папки в хеш-код. Это займет O(N) времени и некоторое пространство..! затем я возьму каждый файл из второй папки и проверим, существует ли ключ в первом хеше.. это снова O(1) операция времени...! проблема решена в O(N) времени.. но это большая потребность в пространстве..

повторить то же самое в обратном порядке, если вы хотите скорость или пространство..!

Answer 4

Сгенерируйте контрольные суммы md5 или sha1 и сравните их. Что-то вроде этого

cd dir1; md5sum * | sort > /tmp/hash1
cd dir2; md5sum * | sort > /tmp/hash2
diff /tmp/hash1 /tmp/hash2  # could also use comm

Если вы беспокоитесь только об именах, а не о содержимом файлов, то diff dir1 dir2 работает отлично.

Answer 5

Если вам нужна эта информация только для их синхронизации, вы можете выполнить сравнение и копирование за один проход:

• Получить список каталогов из обоих каталогов
• сортировать оба списка лексикографически
• цикл одновременно через оба списка:
  • если один из списков пуст, остановите цикл
  • если оба элемента одинаковы: пошаговые оба индекса
  • иначе возьмите лексикографически нижний элемент, скопируйте его и добавьте только этот индекс
• скопировать все оставшиеся элементы непустого списка, если таковые существуют

Если вы хотите сделать это за два прохода или вам нужна информация, куда и куда копируется, замените "копировать" на "поместить имя и направление в список результатов".