環境：
最適化しようとしているコード/テキスト エディターがあります。現在、プログラムのボトルネックは、すべてのキーワードをスキャンする言語パーサーです (複数ありますが、一般的に同じように記述されています)。
1,000,000私のコンピューターでは、コード行の周りのファイルでエディターが遅延します。Raspberry Pi のようなローエンドのコンピューターでは、遅延がはるかに早く発生し始めます (正確には覚えていませんが10,000、コードの行数あたりだと思います)。また、コード行よりも大きなドキュメントを見たことはありません1,000,000が、確かに存在するので、自分のプログラムでそれらを編集できるようにしたいと考えています。
質問：
これは、大きな動的文字列内の単語のリストをスキャンする最速の方法は何ですか?という質問につながります。
アルゴリズムの設計に影響を与える可能性のある情報を次に示します。
- キーワード
- キーワードの一部として使用できる修飾文字 (私はそれらを修飾子と呼びます)
- 大きな文字列
ボトルネック ソリューション:
これは（大まかに）私が現在文字列を解析するために使用している方法です：
// this is just an example, not an excerpt
// I haven't compiled this, I'm just writing it to
// illustrate how I'm currently parsing strings
struct tokens * scantokens (char * string, char ** tokens, int tcount){
int result = 0;
struct tokens * tks = tokens_init ();
for (int i = 0; string[i]; i++){
// qualifiers for C are: a-z, A-Z, 0-9, and underscore
// if it isn't a qualifier, skip it
while (isnotqualifier (string[i])) i++;
for (int j = 0; j < tcount; j++){
// returns 0 for no match
// returns the length of the keyword if they match
result = string_compare (&string[i], tokens[j]);
if (result > 0){ // if the string matches
token_push (tks, i, i + result); // add the token
// token_push (data_struct, where_it_begins, where_it_ends)
break;
}
}
if (result > 0){
i += result;
} else {
// skip to the next non-qualifier
// then skip to the beginning of the next qualifier
/* ie, go from:
'some_id + sizeof (int)'
^
to here:
'some_id + sizeof (int)'
^
*/
}
}
if (!tks->len){
free (tks);
return 0;
} else return tks;
}
可能な解決策：
状況に応じたソリューション:
私は次のことを検討しています：
大きな文字列を 1 回スキャンし、(ドキュメント全体を何度も再スキャンする代わりに) ユーザー入力があるたびにトークン マーカーを評価/調整する関数を追加します。解析がはるかに少ないため、これでボトルネックが解消されると期待しています。ただし、最初のスキャンにはまだ非常に長い時間がかかる可能性があるため、プログラムを完全に修正することはできません。
トークン スキャン アルゴリズムを最適化する (以下を参照)
これらの最適化も検討しましたが、拒否しました。
- 画面上だけにあるコードをスキャンします。これによりボトルネックは解消されますが、画面の開始位置よりも前に表示されるユーザー定義のトークン (つまり、変数名、関数名、マクロ) を見つける機能が制限されます。
- モノリシックな配列ではなく、リンクされたリスト (行ごとのノード) にテキストを切り替えます。これは実際にはボトルネックを助けません。挿入/削除は高速になりますが、インデックス付きアクセスが失われるとパーサーの速度が低下します。また、モノリシックな配列は、分割されたリストよりもキャッシュされる可能性が高いと思います。
- すべての言語のスキャン トークン関数をハード コーディングします。これはパフォーマンスの最適化には最適かもしれませんが、ソフトウェア開発の観点からは実用的ではないようです。
アーキテクチャ ソリューション:
アセンブリ言語では、これらの文字列を解析するより迅速な方法は、文字をレジスタにロードし、それら4または8バイトを一度に比較することです。次のような追加の対策と予防措置を考慮する必要があります。
- アーキテクチャは、アライメントされていないメモリ アクセスをサポートしていますか?
- すべての文字列は、読み取り違反を防ぐために、サイズ
sが である必要があります。s % word-size == 0 - その他？
しかし、これらの問題は簡単に修正できるようです。唯一の問題 (アセンブリ言語での記述に伴う通常の問題を除く) は、ハードウェア ソリューションであるため、アルゴリズム ソリューションではありません。
アルゴリズム ソリューション:
これまでのところ、二分探索アルゴリズムをもう少し可能にするために、プログラムにキーワードのリストを再配置させることを検討してきました。
このためにそれらを再配置することを考えた 1 つの方法は、キーワードのリストの次元を切り替えることです。の例を次に示しCます。
// some keywords for the C language
auto // keywords[0]
break // keywords[1]
case char const continue // keywords[2], keywords[3], keywords[4]
default do double
else enum extern
float for
goto
if int
long
register return
short signed sizeof static struct switch
typedef
union unsigned
void volatile
while
/* keywords[i] refers to the i-th keyword in the list
*
*/
2 次元配列の次元を切り替えると、次のようになります。
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
-----------------------------------------------------------------
1 | a b c c c c d d d e e e f f g i i l r r s s s s s s t u u v v w
2 | u r a h o o e o o l n x l o o f n o e e h i i t t w y n n o o h
3 | t e s a n n f u s u t o r t t n g t o g z a r i p i s i l i
4 | o a e r s t a b e m e a o g i u r n e t u t e o i d a l
5 | k i u l r t s r t e o i c c d n g t e
6 | n l e n t n d f c t h e n i
7 | u t e f e l
8 | e r d e
// note that, now, keywords[0] refers to the string "abccccdddeeefffiilrr"
これにより、二分探索アルゴリズム (または単純なブルート フォース アルゴリズム) を使用することがより効率的になります。ただし、各キーワードの最初の文字の単語のみであり、その後は「ソート済み」と見なすことはできません。これは、プログラミング言語のような単語の小さなセットには役立つかもしれませんが、(英語全体のような) 大きな単語のセットには十分ではありません。
このアルゴリズムを改善するためにできる以上のことはありますか?
パフォーマンスを向上させるために使用できる別のアプローチはありますか?
ノート：
SOからのこの質問は役に立ちません。Boyer-Moore-Horspool アルゴリズム (私が理解しているように) は、文字列内の部分文字列を見つけるためのアルゴリズムです。複数の文字列を解析しているので、最適化の余地がはるかにあると思います。