информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Сетевые кракеры и правда о деле ЛевинаСтрашный баг в WindowsАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Microsoft обещает радикально усилить... 
 Ядро Linux избавляется от российских... 
 20 лет Ubuntu 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
[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
<"чистая" ссылка>
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach