Бойер Мур ищет маленький ключ

Question

Во-первых, я очень мало знаю об алгоритмах, так что терпите меня.

Насколько я понимаю, алгоритм Бойера-Мура быстрее всего с длинным ключом.Так что, если у меня очень короткий ключ (например, 10 символов) и много текста для поиска (более 10000 символов).Был бы Бойер Мур лучшим алгоритмом поиска для этого сценария?

Если бы не то, что было бы?

Answer 1

Согласно алгоритму поиска строки , «алгоритм поиска строки Бойера-Мура является стандартным эталоном для практической литературы по поиску строки». Это не всегда самый быстрый, но в целом это путь.

Кнут-Моррис-Пратт и Бойер-Мур очень близки во времени выполнения, когда вы говорите о небольшом текстовом буфере, таком как 10000 символов. Даже простой поиск строк будет ослепительно быстрым в 10K буфере при запуске на современном компьютере. Я подозреваю, что вы обнаружите, что разница между KMP и Бойером-Муром, которые ищут строку из 10 символов в буфере из 10 000 символов, будет порядка наносекунд.

Лучший алгоритм поиска в этом сценарии? Это будет зависеть от того, как часто вам нужно звонить. Если это то, что вызывается несколько раз в секунду (самое большее), я, вероятно, напишу наивный поиск и оставлю это на этом. Разница между Boyer-Moore и наивным поиском в этом небольшом буфере будет незначительной по сравнению со временем выполнения вашей программы, и ваши усилия по оптимизации будут лучше потрачены где-то еще. Если бы мне приходилось вызывать его сотни или тысячи раз в секунду, я бы нашел время для написания оптимизированного поиска Бойера-Мура.

Answer 2

Чтобы ответить на ваш вопрос, вам нужно посетить только одну ссылку: http://www.codeproject.com/Articles/250566/Fastest-strstr-like-function-in-C

На самом деле домашняя страница самого быстрого текстового поисковика такова: http://www.sanmayce.com/Railgun/index.html

> Так что, если у меня очень короткий ключ (например, 10 символов) и много текста для поиска (более 10000 символов). Именно этот ключевой диапазон (10-11 символов) проверен в моем тяжелом (1 ТБ) вскрытии strstr. Там 400 000 слов ищутся в 300 000 слов, один на один, отличная загрузка для функции strstr!

> Будет ли Бойер Мур лучшим алгоритмом поиска для этого сценария? Согласно моим тестам, самый быстрый текстовый поисковик (использующий Microsoft V16 / Ox) - Railgun_Quadruplet_7Gulliver , но это второй лучший вариант, когда используется / Ox и Intel 12.1, вы можете протестировать его самостоятельно, см. Ниже.

Если у вас быстрый компьютер, скажем, i7 37 *, я хотел бы увидеть ваши результаты моего последнего пакета тестирования консоли (тестирование Microsoft v16 против Intel 12.1 компиляторов):
http://www.sanmayce.com/Downloads/_KAZE_Benchmark_2013.zip

Тест на моем ноутбуке T7500 2200 МГц:

E:\_KAZE_Benchmark_2013>RUNME.bat

E:\_KAZE_Benchmark_2013>SKYFALL_TXT2HTML_MicrosoftV16.exe MIX_Tesla_BABAJI_Castaneda_Poirot_Holmes_Sunnah_Hadith_Quran_Bible_Patanjali_Dao_Simplici
ssimus.wrd.txt MASAKARI_General-Purpose_Grade_English_Wordlist_r3_316423_words.wrd /Gulliver
SKYFALL_TXT2HTML, revision 2, written by Kaze.
Size of 1st input file: 8916987
Size of 2nd input file: 3869529

Doing Search for each word with Railgun_Quadruplet_7Gulliver ...
Railgun_Quadruplet_7Gulliver performance: 1944+KB/clock
Average Pattern Length: 11
Function Invocations: 420,640
Function Inner-Loop Iterations: 131,873,881,926
Function Really Traversed: 1,142,740,439KB

E:\_KAZE_Benchmark_2013>SKYFALL_TXT2HTML_MicrosoftV16.exe MIX_Tesla_BABAJI_Castaneda_Poirot_Holmes_Sunnah_Hadith_Quran_Bible_Patanjali_Dao_Simplici
ssimus.wrd.txt MASAKARI_General-Purpose_Grade_English_Wordlist_r3_316423_words.wrd
SKYFALL_TXT2HTML, revision 2, written by Kaze.
Size of 1st input file: 8916987
Size of 2nd input file: 3869529

Doing Search for each word with Railgun_Quadruplet_7 ...
Railgun_Quadruplet_7 performance: 1747+KB/clock
Average Pattern Length: 11
Function Invocations: 420,640
Function Inner-Loop Iterations: 146,826,792,351
Function Really Traversed: 1,142,740,439KB

E:\_KAZE_Benchmark_2013>SKYFALL_TXT2HTML_MicrosoftV16.exe MIX_Tesla_BABAJI_Castaneda_Poirot_Holmes_Sunnah_Hadith_Quran_Bible_Patanjali_Dao_Simplici
ssimus.wrd.txt MASAKARI_General-Purpose_Grade_English_Wordlist_r3_316423_words.wrd /Hasherezade
SKYFALL_TXT2HTML, revision 2, written by Kaze.
Size of 1st input file: 8916987
Size of 2nd input file: 3869529

Doing Search for each word with Railgun_Hasherezade ...
Railgun_Hasherezade performance: 1774+KB/clock
Average Pattern Length: 11
Function Invocations: 420,640
Function Inner-Loop Iterations: 128,900,655,391
Function Really Traversed: 1,142,740,439KB

Существуют некоторые взлеты и падения при использовании 32-битного и 64-битного кода, а также значительные различия между Microsoft и Intel.

"Двигатель" Гулливера - это заказ 2 BM-Horspool , настроенный мной.

Как вы можете видеть на моем скромном ноутбуке Гулливер ищет шаблоны (Средняя длина шаблона: 11) при 1898 МБ / с , даже очень красивые BNDM сгибает колено здесь.