スイッチケースやstd :: mapの方が効率的です

Question

ここでトークナイザーについて考えています。
各トークンは、パーサ内で異なる関数を呼び出します。
がより効率的にどのようなものです：

• のstd ::機能のマップは/後押し::機能
• スイッチケース

のVisual Studio 2008に付属している

Answer 1

STLのマップは、あなたを与えるだろう O（ log（n））は各関数呼び出しの下にツリー構造を隠しているためです。 最新のコンパイラ（実装に依存します）では、switch文がO（1）を返します。コンパイラはそれを何らかのルックアップテーブルに変換します。 一般的に、スイッチは高速です。

しかし、以下の事実を考慮してください。

マップとスイッチの間に差があることである：スイッチはできませんが地図を動的に構築することができます。マップはキーとして任意の型を含むことができ、スイッチはC++プリミティブ型（char、int、enumなど）に非常に制限されています。

ところで、ハッシュマップを使用してほぼO（1）ディスパッチを実現できます（ただし、ハッシュテーブルの実装によっては、最悪の場合はO（n）になることがあります）。スイッチはまだまだ高速です。

編集

私は、私はあなたのための素敵な最適化を提案することができ、次の唯一の楽しみのためにと議論

の問題のために書いていますが、それはあなたの言語の性質に依存し、あなたの言語がどのように使われるかを期待できるかどうか。

コードを書くとき トークンを2つのグループに分けます.1つのグループは頻繁に使用頻度が高く、残りの頻度は低い頻度で使用されます。頻繁に使用されるトークンもソートします。 頻繁に使用される頻度が高いif-elseシリーズを頻繁に使用するトークンを作成します。低頻度で使用するために、switch文を記述します。

考え方は、別のレベルの間接を避けるためにも（ifステートメントの条件チェックがほぼ無コストであると仮定して）CPU分岐予測を使用することです。 ほとんどの場合、CPUは間接レベルのない正しいブランチを選択します。しかし、ブランチが間違った場所に行くことはほとんどありません。 ランゲージの性質によって、統計的にはパフォーマンスが向上する可能性があります。

編集：以下のコメントのために、コンパイラが常にスイッチをLUTに変換することを伝える文を変更しました。

Answer 2

"効率的な"あなたの定義は何ですか？あなたがより速いことを意味するならば、おそらく明確な答えのためにいくつかのテストコードをプロファイルするべきでしょう。柔軟性があり、コードを拡張しやすくなっている場合は、自分自身で好きなことを行い、マップの手法を使用してください。それ以外のものは時期尚早の最適化です。

Answer 3

あなたのトークンのタイプはあなたが言っていません。整数でない場合、選択肢はありません。スイッチは整数型でしか動作しません。yossi1981同様

Answer 4

スイッチは、高速ルックアップテーブルをbeeingての最適化を図ることができたが、そこに保証されていない、と述べ、すべてのコンパイラは、連続するように、スイッチを実装するかどうかを決定するために他のアルゴリズムを持っている場合は多分のか、などの高速ルックアップテーブル、または両方の組み合わせ。

高速スイッチを得るには、値が次のルールを満たす必要があります。 これらは連続している必要があります。 0,1,2,3,4。いくつかの値を残しておくことはできますが、0,1,2,34,43のようなものは最適化することはほとんどありません。

質問は本当にあります：あなたのアプリケーションでこのような重要性のパフォーマンスですか？ 複数のコードページにわたる巨大なステートメントの代わりに、ファイルから動的にその値をロードするマップを読みやすく保守しやすいとは思わないでしょうか？

Answer 5

C++標準では、要件のパフォーマンスについては何も言わず、機能はそこにあるはずです。

あなたが話しているの実装について述べていない限り、このような質問の方が優れています。たとえば、JavaScriptの特定の実装の特定のバージョンでの文字列処理は残念ですが、それを関連する標準の機能に推論することはできません。

switchとstd::mapで提供されている機能が異なるため（オーバーラップしているにもかかわらず）、実装に関係なく問題ではないと言っています。

これらのマイクロ最適化は、私の意見ではほとんど必要ありません。

Answer 6

私はJoel on Softwareからswitch() vs. lookup table?を読むことをお勧めします。特に、この応答は興味深いです：

「少なくとも 重要な事を最適化しようと時間を無駄に 人の典型的な例。」

はい、いいえ。 VMでは、通常は という小さな関数を呼び出すことがほとんどありません。 プリアンブル と各機能のクリーンアップルーチン の多くは、実行時間のかなりの割合である であることが多いコール/リターン ではありません。これは、 が、特に スレッドによって実装された人々 インタプリタによって調査されました。

仮想マシンでは、通話する計算されたアドレスを格納しているルックアップテーブルが通常スイッチよりも優先されます。 （ダイレクト・スレッディング、つまり「値としてのラベル」はルックアップ・テーブルに格納されているラベル・アドレスを直接呼び出す）特定の条件下で、長いパイプラインのCPUで非常に高価なbranch mispredictionを減らすことができるからですパイプライン）。しかし、コードの可搬性が低下します。

この問題は、VMコミュニティで広範に議論されています。詳しくは、この分野の学術論文を探すことをお勧めします。エルトル&グレッグは、2001年にこのトピックに関する素晴らしい記事を書いた

でも述べたように、私はこれらの詳細はあなたコードに関連していないことをかなり確信してThe Behavior of Efficient Virtual Machine Interpreters on Modern Architectures。これらは細部の細部なので、あまり重視しないでください。 Pythonインタプリタはスイッチを使用しています。なぜなら、コードを読みやすくするためだと思うからです。あなたが最も快適な使い方を選んでみませんか？それが重要な場合は、ハッシュテーブルを使用しては常には、ルックアップテーブルよりも遅くなります。）

編集、パフォーマンスへの影響は、あなたがより良い今のコードの読みやすさに焦点を当てたいという小さいであろう。ルックアップテーブルでは、 "キー"にenumタイプを使用し、間接ジャンプを使用して値を取得します。これは単一のアセンブリ操作です。 O（1）。ハッシュテーブルのルックアップでは、最初にハッシュを計算してから値を取得する必要がありますが、これはコストがかかります。

機能アドレスが格納され、列挙型の値を使用してアクセスされる配列を使用すると便利です。しかし、同じことを行うために、ハッシュテーブルを使用して

をまとめることが重要オーバーヘッドを追加し、我々は持っている：

• コスト（Hash_table）>>〜=コスト（direct_lookup_table）
• コスト（direct_lookup_table）コストコンパイラがスイッチをルックアップテーブルに変換する場合は、スイッチ（スイッチ）を使用します。
• あなたのコンパイラがスイッチを変換せずに条件文を使用していない場合は、コスト（direct_lookup_table）（O（N）対O（1））ですが、これを行うコンパイラは考えられません。
• しかし、インライン直接スレッドでは、コードが読みにくくなります。