3

まず、私はアルゴリズムについてほとんど知らないので、我慢してください。

私が理解しているように、ボイヤームーアアルゴリズムは長いキーで最速です。したがって、非常に短いキー（たとえば、10文字）と検索するテキスト（10,000文字以上）がある場合はどうなりますか。ボイヤームーアは、このシナリオに最適な検索アルゴリズムでしょうか？

そうでない場合はどうなりますか？

4

2 に答える 2

2

文字列検索アルゴリズムによると、「ボイヤー-ムーア文字列検索アルゴリズムは、実用的な文字列検索文献の標準的なベンチマークでした。」常に最速であるとは限りませんが、一般的にはそれが進むべき道です。

Knuth-Morris-PrattとBoyer-Mooreは、10,000文字のような小さなテキストバッファについて話しているとき、実行時間に非常に近いです。単純な文字列検索でさえ、最新のコンピューターで実行すると、10Kバッファーでは目がくらむほど高速になります。10,000文字のバッファで10文字の文字列を検索するKMPとBoyer-Moore2の違いは、ナノ秒のオーダーになると思います。

このシナリオで最適な検索アルゴリズムは？それはあなたがそれを呼ぶ必要がある頻度に依存するでしょう。それが（せいぜい）1秒間に数回呼び出されるものであれば、私はおそらく素朴な検索を書いて、そのままにしておきます。その小さなバッファーでのボイヤームーア文字とナイーブ検索の違いは、プログラムの実行時間と比較して重要ではなく、最適化の作業は別の場所で行う方がよいでしょう。1秒間に数百回または数千回呼び出す必要がある場合は、時間をかけて最適化されたボイヤームーア文字検索を記述します。

于 2011-09-28T15:58:05.230 に答える
0

あなたの質問に答えるには、1つのリンクだけにアクセスする必要があります：http： //www.codeproject.com/Articles/250566/Fastest-strstr-like-function-in-C

実際、最速のテキスト検索者のホームページは次のとおりです。http: //www.sanmayce.com/Railgun/index.html

>それで、私が非常に短いキー（例10文字）と検索するテキストがたくさんある場合（10,000文字以上）はどうなりますか？ まさにこのキー範囲（10-11文字）は私の重い（1TB）strstr対決でテストされています。30万語で40万語が検索され、1つずつ検索されます。これはstrstr関数の優れた負荷です。

>ボイヤームーアはこのシナリオに最適な検索アルゴリズムでしょうか？ 私のテストによると、（Microsoft V16 / Oxを使用する）最速のテキストサーチャーはRailgun_Quadruplet_7Gulliverですが、/OxとIntel12.1を使用すると、2番目に優れています。自分でテストできます。以下を参照してください。

高速なマシン、たとえばi7 37 *をお持ちの場合は、最新のコンソールベンチマークパッケージ（Microsoftv16とIntel12.1コンパイラのテスト）の結果を確認したいと思います：http：
//www.sanmayce.com/Downloads/_KAZE_Benchmark_2013.zip

T75002200Mhzノートブックでテストします。

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の間にもかなりのマージンがあります。

ガリバーの「エンジン」は、私が調整したオーダー2BM-Horspoolです。

私の謙虚なラップトップでわかるように、ガリバーは1898MB / sでパターン（平均パターン長：11）を検索しますが、非常に美しいBNDMでさえここで膝を曲げます。

于 2013-01-11T15:09:21.937 に答える