|
06.02.2013, 00:29
|
#1
|
ПроЭктировщик
Регистрация: 20.06.2009
Адрес: Україна
Сообщений: 152
Написано 10 полезных сообщений (для 24 пользователей)
|
Как искать идентичные файлы?
У меня задание:
Написать программу которая бы искала идентичные файлы.
Входными данными являются пути к директориям.
Результатом работы должен быть список найденных идентичных файлов.
Поскольку я раньше все делал на C# то решил юзать "System" и "Windows Forms" короче CLR приложение. И GUI делать легко и типов удобных достаточно. Но когда вопрос дошел к реализации алгоритма поиска и сравнения файлов - тут я немного запутался...
Я расскажу как я придумал искать идентичные файлы, а потом задам вам вопросы.
Весь процесс поиска будет состоять из 2-х этапов: - Создание базы с данными файлов.
- Сравнение всех записей между собой и подготовка результата.
Вопросы: - Есть ли у вас предложение получше касательно выбора средств разработки с учетом того что это необходимо писать на С++?
- Какой тип контейнера мне лучше всего использовать для создания Базы Данных файлов? (Мне нужно хранить путь и размер)
- Есть ли смысл использовать Хеширование для сравнения больших файлов, если да, то какую Хеш-функцию выбрать?
пока что все...
Заранее СПАСИБО за ответы!
__________________
Blitz3D, XNA, WebGL, OpenGL, Unity3D
PC: ASUS A55VM Core i3 (2.4Ghz), 6 Gb RAM, Nvidia GF 630M GT 2Gb
|
(Offline)
|
|
06.02.2013, 03:44
|
#2
|
|
Ответ: Как искать идентичные файлы?
можно стандартными средствами создать хеш-суммы файлов (например md5), потом найти все пары файлов чьи хеш-суммы совпадают и проверить уже эти пары на побайтовое совпадение
|
|
|
06.02.2013, 12:44
|
#3
|
ПроЭктировщик
Регистрация: 20.06.2009
Адрес: Україна
Сообщений: 152
Написано 10 полезных сообщений (для 24 пользователей)
|
Ответ: Как искать идентичные файлы?
Сообщение от jimon
можно стандартными средствами создать хеш-суммы файлов (например md5), потом найти все пары файлов чьи хеш-суммы совпадают и проверить уже эти пары на побайтовое совпадение
|
Спасибо! но тут как раз очень важен 2-й вопрос.
Каким контейнером пользоваться, чтобы сравнение элементов между собой занимало поменьше времени?
БД с данными файлов я создам как класс внутри которого будет контейнер (массив) с данными файлов (путь к файлу, размер файла).
Конструктор класса будет принимать контейнер с путями директорий, искать в этих директориях файлы и заполнять их данными внутренний контейнер.
А сам поиск идентичных файлов будет организован как метод, который после вычислений будет возвращать контейнер с данными идентичных файлов.
Какой же тип контейнера выбрать? - List<T>
- Dictionary<TKey,TValue>
- HashSet<T>
__________________
Blitz3D, XNA, WebGL, OpenGL, Unity3D
PC: ASUS A55VM Core i3 (2.4Ghz), 6 Gb RAM, Nvidia GF 630M GT 2Gb
|
(Offline)
|
|
06.02.2013, 12:57
|
#4
|
|
Ответ: Как искать идентичные файлы?
ІГРОГРАЙКО
список наверно проще для тебя будет
|
|
|
06.02.2013, 13:08
|
#5
|
Злобный Админ
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений (для 9,330 пользователей)
|
Ответ: Как искать идентичные файлы?
Очевидно нужно в бинарном дереве хранить чексуммы
__________________
|
(Offline)
|
|
06.02.2013, 13:37
|
#6
|
ПроЭктировщик
Регистрация: 20.06.2009
Адрес: Україна
Сообщений: 152
Написано 10 полезных сообщений (для 24 пользователей)
|
Ответ: Как искать идентичные файлы?
Сообщение от SBJoker
Очевидно нужно в бинарном дереве хранить чексуммы
|
Стоп...
Я чето не понял. Как хранить чексуммы в бинарном дереве, если 100% где то будут два одинаковых значения? И зачем? Ведь бинарное дерево нужно для сравнения "<" ">" а не для "=="?
Или это я ошибаюсь...
Объясни пожалуйста?
__________________
Blitz3D, XNA, WebGL, OpenGL, Unity3D
PC: ASUS A55VM Core i3 (2.4Ghz), 6 Gb RAM, Nvidia GF 630M GT 2Gb
|
(Offline)
|
|
06.02.2013, 14:14
|
#7
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Ответ: Как искать идентичные файлы?
Dictionary<int,List<std::wstring>> candidates;
|
(Offline)
|
|
06.02.2013, 15:06
|
#8
|
Злобный Админ
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений (для 9,330 пользователей)
|
Ответ: Как искать идентичные файлы?
Сообщение от ІГРОГРАЙКО
Стоп...
Я чето не понял. Как хранить чексуммы в бинарном дереве, если 100% где то будут два одинаковых значения? И зачем? Ведь бинарное дерево нужно для сравнения "<" ">" а не для "=="?
Или это я ошибаюсь...
Объясни пожалуйста?
|
А ты собираешься список весь перебирать для каждого файла?
Две чексуммы 100% совпадут? а разве не это нам нужно? Совпали значит нашли.
__________________
|
(Offline)
|
|
06.02.2013, 17:25
|
#9
|
ПроЭктировщик
Регистрация: 20.06.2009
Адрес: Україна
Сообщений: 152
Написано 10 полезных сообщений (для 24 пользователей)
|
Ответ: Как искать идентичные файлы?
Сообщение от SBJoker
А ты собираешься список весь перебирать для каждого файла?
Две чексуммы 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 совпало тогда и их на побитовою проверку...
Что скажете?
Может у вас есть идеи получше?
__________________
Blitz3D, XNA, WebGL, OpenGL, Unity3D
PC: ASUS A55VM Core i3 (2.4Ghz), 6 Gb RAM, Nvidia GF 630M GT 2Gb
|
(Offline)
|
|
06.02.2013, 17:29
|
#10
|
ПроЭктировщик
Регистрация: 20.06.2009
Адрес: Україна
Сообщений: 152
Написано 10 полезных сообщений (для 24 пользователей)
|
Ответ: Как искать идентичные файлы?
Сообщение от HolyDel
Dictionary<int,List<std::wstring>> candidates;
|
Объясни пожалуйста что где должно хранится?
__________________
Blitz3D, XNA, WebGL, OpenGL, Unity3D
PC: ASUS A55VM Core i3 (2.4Ghz), 6 Gb RAM, Nvidia GF 630M GT 2Gb
|
(Offline)
|
|
06.02.2013, 17:35
|
#11
|
Злобный Админ
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений (для 9,330 пользователей)
|
Ответ: Как искать идентичные файлы?
Сообщение от ІГРОГРАЙКО
Зачем перебирать весь список?
в Dictionary<TKey,TValue> есть такая штука:
|
а Dictionary по-твоему это что? Это и есть бинарное дерево!
__________________
|
(Offline)
|
|
06.02.2013, 17:44
|
#12
|
ПроЭктировщик
Регистрация: 20.06.2009
Адрес: Україна
Сообщений: 152
Написано 10 полезных сообщений (для 24 пользователей)
|
Ответ: Как искать идентичные файлы?
Сообщение от SBJoker
а Dictionary по-твоему это что? Это и есть бинарное дерево!
|
Ну если так то я теперь тебя понял
__________________
Blitz3D, XNA, WebGL, OpenGL, Unity3D
PC: ASUS A55VM Core i3 (2.4Ghz), 6 Gb RAM, Nvidia GF 630M GT 2Gb
|
(Offline)
|
|
06.02.2013, 18:40
|
#13
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Ответ: Как искать идентичные файлы?
Объясни пожалуйста что где должно хранится?
|
в инте (ключе, тип может быть другим) - хэш файлов.
в списке строк - пути к файлам с одинаковым хэшем
алгоритм:
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) если побитово сравнились - запихиваешь в какой-то свой список одинаковых файлов.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
06.02.2013, 20:49
|
#14
|
Злобный Админ
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений (для 9,330 пользователей)
|
Ответ: Как искать идентичные файлы?
Ещё можно посоветовать не сравнивать файлы нулевого размера, у них чек сумма = 0, да и смысла их сравнивать нет, разве что по имени.
__________________
|
(Offline)
|
|
21.02.2013, 02:35
|
#15
|
ПроЭктировщик
Регистрация: 20.06.2009
Адрес: Україна
Сообщений: 152
Написано 10 полезных сообщений (для 24 пользователей)
|
Ответ: Как искать идентичные файлы?
Добрый вечер!
Я вот уже сделал задание:
FindDublicatedFiles.rar
Но мне дали дополнительное:
Надо сделать так, чтобы GUI во время процессинга (поиска идентичных файлов) не зависало, а отвечало на разные действия юзверя.
Я понял, что тут надо запустить процессинг в отдельном потоке, но у меня не получается запустить функцию внутри которой и вызов метода, что ищет идентичные файлы И изменение параметров контрола progressBar так, чтобы это все было в отдельном потоке...
Помогите пожалуйста!
Кто знает как пользоваться System::Threading!!!
__________________
Blitz3D, XNA, WebGL, OpenGL, Unity3D
PC: ASUS A55VM Core i3 (2.4Ghz), 6 Gb RAM, Nvidia GF 630M GT 2Gb
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 16:28.
|