Форум программистов CodeGuru
15 Август 2018, 07:55:44 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.

Войти
Новости:
 
   Начало   Помощь Войти Регистрация  
Страниц: [1]   Вниз
  Печать  
Автор Тема: Скорость выполнения  (Прочитано 19146 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Valery
Пользователь
***
Офлайн Офлайн

Сообщений: 83


Просмотр профиля
« : 11 Август 2010, 12:51:12 »

Мне необходимо просканировать какую-нибудь директорию
и записать в структуру значения из файлов
делаю так
поиск файлов

Код:
int CdublicatorDlg::SkanDirecotory(CString nameDirecory)
{
WIN32_FIND_DATA FindData;
CString nameFindFile;
CString nameFile;
nameFindFile.Format(_T("%s\\*.*"),nameDirecory);

HANDLE hand=FindFirstFile(nameFindFile,&FindData);
if(hand!=(HANDLE)-1)
{
do
{
nameFile.Format(_T("%s"),FindData.cFileName);
if(nameFile!=_T(".")&& nameFile!=_T(".."))
{
if(FindData.dwFileAttributes&FILE_ATTRIBUTE_DIRECTORY)
  {
  nameFile.Format(_T("%s\\%s"),nameDirecory,FindData.cFileName);

                       SkanDirecotory(nameFile);

}
else
{
ReadingValueFile(nameFile,nameDirecory);
}
}
}while(FindNextFile(hand,&FindData));

}
return 0;
}
обычная рекурсия
как убыстрить???

заполнение структуры значениями из файла
Код:
int CdublicatorDlg::ReadingValueFile(CString nameFile, CString nameDirectory)
{
    CDubicFile * dF=new CDubicFile;// это служебная структура
    CFile file;
    CString namFile;
namFile.Format(_T("%s\\%s"),nameDirectory,nameFile);
if(file.Open(namFile,CFile::modeRead))
{
     dF->nameDirectory=nameDirectory; //имя директории где находится файл
     dF->name=nameFile;                    // имя файла
dF->size=file.GetLength();
byte  * buf=new byte[dF->size]; // буфер для чтения вопрос ниже
file.Read(&(dF->firstValue),sizeof(int));// в структуру значение первых 4 байт
     file.Read(buf,dF->size);

          for(int i=0;i<dF->size;i++)
dF->IDVal+=buf[i]; // сумма байтов файла
   
            delete [] buf;
}
return 0;
}
вот здесь самое интересное
 
если читать побайтово то помереть можно,

если выделять блок то читает быстро но
1 размер файла никто не ограничивает может получится что памяти не хватит(каков оптимальный размер буфера???)
2 файлов много выделяя /удаляя память получим фрагментацию

можно один раз выделить блок и работать с ним но какой оптимально по размеру??

кто что думает??
С уважением Валерий.
PS если интересно решил написать прилуду для поиска дубликатов файлов.
PSS как можно рассчитать время сканирования типа в винде осталось стоко-то секунд
Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #1 : 20 Август 2010, 00:24:41 »

Мне необходимо просканировать какую-нибудь директорию
и записать в структуру значения из файлов
делаю так
поиск файлов
...
обычная рекурсия
как убыстрить???

Можно попробовать через интерфейс IShellFolder. Но, имхо, в общем быстродействие особо сильно не увеличится, т.к. необходимо чтение из файлов.


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

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

если выделять блок то читает быстро но
1 размер файла никто не ограничивает может получится что памяти не хватит(каков оптимальный размер буфера???)
2 файлов много выделяя /удаляя память получим фрагментацию

можно один раз выделить блок и работать с ним но какой оптимально по размеру??

Тут, думаю, нужно соотнести скорость чтения с быстрых устройств хранения данных (винчестеров), примерную скорость обработки информации, примерный "незначительный" объем оперативной памяти для сегодняшних компов . Имхо, 1-10 мб вполне нормально. Не думаю, что кто-то особо заморачивается над алгоритмами вычисления оптимального объема такого буфера. Ну, в крайнем случае можно получать информацию о памяти при помощи Memory Management Functions или чего-то подобного и выделять себе диапазон страниц из nonpaged pool для гарантированной быстрой работы с ними.

PS если интересно решил написать прилуду для поиска дубликатов файлов.

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

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

Кстати, в качестве "первичных хешей" можно брать длину файлов (если длина файлов не совпадает, то они точно не равны).

PSS как можно рассчитать время сканирования типа в винде осталось стоко-то секунд

Ну, я до этого момента нигде не видел особо точного подсчета времени до завершения операции.
Обычно основываются на известных величинах, или зависимостях от них, которые линейны.
Записан

Valery
Пользователь
***
Офлайн Офлайн

Сообщений: 83


Просмотр профиля
« Ответ #2 : 29 Август 2010, 09:43:21 »

Цитировать
Имхо, дубликаты файлов искать достаточно дорого по времени.
Согласен...
но прилуда необходима, по крайней мере для меня.
ибо 400гБ архива вручную не посмотришь.
Цитировать
И ищутся они на основе построения хешей для всего файла и его кусков.
для чего нужно прочитать файл
идея такая
точнее две разных
1 создаем файл БД
2 сканируя диски записываем в БД путь и размер файла
3 сортируем записи по размеру
4 если совпадает размер создаем еще один файл
5 в него записываем хеш, контрольную сумму, и первые байты файла
6 если все это совпадает то побайтовое сравнение
недостаток к одному файлу несколько обращений?
вторая
1 создаем файл БД
2 сканируя диски записываем в БД путь и размер файла, хеш, контрольную сумму, и первые байты файла
3 если все это совпадает то побайтовое сравнение
недостаток
каждый файл придется читать
которая из них быстрее не знаю
С уважением Валерий
Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #3 : 30 Август 2010, 01:11:55 »

ибо 400гБ архива вручную не посмотришь.

400гб, в принципе, "реальная" цифра. Те же хеши на быстрой машине за сутки построятся (наверно) Улыбка

Цитировать
И ищутся они на основе построения хешей для всего файла и его кусков.
для чего нужно прочитать файл

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

идея такая
точнее две разных
1 создаем файл БД
2 сканируя диски записываем в БД путь и размер файла
3 сортируем записи по размеру
4 если совпадает размер создаем еще один файл
5 в него записываем хеш, контрольную сумму, и первые байты файла
6 если все это совпадает то побайтовое сравнение
недостаток к одному файлу несколько обращений?
вторая
1 создаем файл БД
2 сканируя диски записываем в БД путь и размер файла, хеш, контрольную сумму, и первые байты файла
3 если все это совпадает то побайтовое сравнение
недостаток
каждый файл придется читать
которая из них быстрее не знаю

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

Первые байты файлов сохранять смысла не имеет. По-крайней мере, по двум причинам:
1. Они могут совпадать у очень многих файлов. У файлов каких-либо форматов могут быть стандартные структуры вначале, в большинстве случаев заполненные одинаковыми данными. Как минимум, у очень многих форматов вначале идут сигнатуры (например, WAV, AVI, MIDI форматы используют формат файлов-контейнеров RIFF, и у них у всех вначале первые 4 байта - "RIFF").
2. Если различаются хеши файлов (т.е. всех данных файла), то и данные различаются. Т.е. если есть хеш всего файла, то сохранять какие-либо данные из него для проверки не имеет смысла (хеша достаточно).

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

Все сканируем, и сохраняем (в БД или еще где) информацию о путях к файлам и их размерах.
Сортируем полученный список по размеру файла (размер файла в данном случае - критерий).
И получаем список вида:
размер1 -> путь_к_файлу_1
размер1 -> путь_к_файлу_2
размер1 -> путь_к_файлу_3
размер2 -> путь_к_файлу_4
размер2 -> путь_к_файлу_5
размер3 -> путь_к_файлу_6
...

Т.е. мы можем уже выделить группы файлов по одинаковому размеру. И в этих группах могут быть дубликаты.

Группы, кстати, надо как-то маркировать (какие-то ID им назначать уникальные).

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

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

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

Сорри, если непонятно изложил, поздно уже Улыбка
Записан

Valery
Пользователь
***
Офлайн Офлайн

Сообщений: 83


Просмотр профиля
« Ответ #4 : 30 Август 2010, 04:09:44 »

первые байты как раз и нужны чтобы понять принадлежность файла к какой либо группе.
например какой-то file.tmp имеет сигнатуру "MZ" значит исполняемый файл и нечего его сравнивать с каким-то документом.
я хочу создать несколько файлов БД с разными значениями первых байт,по моему сортировка быстрей пройдет, чем в одном большом файле.

Цитировать
размер1 -> путь_к_файлу_1
Группы, кстати, надо как-то маркировать (какие-то ID им назначать уникальные).

так размер и будет этим уникальным ID
а если у файла то полный путь тоже достаточно уникален
какой хеш можешь посоветовать ??
С Уважением Валерий.
Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #5 : 06 Сентябрь 2010, 20:08:55 »

первые байты как раз и нужны чтобы понять принадлежность файла к какой либо группе.
например какой-то file.tmp имеет сигнатуру "MZ" значит исполняемый файл и нечего его сравнивать с каким-то документом.

Имхо, это не четкий критерий.
Например, можно и в текстовом файле написать вначале "MZ".

так размер и будет этим уникальным ID

Не, я имел в виду, ID, который будет обозначать группу файлов, в которой возможны дубликаты.
Изначально эта группа - одна (все файлы). А потом они разделяются последовательно на более мелкие группы (например, сначала по размерам, потом - по еще чему нибудь).

какой хеш можешь посоветовать ??

Да тут практически все, что угодно - от CRC32 до криптографических хешей типа RIPEMD, SHA. Выбор зависит лишь от скорости, наверно.

Вот статья про хеширование в википедии: хеширование.
Там в самом конце перечислены ссылки на статьи по конкретным хешам (как общим, так и криптохешам).

З.Ы. быстрая, с 32-х битным результатом - FAQ6.
Записан

Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!