День добрый, всем, Нужен совет, если кто сталкивался.... Задача вполне тривиальная - поиск подстроки в стоке, Алгоритмы Бойера Мура, Карпа Рабина, построение автоматов - ссылки листал, другое дело в их описании говорится об эффективности на больших строках. У меня же условия такие: массив строк в памяти - ну скажем каждая не длиннее 10 символом (длинна самого массива порядка 20 элементов)... так же в другой области в памяти, находится строка которую надо проверить есть ли такая же в массиве (строка тоже не длиннее 10 символом) Реализуется на асме, но нужно сделать как можно эффективнее. Может использовать, так сказать, сравнение "в лоб", то есть посимвольно сравнивать?? или есть более быстрый способ??
Если искать именно подстроку (т.е. при строке "soft" и наличии в массиве "microsoft" считать это совпадением) - кроме как в лоб и посимвольно, для коротких строк, эффективнее не сделать. Можно сравнивать по двойному слову (это выглядит несколько быстрее, чем по 1 символу), сдвигаясь в массиве на 1 байт, но эффективность будет страдать (чтение двойного слова с некратного 4 адреса даст некоторое падение производительности - не факт, что будет заметный выйгрыш). Если есть дополнительные ограничения: - не подстрока, а точное совпадение строк или совпадения только с началом строки, - максимальный размер строк - кратный 4 байтам, - максимальный размер постоянен для всех элементов массива и образца, - все строки с длиной менее максимальной гарантированно дополнены нулями до конца ... то можно подумать о более эффективных и быстрых вариантах, чем посимвольное сравнение.
требуется поиск полного совпадения введенной строки слову из массива... (задача сама по себе простая, но нужно реализовать как можно эффективнее) - других ограничений вроде нет, ну разве что про размер написал выше... Что посоветуете??
если кто реализовывал что нибудь подобное подскажите. потому что сейчас опять обдумал и получается что при использовании хэшей, больше времени уйдет на работу с большими числами...
Если Вы про хеш функцию, пока не знаю. Гугл подсказывает: А по поводу сути, то подумал может, вычислить хеш от каждой из строк в массиве (тут можно даже заменить сами строки массива на их хеши, потому что строки будут неизменны), и по ходу выполнения программы считать хеш от введенного слова и уже сравнивать с содержимым массива.
но хеши могут повторяться, если не сохранить оригиналы строк, можно нарваться на ошибку. тестируя хеш функцию не забудьте убедиться, что все они оригинальны (хеши оригинальны для каждой строки), хотя это не исключит возможность ошибки. где гарантия, что хеш введенной строки не совпадет с хешем из таблицы. тут важно найти совпадения по хешу и потом сравнить строки, тогда ошибки не будет.
Советую глянуть в сторону алгоритма Ахо-Корасик (конечный автомат). Ну если кол-во элементов в массиве ограниченно 20-тью, то наверное не стоит на асме реализовывать конечные автоматы (можно и перебором, если строка не очень длинная =).
max7C4 Да про то, что повторяться могут в курсе (спасибо что все таки упомянули, потому что и правда нужно копию строки хранить) Только вот тут опять наболевший вопрос насколько это эффективно (в контексте условий задачи). Ведь числа получаются большие и использовать придется MMX + операции умножения, оно того стоит ??? T800 Спасибо, но по поводу автоматов в данном случае кажется все таки цель не оправдывает средства
Vic Трудности при построении дерева Бора. А сам поиск это элементарный цикл из 9-15 интрукций (скорость чумовая =).
T800 поясни пожалуйста, про поиск и элементарный цикл, - это ты по поводу чего?? реализации ДКА? или про дерево Бора?
Код (Text): mov ebx, buffer mov eax, last mov ecx, length not eax lp0: xor edx, edx mov dl, al xor dl, [ebx] inc ebx ;========эта часть========== mov edi, 8 lp1: shr edx, 1 jnc @f xor edx, 0xEDB88320 @@: dec edi jnz lp1 ;========эта часть========== shr eax, 8 xor eax, edx loop lp0 not eax CRC32 для таких строк вполне подойдет, повторяться будет достаточно редко, но будет и работает достаточно быстро (и не придется использовать mmx, сравнивать придется всего-то 4-байтные величины) P.S. Вот это часть всегда выдает одни и теже значения. Если не жалко 1 Кб памяти можете составить таблицу и заменить эту часть на Код (Text): mov edx, [esi+edx*4] соответственно в esi надо будет в начале Код (Text): mov esi, CRC32Table
max7C4 Спасибо большое, с алгоритмом пока не разбирался, ближе к вечеру отпишусь что и как. Пока только один вопрос - то есть тем не менее придется при получении совпадения CRC32 сравнивать уже побайтно??
