нужна функция поиска дубликатов файлов

[marat_]

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

[Алексей++]

я не занимался, но можно сделать сравнение по контрольной сумме и размеру файла. Вести мини-базу данных в озу )

[Вад]

По-моему, наиболее очевидно начинать проверку со сверки размеров файла. Если у тебя дубликатов будет не слишком много, то едва ли слишком часто будет совпадать размер. Для тех, которые совпадают, думаю, проверку можно начинать поблочно - опять же, едва ли кроме случая умышленно незначительно модифицированной версии того же файла, что-то другое будет совпадать настолько точно, что придётся дочитать до конца файла

[McZim]

смысл создания темы мне не понятен? Нужна функция поиска дубликатов файлов, причем как утверждает автор, он знает как ее сделать, но чего то боится, мне лично не понятно чего.

[marat_]

объясню. файлов ~5-6 милионов, могут присутствовать различные форматы, но в основном -  изображения bmp большой размерности (размер файла у них одинаков). функция мне нужна, но интересует опыт тех, кто сталкивался с подобными вещами. если хранить в озу - свопить будет, скорость упадёт, если скидывать в файл - аналогично. вот и хочется сначала узнать об ошибках, чтобы потом на них не споткнуться.

[Алексей++]

озу ты не забьёшь имхо )

[marat_]

в смысле?
при самых скромных подсчётах размер данных составит более гигабайта

[Вад]

marat_, изложи подсчёт что именно считаешь?

[marat_]

считаем md5 - 128 бит
+ путь - 260 байт
умножаем на 5 млн
получаем

[McZim]

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

[Вад]

Для твоего решения, как минимум, оптимизация: хранить не весь путь к каждому файлу, а древовидную структуру для вложенных директорий. в каждом узле дерева - имя директории, перечень файлов с их md5 и вложенные блоки субдиректорий с той же структурой. Тогда для всех файлов в подкаталоге путь будет один раз записан.

[marat_]

в принципе, я так и думал...
но хранить всё таки мыслю в озу, файл больше гига не очень пригоден для чтения\записи

[McZim]

marat_, а до какого момента вы хотите это дело хранить в оперативной памяти?

[marat_]

кстати, уточнение, хеш будет sha256. хранить думал до окончания подсчёта всех файлов, потом потихоньку подчищать по мере прохождения и анализа.McZim, если вам не трудно, обращайтесь ко мне на "ты". я и "вы" - несовместимы.

[McZim]

marat_, может лучше будет использовать для этого дела именованные каналы? Да кстате ОС какая?

[marat_]

интересный вопрос... даже не соображу...

ps винда, родимая

[Алексей++]

marat_ , а пути можно хранить в виде дерева, много префиксов будет одинаковых.

Вад опередил )

[McZim]

marat_, к сожалению не знаю как эти каналы устроены в Windows, но знаю как в Linux скажите у вас ОС какая, для котороы вы будете писать данное приложение.

[Алексей++]

McZim, а при чём каналы ? Я тоже в груз

[marat_]

ну вот! а вы говорите! сколько уже полезных советов!
McZim, предполагается xp2sp. ещё раз прошу, не надо "вы", раздражает, ей-богу!

[McZim]

Алексей1153++, я так понимаю marat_, в дальнейшем будет хранить полученный результат найденных файлов или их количество где то для дальнейшей обработки, так вот я думаю что бы не пихать сначала во временный буфер в памяти и беспокоится о занимаемом месте, а потом выбирать это дело куда то, думаю проще будет помещать результат в канал а уже из канала ложить в долговременное хранилище, при этом канал распологается в ФС и не нужно беспокоится о ОЗУ.

[marat_]

даа, хитрость города берёт!
сначала, всё таки, анализ размеров и расширений будет совсем не лишним... а потом уже среди одинаковых размеров считать хеши

[Вад]

Если у тебя гарантированно за время проверки никто не добавит без твоего ведома новый файл или каталог, то можешь хранить не имена файлов и каталогов, а порядковые номера в алфавитном порядке, например. Места сэкономишь уйму

[marat_]

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

[Антон (LogRus)]

marat_, решение большенства задач упрошается, если правильно выбрать и организовать данные.
какие данные нам нужны?
1. Пути к файлам пускай строки длиннной до 256 символов
2. размер файла long - 4 байта
3. иногда контрольная сумма еще 32 байта
имеем до ~300 байт на файл
6E6 файлов итого 2 гига.

решение 1.
использовать БД(BerkeleyDB подойдёт)
решение 2.
снизить потребности например засчет, уменьшения расходов на хранение пути к файлу(хранить в виде дерева, аналогичного дереву каталогов), экономим 220 байт на файл, т.е где, то 500-600 мег на 6E6 файлов

вариант с БД мне нравится больше, конечно страдает скорость, но резко снижаются требования к памяти.
можно наверняка еще, что нибуть придумать

собственно вы это уже по обсуждали, пока я сообщение писал

[McZim]

LogRus, можно так же использовать SQLite БД очень шустрая

[Антон (LogRus)]

McZim, с чем работал про то и говорю

[marat_]

не, бд юзать нельзя. программа должна быть самодостаточной. а вот ещё средство экономии: использоватть досовские пути к файлам. в основе решение уже сформировалось, надо переспать, а там мозг и детали придумает. всем бАльшое спасибо!!!

[RXL]

Пути можно выделить в отдельную таблицу, а в основную числовой идентификатор вставлять. Так и компактнее, и с деревьями не надо возиться.

Размер файла может быть больше 4ГБ.

[Антон (LogRus)]

marat_, BerkeleyDB позволяет или тащить с прогой только одну dll или статически слинковать её с твой прогой(500 кило весит всеголишь).
я бы постороил, дерево путей, проставляя уникальные номера файлам, контрольную сумму или размер файла использовал бы в качестве ключа к БД, далее прошелся бы курсором по всей BerkeleyDB, файлы с одинаковой длинной или контрольной суммой будут идти подряд(это гарантирует БД), если нашел дубликаты, делал бы доп.проверки на совпадение и по номерам файлов находил бы их имена, кстати контрольную сумму можно считать не по всему файлу.

ну это как бы сделал я, но  коллективный разум наверняка найдёт более изящьные решения.