Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование игр для компьютеров > C++

Ответ
 
Опции темы
Старый 06.02.2013, 00:29   #1
ІГРОГРАЙКО
ПроЭктировщик
 
Аватар для ІГРОГРАЙКО
 
Регистрация: 20.06.2009
Адрес: Україна
Сообщений: 152
Написано 10 полезных сообщений
(для 24 пользователей)
Как искать идентичные файлы?

У меня задание:
Написать программу которая бы искала идентичные файлы.
Входными данными являются пути к директориям.
Результатом работы должен быть список найденных идентичных файлов.

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

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

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

пока что все...
Заранее СПАСИБО за ответы!
__________________
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
jimon
 
Сообщений: n/a
Ответ: Как искать идентичные файлы?

можно стандартными средствами создать хеш-суммы файлов (например md5), потом найти все пары файлов чьи хеш-суммы совпадают и проверить уже эти пары на побайтовое совпадение
 
Ответить с цитированием
Старый 06.02.2013, 12:44   #3
ІГРОГРАЙКО
ПроЭктировщик
 
Аватар для ІГРОГРАЙКО
 
Регистрация: 20.06.2009
Адрес: Україна
Сообщений: 152
Написано 10 полезных сообщений
(для 24 пользователей)
Смех Ответ: Как искать идентичные файлы?

Сообщение от jimon Посмотреть сообщение
можно стандартными средствами создать хеш-суммы файлов (например md5), потом найти все пары файлов чьи хеш-суммы совпадают и проверить уже эти пары на побайтовое совпадение
Спасибо! но тут как раз очень важен 2-й вопрос.
Каким контейнером пользоваться, чтобы сравнение элементов между собой занимало поменьше времени?
БД с данными файлов я создам как класс внутри которого будет контейнер (массив) с данными файлов (путь к файлу, размер файла).
Конструктор класса будет принимать контейнер с путями директорий, искать в этих директориях файлы и заполнять их данными внутренний контейнер.
А сам поиск идентичных файлов будет организован как метод, который после вычислений будет возвращать контейнер с данными идентичных файлов.
Какой же тип контейнера выбрать?
  1. List<T>
  2. Dictionary<TKey,TValue>
  3. 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
jimon
 
Сообщений: n/a
Ответ: Как искать идентичные файлы?

ІГРОГРАЙКО
список наверно проще для тебя будет
 
Ответить с цитированием
Старый 06.02.2013, 13:08   #5
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 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
HolyDel
 
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений
(для 2,707 пользователей)
Ответ: Как искать идентичные файлы?

Dictionary<int,List<std::wstring>> candidates;
(Offline)
 
Ответить с цитированием
Старый 06.02.2013, 15:06   #8
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 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
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 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
HolyDel
 
Регистрация: 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)
Старый 06.02.2013, 20:49   #14
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 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)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 23:53.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com