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

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

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

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

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

Answer 5

Создайте контрольные суммы 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 работает нормально.