|
Разработчик
Ответов: 26170
Рейтинг: 2127
|
|||
|
Леонид писал(а): не понятно почемуИ чего там непонятного, так и должно быть -- при меньшем количестве букв, меньше максимальное относительное смещение, дольше поиск, а алгоритм-то не шибко короткий, вот и тратит время на лишние операции, с той же таблицей, например. Но ни в одном случае (кроме поиска одного символа), он не отличался сильно от asm-кода на Intel процессорах в самом худшем случае (у меня при двух символах) |
|||
| карма: 22 |
|
Ответов: 8930
Рейтинг: 823
|
|||
|
nesco, захотелось сравнить прямолинейный поиск - оказалось чистое время поиска всего в два раза больше, чем у штатного. code_18008.txt
|
|||
| карма: 19 |
| ||
| файлы: 2 | position.jpg [70.5KB] [176], code_18008.txt [2.5KB] [234] |
|
Разработчик
Ответов: 26170
Рейтинг: 2127
|
|||
|
Ага, на длинных словах , аж на порядок, уступает АБМ
|
|||
| карма: 22 |
|
|
Ответов: 16884
Рейтинг: 1239
|
|||
|
nesco, зря ты послушался Assasin-а
Идея алгоритма БМ-поиска в том, что сравнению подвергаются не первые, а последние символы образца Р и очередного фрагмента строки S. Если они не равны, то сдвиг в строке S осуществляется сразу на всю длину образца. Если последние символы равны, то сравнению подвергаются предпоследние символы, и т. д. При несовпадении очередных символов величина сдвига извлекается из таблицы D, которая, таким образом, выполняет ключевую роль в этом алгоритме. Заполнение таблицы происходит на основе конкретной строки-образца Р следующим образом. Размер таблицы определяется размером алфавита, то есть количеством кодов символов, которые могут появляться в тексте. В этом случае под таблицу D память длиной, равной длине кодовой таблицы ASCII. Таким образом, строки S и Р могут содержать любые символы. Первоначально все байты кодовой таблицы заполняются значением, равным длине строки-образца для поиска Р. Далее последовательно извлекаются символы строки-образца Р начиная с первого. Для каждого символа определяется позиция его самого правого вхождения в строку-образец Р. Это значение и заносится в таблицу D на место, соответствующее этому символу ------------ Дoбавленo в 12.16: Выходит правильным был твой первый вариант БМ |
|||
| карма: 25 |
|
|
Разработчик
Ответов: 26170
Рейтинг: 2127
|
|||
|
Tad писал(а): зря ты послушался Assasin-аОн тут совсем не причем, это немного другой вариант алгоритма. И если бы я не нашел его, как реализацию к математическому обоснованию, я бы не послушал Assasin-а и не поставил бы его Tad писал(а): Выходит правильным был твой первый вариант БМСкорость поиска этого варианта ниже (почти, в два раза), чем последнего при любых количествах поисковых символов |
|||
| карма: 22 |
|
Поиск
Друзья
Администрация