информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Spanning Tree Protocol: недокументированное применениеСтрашный баг в WindowsЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 The Great Suspender предположительно... 
 Десятилетняя уязвимость в sudo 
 Блокировка Flash поломала китайскую... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
[C++] А ты попробуй так... 09.12.04 15:42  Число просмотров: 2418
Автор: HandleX <Александр Майборода> Статус: The Elderman
Отредактировано 09.12.04 15:44  Количество правок: 1
<"чистая" ссылка>
> Доброго времени суток!
Доброго.

> Нужен алгоритм, самое главное быстрый!! поиска строк по
> символу признаку, например найти в файле строчки содержащие большую букву "А"
> (или любую другую), при этом учитывая что строки
> заканчиваюца и начинаюца не обязятельно с пробелов, (есть и
> другие символы, как то всякие скобки и т.д. - даже есть
> символы не текстовые - те что меньше 0x20)
> Буква можен быть не только первой - тоесть это не просто
> слова начинающиеся с большой буквы "А"
> Файл открываеца по пути - тоесть например CreateFile и т.д.
Слышал что-нить про Mapping? CreateFileMapping() и т.д.
В конце концов ты получишь указатель на виртуальную память, отображённую в этот файл. Убиваешь этим несколько зайцев -- т.е. самому тебе malloc делать не надо, файл читать не надо, и т.д. -- мощная штука, кстати.
Ну а потом REP SCASB и вуаля ;-)
Далее откатываешься назад... Странно, почему ты решил что начало строки у тебя тоже будет ограничиваться нулём? Ну да ладно. Потом кастишь указатель начала строки как PChar, и всё.
В общем, пробуй.
<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
<"чистая" ссылка>
1






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


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