>>06837
А я это писал до того, как программу посмотрел, удивившись, что 500 МБ внезапно разбухли в десять раз. А сейчас, попрактиковавшись, ничего странного не вижу — это просто Python, если в нём не думать над каждым действием. Даже беззаботное создание списка индексов через list(range(num_hashes)) прибавляет к используемым 500 МБ ещё примерно столько же, потому что это всё ссылки на объекты со своими объектами внутри, а не голые байтики. Что уж говорить о всяких сложно устроенных внутри структурах. Или вот встроенный sort() генерирует для каждого элемента объект-ключ для операций сравнения. Когда элементы — сложные объекты, иметь более мелкий выгодно, но вот когда это циферки, которые могут занимать меньше памяти, чем указатели на них, а уж тем более объекты, их оборачивающие, временные данные начинают занимать в два-три раза больше места. Что файлу делать mmap, когда скопированные оттуда и преобразованные данные занимают во много раз больше? Вообще, обычный read() в бинарном режиме под капотом тоже использует системный кэш и выполняется почти мгновенно после первого запуска (на моей системе), так что ничего особенного тут городить и не надо было.

Центральный вопрос: зачем использовать всякие hashtable, если у нас есть таблица хэшей, вот прямо буквально? Зачем каждый хэш хэшировать ещё раз, хранить и то, и другое, ссылки туда-сюда лепить?

Для начала отсортируем хэши, чтобы можно было пользоваться бинарным поиском прямо по готовому массиву. Удобно это было бы сделать прямо при экспорте из базы данных, но можно развлечься и написать скриптик (так, как будто это C):
https://paste.debian.net/1302875/

Памяти требует 600 с чем-то мегабайт, плюс-минус интерпретатор. Индексы используются вместо перемещения самих данных потому, что я не накопал, как неизменяемые bytes из файла без копирования переделать в bytearray (иначе на какое-то мгновение процессу требуется 500+500 МБ памяти, что на практике, конечно, фигня, но мне интересно минимумом накладных расходов обойтись). Из-за всей иерархии косвенной адресации при интерпретации, думаю, разницы не будет ни в скорости, ни в объёмах работы с памятью. Да, я посмотрел, что нормальные люди используют нормальные массивы в numpy, и что всё это можно красиво обернуть в классы с операциями доступа и сравнения, это понятно. Запись маленькими кусочками тоже не слишком удобна для дисков и файловых систем, но это уже мелочи.

Занимает такая наивная сортировка 484 МБ 16-байтовых хэшей почти полтора часа. Мда. Если сравнить время работы на разных объёмах, то зависимость мало чем отличается от линейной:
https://www.wolframalpha.com/input?i=quadratic+fit+%7B%7B1%2C+6.8%7D%2C+%7B8%2C+67%7D%2C+%7B32%2C+290%7D%2C+%7B64%2C+618%7D%2C+%7B100%2C+1058%7D%2C+%7B484%2C+5663%7D%7D
Значит, не в алгоритме дело. Скрипт запускался с -m cProfile, и допустим, 15% производительности это съело, что тоже не слишком важно.

Можно ли сделать лучше на коленке? Допустим, мы перевели хэши в текстовый формат:
xxd -ps -c 16 hashes.bin hashes.txt
Затем достали замшелую досовскую (на самом деле не досовскую) утилиту SORT:
sort /L "C" hashes.txt /O sorted.txt
Она справилась с сортировкой гигабайтного файла за три с половиной минуты — правда, не имея ограничений по дополнительным памяти и месту на диске. Ну да, технологии семидесятых и восьмидесятых годов, ещё на медленных плёночных архивах отлаженные.

Логично предположить, что и дальше можно готовыми инструментами обойтись. Типичным find … | xargs … md5sum получить список файлов-кандидатов с их хэшами, потом грепнуть одно по другому (вроде даже какие-то оптимизированные grep для отсортированных данных можно накопать), а совпадения скопировать в целевой каталог. Базу можно сжать и на лету распаковывать при чтении, она вернётся к своему исходному размеру (и даже немного меньше станет после сортировки, расположившей совпадающие начальные байты рядом). Скрипт получится не в одну строку, а в несколько, и для обычных людей, у которых не миллионы картинок, сгодится, думаю, без хитрых доработок. Проблема, конечно, в некроссплатформенности, и в том, что для нормальной работы с юникодными путями в Windows придётся делать что-то либо под Powershell, либо под оболочку под Windows Terminal и новую консоль, либо под WSL.

Возвращаемся к пистону и возвращаем данные в бинарный формат (да, мы всё ещё развлекаемся, экономя память):
xxd -r -c 16 -ps sorted.txt sorted.bin
Проверяем хэш файла с хэшами (yo dawg). Он совпадает с полученным в первом варианте, ура (CD716333B72909B4D2D9D78B62E30CB5). Вот сама отсортированная база, она ещё понадобится:
https://www.mediafire.com/file/epum672yxto5d2z/sorted.bin/file

Никто не мешает теперь написать другой скрипт, перебирающий файлы так, как описано выше, но не требующий непонятных гигабайтов памяти. Потом к нему можно приделывать и GUI, и всё на свете. Вжух, и он готов:
https://paste.debian.net/1302902/

Кладёте sorted.bin и скрипт рядом, он начинает искать (по умолчанию в текущем каталоге и ниже, но можно другой задать). Если указать место для копирования, копирует найденное туда, иначе просто выводит пути. Можно включить подсчёт. В памяти занимает не больше объёма базы хэшей, плюс хэшируемый в данный момент файл, ограниченный 100 МБ, плюс мелочь на остальную программу, пиковое потребление процесса в процесе тестирования — 605 МБ.

Только у меня есть сомнения, что расширения файлам нужны, хэш-то от них не зависит, а переименовываться по ошибке или специально они могли как угодно. Надеюсь, на сервере это обрабатывается. И ещё надеюсь, что люди будут смотреть, что собралось, перед заливкой на хостинги, потому что некоторые старенькие файлы с большой вероятностью находятся в используемых крупными фирмами проверочных базах. Кажется, многим понадобится чёрный список каталогов. Ещё можно перебор поменять, чтобы заглатывать файлы пачками (например, по целой папке), но не раздувая до списка всех существующих (у некоторых, думаю, они просто слишком большими выйдут), возможно, дискам от этого будет легче. Ну и хэшировать тогда можно в несколько потоков.

прошу к столу!