11

switchが 5000 を超えるとどうなりますかcase。欠点は何ですか?また、それをより高速なものに置き換えるにはどうすればよいですか?

注:配列は同じであるため、ケースを格納するために配列を使用することは期待していません。

4

4 に答える 4

13

switch/case ステートメント以外が必要だと考える特別な理由はありません (実際、私はそれが役に立たないことを積極的に期待しています)。コンパイラは効率的なディスパッチ コードを作成する必要があります。これには、静的 [スパース] テーブルと直接インデックス付け、バイナリ分岐などの組み合わせが含まれる場合があります。ケースの静的な値への洞察があり、優れた仕事をするはずです (ケースを変更するたびにその場で再調整しますが、大幅に異なる値など、手作りのアプローチにはうまく適合しない新しい値かなりパックされた配列ルックアップがあった場合、コードの再作業が必要になるか、静かにメモリが膨張したり、パフォーマンスが低下したりする可能性があります)。

Cが筋金入りのアセンブリプログラマーを獲得しようとしていた頃、人々はこの種のことを本当に気にかけていました...コンパイラーは良いコードを生成する責任を負っていました。別の言い方をすれば、(ある程度) 壊れていない場合は、修正しないでください。

より一般的には、この種のことに興味を持ち、代替案とそのパフォーマンスへの影響について人々のアイデアを得るのは素晴らしいことですが、本当に気にかけ、パフォーマンスの違いがプログラムに有益な違いをもたらす可能性がある場合 (特にプロファイリングがそれを示唆している場合) は、常にあなたのプログラムが実際の仕事をしているベンチマーク。

于 2012-09-12T07:22:54.803 に答える
11

思考の糧として...古い/バグのある/非効率的なコンパイラーで立ち往生している場合、または単にハッキングが好きな場合に備えて。

ステートメントの内部作業はswitch2 つの部分で構成されます。ジャンプするアドレスを見つけて、そこにうまくジャンプ。最初の部分では、アドレスを見つけるためにテーブルを使用する必要があります。件数が増えるとテーブルが大きくなり、ジャンプするアドレスを探すのに時間がかかります。これは、コンパイラがいくつかの手法を組み合わせて最適化しようとするポイントですが、簡単な方法の 1 つは、大文字と小文字の値の空間に依存するテーブルを直接使用することです。

ナプキン例の裏に・・・

switch (n) {
    case 1: foo(); break;
    case 2: bar(); break;
    case 3: baz(); break;
}

このようなコードを使用すると、コンパイラは jump_addresses の配列を作成し、array[n] でアドレスを直接取得できます。これで、検索に O(1) がかかりました。ただし、次のようなスイッチがある場合：

switch (n) {
    case 10: foo(); break;
    case 17: bar(); break;
    case 23: baz(); break;
    // and a lot other
}

コンパイラは、case_id、jump_address のペア、およびコードを含むテーブルを生成して、最悪の実装では O(n) になる可能性があるその構造を検索する必要があります。(適切なコンパイラは、そのような最適化されたコードをデバッグする必要があるときに脳がフライを開始する程度に最適化フラグを有効にすることによって、完全に解き放たれたときに、そのようなシナリオから地獄を最適化します。)

質問は、これをすべて自分で C レベルで実行して、コンパイラを打ち負かすことができるかということです。面白いことに、テーブルを作成してそれらを検索するのは簡単に思えgotoますが、標準 C では変数ポイントにジャンプすることはできません。したがって、オーバーヘッドやコード構造のために関数ポインターを使用しない場合は、詰まっている...まあ、使用していない場合GCC。GCC には、 Labels as Valuesと呼ばれる非標準機能があり、ラベルへのポインターを取得するのに役立ちます。

例を完了するには、次のように「値としてのラベル」機能を使用して 2 番目の switch ステートメントを記述できます。

const void *cases[] = {&&case_foo, &&case_bar, &&case_baz, ....};
goto *labels[n];
case_foo:
    foo();
    goto switch_end;
case_bar:
    bar();
    goto switch_end;
case_baz:
    baz();
    goto switch_end;
// and a lot other
switch_end:

もちろん、5000 のケースについて話しているのであれば、このコードを作成するためのコードを書いた方がはるかに優れています。おそらく、それがそのようなソフトウェアを維持する唯一の方法です。

結びのメモとして; これはあなたの毎日の仕事を改善しますか？いいえ、これはあなたのスキルを向上させますか? はい、経験から言えば、大文字と小文字の値を最適化するだけで、スマート カードのセキュリティ アルゴリズムを改善できたことがあります。不思議な世界です。

于 2012-09-12T08:30:49.443 に答える
3

Delegate値でDictionaryクラスを使用してみてください。少なくとも、コードが少し読みやすくなります。

于 2012-09-12T07:20:48.647 に答える