0

ユニコード文字で構成される文字列があります。同じ文字は一度だけ出現します。文字列の長さは 1 ~ 50 です。

特定の文字が文字列に含まれているかどうかを確認する最も速い方法は何ですか?

文字列を反復するのは良い選択ではありませんね。この目的のための効率的なアルゴリズムはありますか?

私の最初のアイデアは、文字列内の文字をアルファベット順にソートすることでした。すばやく検索できますが、ユニコード文字の並べ替えと比較は (正しい照合を使用して) それほど簡単ではなく、おそらく文字列全体を反復するよりも大きなコストがかかります。

多分いくつかのハッシュ?たぶん、反復が最速の方法ですか?

何か案が?

4

3 に答える 3

4

前処理がない場合、最も簡単で最速の方法は、文字を繰り返し処理することです。

前処理がある場合は、前のアプローチが引き続き最適である可能性があります。または、文字列にその文字が含まれているかどうかを格納する小さなハッシュテーブルを試すこともできます。ハッシュの保存には余分なスペースが必要ですが、メモリ キャッシュには適している可能性があります (ハッシュの競合が少なく、実際の文字列にアクセスする必要がない場合)。必ずパフォーマンスを測定してください。

本当に単純なタスクを過度に設計しようとしているように感じます。これがアプリケーションのボトルネックであることを確認しましたか?

于 2013-09-16T19:42:16.087 に答える