forum.boolean.name
Страница 1 из 2 1 2 >
Показывать 64 сообщений этой темы на одной странице

forum.boolean.name (http://forum.boolean.name/index.php)
-   C++ (http://forum.boolean.name/forumdisplay.php?f=22)
-   -   Как искать идентичные файлы? (http://forum.boolean.name/showthread.php?t=17841)

ІГРОГРАЙКО 06.02.2013 00:29
Как искать идентичные файлы?
 
У меня задание:
Написать программу которая бы искала идентичные файлы.
Входными данными являются пути к директориям.
Результатом работы должен быть список найденных идентичных файлов.

Поскольку я раньше все делал на C# то решил юзать "System" и "Windows Forms" короче CLR приложение. И GUI делать легко и типов удобных достаточно. Но когда вопрос дошел к реализации алгоритма поиска и сравнения файлов - тут я немного запутался...

Я расскажу как я придумал искать идентичные файлы, а потом задам вам вопросы.
Весь процесс поиска будет состоять из 2-х этапов:
  1. Создание базы с данными файлов.
  2. Сравнение всех записей между собой и подготовка результата.

Вопросы:
  1. Есть ли у вас предложение получше касательно выбора средств разработки с учетом того что это необходимо писать на С++?
  2. Какой тип контейнера мне лучше всего использовать для создания Базы Данных файлов? (Мне нужно хранить путь и размер)
  3. Есть ли смысл использовать Хеширование для сравнения больших файлов, если да, то какую Хеш-функцию выбрать?

пока что все...
Заранее СПАСИБО за ответы! ;)

jimon 06.02.2013 03:44
Ответ: Как искать идентичные файлы?
 
можно стандартными средствами создать хеш-суммы файлов (например md5), потом найти все пары файлов чьи хеш-суммы совпадают и проверить уже эти пары на побайтовое совпадение

ІГРОГРАЙКО 06.02.2013 12:44
Ответ: Как искать идентичные файлы?
 
Цитата:
Сообщение от jimon (Сообщение 251872)
можно стандартными средствами создать хеш-суммы файлов (например md5), потом найти все пары файлов чьи хеш-суммы совпадают и проверить уже эти пары на побайтовое совпадение
Спасибо! но тут как раз очень важен 2-й вопрос.
Каким контейнером пользоваться, чтобы сравнение элементов между собой занимало поменьше времени?
БД с данными файлов я создам как класс внутри которого будет контейнер (массив) с данными файлов (путь к файлу, размер файла).
Конструктор класса будет принимать контейнер с путями директорий, искать в этих директориях файлы и заполнять их данными внутренний контейнер.
А сам поиск идентичных файлов будет организован как метод, который после вычислений будет возвращать контейнер с данными идентичных файлов.
Какой же тип контейнера выбрать?
  1. List<T>
  2. Dictionary<TKey,TValue>
  3. HashSet<T>

jimon 06.02.2013 12:57
Ответ: Как искать идентичные файлы?
 
ІГРОГРАЙКО
список наверно проще для тебя будет

SBJoker 06.02.2013 13:08
Ответ: Как искать идентичные файлы?
 
Очевидно нужно в бинарном дереве хранить чексуммы

ІГРОГРАЙКО 06.02.2013 13:37
Ответ: Как искать идентичные файлы?
 
Цитата:
Сообщение от SBJoker (Сообщение 251899)
Очевидно нужно в бинарном дереве хранить чексуммы
Стоп...
Я чето не понял. :dontknow: Как хранить чексуммы в бинарном дереве, если 100% где то будут два одинаковых значения? И зачем? Ведь бинарное дерево нужно для сравнения "<" ">" а не для "=="?
Или это я ошибаюсь...

Объясни пожалуйста?

HolyDel 06.02.2013 14:14
Ответ: Как искать идентичные файлы?
 
Dictionary<int,List<std::wstring>> candidates;

SBJoker 06.02.2013 15:06
Ответ: Как искать идентичные файлы?
 
Цитата:
Сообщение от ІГРОГРАЙКО (Сообщение 251900)
Стоп...
Я чето не понял. :dontknow: Как хранить чексуммы в бинарном дереве, если 100% где то будут два одинаковых значения? И зачем? Ведь бинарное дерево нужно для сравнения "<" ">" а не для "=="?
Или это я ошибаюсь...

Объясни пожалуйста?
А ты собираешься список весь перебирать для каждого файла?
Две чексуммы 100% совпадут? а разве не это нам нужно? Совпали значит нашли.

ІГРОГРАЙКО 06.02.2013 17:25
Ответ: Как искать идентичные файлы?
 
Цитата:
Сообщение от SBJoker (Сообщение 251912)
А ты собираешься список весь перебирать для каждого файла?
Две чексуммы 100% совпадут? а разве не это нам нужно? Совпали значит нашли.
Зачем перебирать весь список?
в Dictionary<TKey,TValue> есть такая штука:
Цитата:
MSDN
ContainsKey - Определяет, содержится ли указанный ключ в словаре Dictionary(TKey, TValue).
ContainsValue - Определяет, содержится ли указанное значение в списке Dictionary(TKey, TValue).
Я думаю создать Базу для поиска:
Dictionary<String,long int> DB; где:
String - єто пути к файлам (они не повторяются)
long int - размеры фалов которые могут совпадать...

Вот только если найдутся 2 записи с одинаковыми размерами, тогда уже буду драть MD5 с этих файлов. Это если они больше примерно 10-100МБ, все что меньше - побитовая проверка. Если у больших файлов MD5 совпало тогда и их на побитовою проверку...

Что скажете?
Может у вас есть идеи получше?

ІГРОГРАЙКО 06.02.2013 17:29
Ответ: Как искать идентичные файлы?
 
Цитата:
Сообщение от HolyDel (Сообщение 251906)
Dictionary<int,List<std::wstring>> candidates;
:dontknow:
Объясни пожалуйста что где должно хранится?

SBJoker 06.02.2013 17:35
Ответ: Как искать идентичные файлы?
 
Цитата:
Сообщение от ІГРОГРАЙКО (Сообщение 251925)
Зачем перебирать весь список?
в Dictionary<TKey,TValue> есть такая штука:
а Dictionary по-твоему это что? Это и есть бинарное дерево!

ІГРОГРАЙКО 06.02.2013 17:44
Ответ: Как искать идентичные файлы?
 
Цитата:
Сообщение от SBJoker (Сообщение 251928)
а Dictionary по-твоему это что? Это и есть бинарное дерево!
Ну если так то я теперь тебя понял :ok:

HolyDel 06.02.2013 18:40
Ответ: Как искать идентичные файлы?
 
Цитата:
Объясни пожалуйста что где должно хранится?
в инте (ключе, тип может быть другим) - хэш файлов.

в списке строк - пути к файлам с одинаковым хэшем

алгоритм:
1) проходишься по всем файлам в выбранной папке рекурсивно.
2) добавляешь путь к списку файлов с таким хэшем:
candidates[GetFileHash(filename)].push_back(filename);
3) после составления мапы проходишься по файлам в списке:
Код:
for(auto ci = candidates.begin(), ei = candidates.end();ci!=ei;++ci)
{
auto files = ci->second;
if(files.size() > 1)
{
for(auto fi = files.begin(), efi = files.end();fi!=efi;++fi)
...побитовое сравнение
}
}
}
4) если побитово сравнились - запихиваешь в какой-то свой список одинаковых файлов.

SBJoker 06.02.2013 20:49
Ответ: Как искать идентичные файлы?
 
Ещё можно посоветовать не сравнивать файлы нулевого размера, у них чек сумма = 0, да и смысла их сравнивать нет, разве что по имени.

ІГРОГРАЙКО 21.02.2013 02:35
Ответ: Как искать идентичные файлы?
 
Вложений: 1
Добрый вечер!

Я вот уже сделал задание:
Вложение 18825

Но мне дали дополнительное:

Надо сделать так, чтобы GUI во время процессинга (поиска идентичных файлов) не зависало, а отвечало на разные действия юзверя.
Я понял, что тут надо запустить процессинг в отдельном потоке, но у меня не получается запустить функцию внутри которой и вызов метода, что ищет идентичные файлы И изменение параметров контрола progressBar так, чтобы это все было в отдельном потоке...

Помогите пожалуйста!
Кто знает как пользоваться System::Threading!!!


Часовой пояс GMT +4, время: 21:16.
Страница 1 из 2 1 2 >
Показывать 64 сообщений этой темы на одной странице

vBulletin® Version 3.6.5.
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Перевод: zCarot