2

私は楽しみのために作った単純な C インタープリターを最適化しようとしています。私はこのように解析を行っています。
このプロトタイプで関数を最適化したい:

bool parsed_keyword(struct token *, char 辞書[][]);

関数内では、基本的にすべてのキーワードに対して strcmp を呼び出し、トークン タイプを編集します。もちろん、これにより、解析中の文字列ごとに (ほぼ) 20 回の strcmp 呼び出しが発生します。

Rabin-Karp が最適だと思っていましたが、この仕事 (小さな辞書に対して 1 つの単語を照合する) には最適ではないように思えます。この作業を行うのに最適なアルゴリズムは何でしょうか? 提案をありがとう。

4

5 に答える 5

3

この特定の問題には、おそらくハッシュ テーブルを選択します。O(1)あなたのサイズのテーブルのルックアップを提供します。ただし、試してみることも良い選択です。

ただし、実装する最も簡単な方法は、単語をアルファベット順に配列に配置bsearchし、C ライブラリから使用することです。処理する単語は 30 語程度しかないため、ハッシュやトライとほぼ同じ速さである必要があります。ハッシュ値を計算する必要がないため、実際にはハッシュ テーブルよりも高速であることが判明する場合があります。

Steve Jessop のアイデアは、文字列の端から端までを同じサイズの char 配列にレイアウトするという優れたアイデアです。

const char keywords[][MAX_KEYWORD_LEN+1] = {
 "auto", "break", "case", /* ... */, "while"
};

#define NUM_KEYWORDS sizeof(keywords)/sizeof(keywords[0])

int keyword_cmp (const void *a, const void *b) {
    return strcmp(a, b);
}

const char *kw = bsearch(word, keywords, NUM_KEYWORDS, sizeof(keywords[0]),
                         keyword_cmp);

int kw_index = (kw ? (const char (*)[MAX_KEYWORD_LEN+1])kw - keywords : -1);

まだお持ちでない場合は、Compilers: Principles, Techniques, and Toolsのコピーを取得することを検討してください。その表紙から、ドラゴンブックと呼ばれることがよくあります。

于 2012-07-09T17:18:22.887 に答える
1

効率を求めるなら、Rabin Karp は最善の策ではないと思います。Boyer-Moore を使用すると、実装がかなり難しくなりますが、最高の効率が得られます。

楽しみのためにこれを行っている場合、正直なところ、これらの呼び出しはかなり短い時間で実行される必要があり、業界の速度で実行する必要がないため、最適化する必要はないと思います。

クールで便利な目標である文字列一致アルゴリズムを試してみたい場合は、KMP アルゴリズムと Boyer-Moore アルゴリズムを調べることをお勧めします。どちらも実装中に多くのことを教えてくれます。

もちろん、辞書検索や単純なバイナリ検索など、他のより簡単な方法もありますが、文字列を扱っているという事実と文字列比較は必然的に実行される非常に興味深い分野であるため、それらは実際には最適化されていません。ある時点で。

于 2012-07-09T17:21:54.990 に答える
1

キーワードが変更されていないと仮定すると、これは完全なハッシュ関数の適切なケースのように思えます。完全なハッシュ関数は入力を (通常のハッシュ関数のように) 整数にマップしますが、衝突はありません。

ウィキペディアには、 GNU gperfを含むいくつかの完全なハッシュ ジェネレーターへのリンクがあります。

于 2012-07-09T21:01:03.963 に答える
0

ルックアップを行うときに最初に頭に浮かぶのは、ソートされたキーボードの配列を使用し、それらに対してバイナリ検索を実行することです。

于 2012-07-09T17:24:11.127 に答える
0

キーワードのセットが固定されている場合、たとえばgperfを使用して、完全ハッシュを使用できます。これには、一定の作業と単一の文字列比較のみが必要なため、おそらく他のアプローチよりも高速です。

于 2012-07-09T20:36:41.130 に答える