Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| |
свои сообщения на этом форуме можно редактировать 09.12.04 20:11 Число просмотров: 2651
Автор: LLL <Алексей> Статус: Member
|
|
|
|
<programming>
|
[C++] Быстрый алгоритм поиска строк по символу-признаку 09.12.04 14:24
Автор: ih8u <i hate you> Статус: Member
|
Доброго времени суток!
Нужен алгоритм, самое главное быстрый!! поиска строк по символу признаку,
например найти в файле строчки содержащие большую букву "А" (или любую другую), при этом учитывая что строки заканчиваюца и начинаюца не обязятельно с пробелов, (есть и другие символы, как то всякие скобки и т.д. - даже есть символы не текстовые - те что меньше 0x20)
Буква можен быть не только первой - тоесть это не просто слова начинающиеся с большой буквы "А"
Файл открываеца по пути - тоесть например CreateFile и т.д.
Я реализовывал это так:
открывал файл CreateFile
получал размер - FileSize = GetFileSize
считывал в буфер - char *buffer = (char *)malloc(FileSize); ReadFile
и крутил в цикле for по символьно сравнивая с нужным символом-признаком,
потом откатывался назад до идентификации начала строки, потом крутился вперёд до идентификации конца строки.
Всё работает, до тока медленно, 10кб файл обрабатываеца около секунды - на P4 2.0GHz
Думаю я что не так намутил, поэтому так долго.
Подскажите кто чем может, как лучше сделать
За ранее спасибки!
|
|
[UPD] чтото типа такого? 09.12.04 21:37
Автор: Killer{R} <Dmitry> Статус: Elderman
Отредактировано 09.12.04 22:31 Количество правок: 4
|
void __inline FoundString(char *str,int len)-обработчик строки
int __inline CheckChar(char ch)-проверялка символа - разделитель, ключ или левый, и чтоб была как можно шустрее
void ProcessBuffer(char *buf,int buflen)
{
char *end=buf+buflen,*lst=buf;
bool FoundCon=0;
for(char *tmp=buf;tmp<end;tmp++)
switch(CheckChar(*tmp))
{
case CHAR_STRING_DIVIDER:
if(FoundCon)
{
FoundString(lst,tmp-lst);
FoundCon=0;
}
lst=tmp+1;
break;
case CHAR_STRING_KEY:FoundCon=1;break;
}
if(FoundCon)FoundString(lst,end-lst);
}
|
|
[C++] А ты попробуй так... 09.12.04 15:42
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 09.12.04 15:44 Количество правок: 1
|
> Доброго времени суток!
Доброго.
> Нужен алгоритм, самое главное быстрый!! поиска строк по
> символу признаку, например найти в файле строчки содержащие большую букву "А"
> (или любую другую), при этом учитывая что строки
> заканчиваюца и начинаюца не обязятельно с пробелов, (есть и
> другие символы, как то всякие скобки и т.д. - даже есть
> символы не текстовые - те что меньше 0x20)
> Буква можен быть не только первой - тоесть это не просто
> слова начинающиеся с большой буквы "А"
> Файл открываеца по пути - тоесть например CreateFile и т.д.
Слышал что-нить про Mapping? CreateFileMapping() и т.д.
В конце концов ты получишь указатель на виртуальную память, отображённую в этот файл. Убиваешь этим несколько зайцев -- т.е. самому тебе malloc делать не надо, файл читать не надо, и т.д. -- мощная штука, кстати.
Ну а потом REP SCASB и вуаля ;-)
Далее откатываешься назад... Странно, почему ты решил что начало строки у тебя тоже будет ограничиваться нулём? Ну да ладно. Потом кастишь указатель начала строки как PChar, и всё.
В общем, пробуй.
|
| |
Да, Про маппинг совсем забыл, 09.12.04 16:55
Автор: ih8u <i hate you> Статус: Member
|
Да, Про маппинг совсем забыл,
это я всё сделал.
Вот тут придумал имхо не плохой способ, заключающийся вот в чём:
Открываем файл - CreateFile
маппим его - hMap = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
получаем размер - filesize = GetFileSize(hFile, NULL);
адресс - LPVOID lpBase = MapViewOfFile(hMap, FILE_MAP_READ, 0, 0, 0);
Далее
while(1)
{
LPVOID lpTemp = memchr(lpBase, 'A', filesize);
if(lpTemp)
{
// символ найден
lpBase = lpTemp;
for(int i = 1; i < 30; i++)
{
// пробуем откатываца назад, ограничение в 30 байт - больше не имеет смысла
memcpy(&buf[0], (LPTSTR)lpBase - i, 1); // Копируеца один символ и проверяеца
if(buf[0] == ''|buf[0] == ''|и т.д.)
break;
}
// Крутимся вперёд, максимум на 50 символов, больше не имеет смысла
for(int k = 0; k < 50; k++)
{
memcpy(&buf[k], (LPTSTR)lpBase - j + k + 1, 1); // считываем по символу и проверяем конец
if(buf[0] == ''|buf[0] == ""|buf[0] == '' и т.д.)
{
buf[k] = 0; // считали
break;
}
}
// тута надо пересчитать адреса и вычислить новый filesize что бы memchr начал искать с новой позиции, но у меня нифига не получаеца, компилятор пишет ощибку 'void *' : unknown size
}
else
//символ не найден, прерываем цикл
break;
}
|
| | |
Ну вот, уже лучше ;-) 09.12.04 17:25
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 09.12.04 17:30 Количество правок: 4
|
Проникнись всё же использованием REP SCASB, он быстр для твоей цели настолько, насколько позволяет процессор и шина памяти вкупе с механизмом виртуализации виндов. Хотя возможно, это сделает за тебя оптимизатор, если поймёт смысл ;-)
Потом в том месте, где ты нашёл маркер, зачем опять копируешь в буфер?
Заведи новый указатель на Char, приравняй его к получившемуся в поиске, и последовательно откатывайся в цикле for (делая декремент указателю) на 50 символов назад, проверяя значение по нему на чего тебе надо (на 0 вроде).
То же самое и поиск окончания строки.
|
| | | |
Можно по подробнее про rep scasb??? 09.12.04 18:12
Автор: ih8u <i hate you> Статус: Member
|
> Проникнись всё же использованием REP SCASB, он быстр для
> твоей цели настолько, насколько позволяет процессор и шина
> памяти вкупе с механизмом виртуализации виндов. Хотя
> возможно, это сделает за тебя оптимизатор, если поймёт
> смысл ;-)
>
> Потом в том месте, где ты нашёл маркер, зачем опять
> копируешь в буфер?
> Заведи новый указатель на Char, приравняй его к
> получившемуся в поиске, и последовательно откатывайся в
> цикле for (делая декремент указателю) на 50 символов назад,
> проверяя значение по нему на чего тебе надо (на 0 вроде).
>
> То же самое и поиск окончания строки.
Можно по подробнее про REP SCASB???
А то это мне вобще ничо не говарит :))
|
| | | | |
Это ассемблерная инструкция микропроцессора. Ищет указанный байт по указателю, доколе на него не натолкнётся. Поищи в Инете про неё. 09.12.04 18:19
Автор: HandleX <Александр М.> Статус: The Elderman
|
|
У тебя что за компилер? «Продвинутые» с хорошим оптимизатором обычно сами находят возможность применение это инструкции, исходя из твоего сяшного кода. Но может это и не случиться.
|
| | | | | |
Компилер MS Visual C++ 6.0 10.12.04 11:51
Автор: ih8u <i hate you> Статус: Member
|
|
|
| |
[C++] Не уверен, что rep scasb будет эффективным 09.12.04 15:50
Автор: amirul <Serge> Статус: The Elderman
|
> Слышал что-нить про Mapping? CreateFileMapping() и т.д.
> В конце концов ты получишь указатель на виртуальную память,
> отображённую в этот файл. Убиваешь этим несколько зайцев --
> т.е. самому тебе malloc делать не надо, файл читать не
> надо, и т.д. -- мощная штука, кстати.
> Ну а потом REP SCASB и вуаля ;-)
> Далее откатываешься назад... Странно, почему ты решил что
Он был бы эффективным, если бы не надо было откатываться назад. Если считать, что положение символа "А" в строке равномерно распределено, то суммарно придется откатываться на половину длины файла. Лучше уж посимвольно просматривать и запоминать, где началась строка, в которой мы в данный момент находимся
> начало строки у тебя тоже будет ограничиваться нулём? Ну да
> ладно. Потом кастишь указатель начала строки как PChar, и
> всё.
> В общем, пробуй.
|
| | |
[C++] У него, скорее всего, начало строки недалеко от символа-маркера. По крайней мере, будет быстрее flex'a ж-) 09.12.04 15:55
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 09.12.04 15:55 Количество правок: 2
|
|
|
| | | |
[C++] Быстрее flex-а точно не будет 09.12.04 16:17
Автор: amirul <Serge> Статус: The Elderman
|
|
Он строит кучу таблиц и решение, о том что делать дальше принимает только на основании ОДНОЙ выборки из таблицы.
|
|
[C++] Возьми flex и не мучайся 09.12.04 15:38
Автор: amirul <Serge> Статус: The Elderman
|
Если хочется реализовывать все самому, то лучше найди библиотеку регулярных выражений и не мучайся.
Если хочется реализовывать ВСЕ самому, то делай так:
Заводишь массив на 256 элементов и выставляешь там флаги для всех символов, которые разделяют строки.
Заводишь переменную начало_предыдущей_строки и инициализируешь ее началом буфера, в котором лежит текст.
В цикле пробегаешь по буферу, считываешь символ c, берешь флаг из массива флагов по индексу c, если флаг выставлен, то запоминаешь в начало_предыдущей_строки позицию следующего символа.
Если встретился символ "А", то пробегаешь до конца строки и можешь выводить найденную строку.
|
| |
[C++] про flex и про "ручной" метод 09.12.04 20:09
Автор: LLL <Алексей> Статус: Member
|
> Если хочется реализовывать все самому, то лучше найди
> библиотеку регулярных выражений и не мучайся.
Вероятно тут надо было записать "если НЕ хочется"?..
Извиняюсь, что спрашиваю, не читая док по flex'у.
Этому flex'у по барабану, что в обрабатываемых данных есть любые байты, в т.ч. и нулевые?
> Если хочется реализовывать ВСЕ самому, то делай так:
... или даже так:
>
> Заводишь массив на 256 элементов и выставляешь там флаги
> для всех символов, которые разделяют строки.
> Заводишь переменную начало_предыдущей_строки и
> инициализируешь ее началом буфера, в котором лежит текст.
> В цикле пробегаешь по буферу, считываешь символ c, берешь
> флаг из массива флагов по индексу c, если флаг выставлен,
> то запоминаешь в начало_предыдущей_строки позицию
> следующего символа.
... но перед этим проверяешь по флагу_A, не попадалось ли в закончившейся строке символа 'A'.
Если попадалось, то выводишь строку (от начало_предыдущей_строки до текущей позиции) и сбрасываешь флаг_A.
> Если встретился символ "А", то
... выставляешь флаг_A.
|
| | |
flex-у вообще все по барабану - он может обрабатывать любые... 10.12.04 12:29
Автор: amirul <Serge> Статус: The Elderman
|
> Извиняюсь, что спрашиваю, не читая док по flex'у.
> Этому flex'у по барабану, что в обрабатываемых данных есть
> любые байты, в т.ч. и нулевые?
flex-у вообще все по барабану - он может обрабатывать любые потоки символов и вырезать оттуда токены. В сущности он внутри пользуется формализмом регулярных выражений, только все таблицы строятся статически (во время компиляции), в то время как библиотеки регэкспов общего применения строят примерно такие же таблицы только в рантайме.
> ... но перед этим проверяешь по флагу_A, не попадалось ли в
> закончившейся строке символа 'A'.
Ну я как бы имел в виду переход в другое состояние - символ встретился и без всяких проверок ищем до конца строки, хотя такая модификация тоже катит
> Если попадалось, то выводишь строку (от
> начало_предыдущей_строки до текущей позиции) и сбрасываешь
> > Если встретился символ "А", то
> ... выставляешь флаг_A.
|
|
во ещо чо - функциями семейства str*** не пользоваца -... 09.12.04 14:39
Автор: ih8u <i hate you> Статус: Member
|
|
во ещо чо - функциями семейства str*** не пользоваца - поскольку ничо не получица, в файле может быть полно нулевых символов
|
| |
свои сообщения на этом форуме можно редактировать 09.12.04 20:11
Автор: LLL <Алексей> Статус: Member
|
|
|
|
|
подробно о проекте
Анализ криптографических сетевых...
