Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, serzhik, Вы писали:
S>>Как искать текст в файле? Если не сложно, можете привести примерчик или ссылочку полезную сбросить???
К>Какие аспекты тебя интересуют?
К>Алгоритмы — см., например, АлгоЛист. К>Доступ к файлу — последовательный или отображение файла в память (файл-маппинг — это уже в WinAPI).
К>
А не знаешь ли, будет ли, например алгоритм Боуера-Мура, в общем случае эффективней чем стандартные возможности, например strstr?
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>А не знаешь ли, будет ли, например алгоритм Боуера-Мура, в общем случае эффективней чем стандартные возможности, например strstr?
strstr на ассемблере x86 может оказаться и быстрее... для коротких строк.
Но это надо мерять... Я этим не занимался.
Здравствуйте, Flamer, Вы писали:
F>[]
ДН>>А не знаешь ли, будет ли, например алгоритм Боуера-Мура, в общем случае эффективней чем стандартные возможности, например strstr?
F>В форуме "Исходники" — здесь
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>>А не знаешь ли, будет ли, например алгоритм Боуера-Мура, в общем случае эффективней чем стандартные возможности, например strstr?
F>В форуме "Исходники" — здесь
.
ДН>Ок, за ссылку спасибо. Но меня больше интересовало сравнение со стандартными функциями поиска — стоит ли овчинка выделки?
Если надо несколько раз искать одну и ту же строку — то почти всегда стоит. Но если и без того быстродействия хватает — то, разумеется, не стоит — че тут еще скажешь ?
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, Sergey, Вы писали:
S>Если надо несколько раз искать одну и ту же строку — то почти всегда стоит. Но если и без того быстродействия хватает — то, разумеется, не стоит — че тут еще скажешь ?
А если все хитрее — есть 100000 текстов, нужно выбрать в каких из них есть вхождение искомой строки, то есть поиск идет до первого встречного, что тогда?
Здравствуйте, Дмитрий Наумов, Вы писали:
ДН>А если все хитрее — есть 100000 текстов, нужно выбрать в каких из них есть вхождение искомой строки, то есть поиск идет до первого встречного, что тогда?
Юзать однозначно. Там по сравнению с "тупым" поиском есть некоторые потери на заполнение таблицы, зависящей от строки, поэтому если их можно считать малыми (длинные тексты, длинная строка или много поисков одной и той же строки), то применение этого алгоритма целесообразно. А вот для юникода оно не очень подходит — алфавит большой, придется разреженный массив городить.
Удалено избыточное цитирование. -- ПК.
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, Sergey, Вы писали:
S>Юзать однозначно. Там по сравнению с "тупым" поиском есть некоторые потери на заполнение таблицы, зависящей от строки, поэтому если их можно считать малыми (длинные тексты, длинная строка или много поисков одной и той же строки), то применение этого алгоритма целесообразно. А вот для юникода оно не очень подходит — алфавит большой, придется разреженный массив городить.
Для юникода (UTF-16 и UTF-32) можно сделать побайтовый поиск, а при нахождении проверять смещение. Если найденный блок байтов не выравнен на границу юникодного символа — продолжить поиск.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Sergey, Вы писали:
S>Юзать однозначно. Там по сравнению с "тупым" поиском есть некоторые потери на заполнение таблицы, зависящей от строки, поэтому если их можно считать малыми (длинные тексты, длинная строка или много поисков одной и той же строки), то применение этого алгоритма целесообразно. А вот для юникода оно не очень подходит — алфавит большой, придется разреженный массив городить.
К>Для юникода (UTF-16 и UTF-32) можно сделать побайтовый поиск, а при нахождении проверять смещение. Если найденный блок байтов не выравнен на границу юникодного символа — продолжить поиск.
Тут еще вопрос, что медленней будет. IMHO, алгоритм с разреженным массивом для алфавитов с фиксированной длиной символа можно сделать более быстрым.
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, Sergey, Вы писали:
К>>Для юникода (UTF-16 и UTF-32) можно сделать побайтовый поиск, а при нахождении проверять смещение. Если найденный блок байтов не выравнен на границу юникодного символа — продолжить поиск.
S>Тут еще вопрос, что медленней будет. IMHO, алгоритм с разреженным массивом для алфавитов с фиксированной длиной символа можно сделать более быстрым.
Ну, если не жалко 2^16 вордов на таблицу, то Боуер-Мур над вордами будет быстрее, чем над байтами.
Более того, можно сделать наоборот: строку байтов рассмотреть как строку вордов, и искать ее в тексте со смещением +0 и +1
Здравствуйте, Кодт, Вы писали:
К>>Для юникода (UTF-16 и UTF-32) можно сделать побайтовый поиск, а при нахождении проверять смещение. Если найденный блок байтов не выравнен на границу юникодного символа — продолжить поиск.
S>Тут еще вопрос, что медленней будет. IMHO, алгоритм с разреженным массивом для алфавитов с фиксированной длиной символа можно сделать более быстрым.
К>Ну, если не жалко 2^16 вордов на таблицу, то Боуер-Мур над вордами будет быстрее, чем над байтами.
128 Кб? Копейки. Но я вообще-то говорил про разреженный массив. Фактически, массив в Бойер-Муре использован просто для табличного задания функции — позиция(текущий символ). позиция == длина строки для всех букв, не встречающихся в строке. Обычный массив — самый простой и быстрый вариант реализации такой функции в случае маленького алфавита. В случае большого алфавита для реальных строк большая часть значений такой функции будет равна длине строки, поэтому можно попробовать поизвращаться в сторону двух и более уровней массивов и перестановки битов в символах, например.
К>Более того, можно сделать наоборот: строку байтов рассмотреть как строку вордов, и искать ее в тексте со смещением +0 и +1
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Перекуём баги на фичи!
