switch case と std::map はどちらが効率的ですか

StackOverflow https://stackoverflow.com/questions/931890

  •  06-09-2019
  •  | 
  •  

質問

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

  • std::functions/boost::functions のマップ
  • スイッチケース
役に立ちましたか？

解決

Visual Studio 2008 に付属の STL マップでは、その下にツリー構造が隠されているため、関数呼び出しごとに O(log(n)) が得られます。最新のコンパイラ (実装に応じて) では、switch ステートメントで O(1) が得られ、コンパイラはそれをある種のルックアップ テーブルに変換します。したがって、一般に、切り替えの方が高速です。

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

マップとスイッチの違いは次のとおりです。マップは動的に構築できますが、スイッチは動的に構築できません。Map には任意の型をキーとして含めることができますが、switch は C++ のプリミティブ型 (char 、 int 、 enum など) に非常に限定されています。

ちなみに、ハッシュ マップを使用すると、ほぼ O(1) のディスパッチを実現できます (ただし、ハッシュ テーブルの実装によっては、最悪の場合 O(n) になる場合もあります)。それでも、切り替えの方が高速です。

編集

私は単なる楽しみと議論のためだけに以下を書いています

私はあなたのために素晴らしい最適化を提案することができますが、それはあなたの言語の性質と、あなたの言語がどのように使用されるかを予測できるかどうかによって異なります。

コードを記述するとき:トークンを 2 つのグループに分割します。1 つのグループは使用頻度が非常に高く、もう 1 つのグループは使用頻度が低いものになります。また、頻繁に使用されるトークンを並べ替えます。使用頻度の高いトークンの場合は、最も使用頻度の高いものを最初に持つ if-else シリーズを作成します。使用頻度が低い の場合は、switch ステートメントを作成します。

このアイデアは、別のレベルの間接化を回避するために CPU 分岐予測を使用することです (if ステートメントでの条件チェックがほとんどコストがかからないと仮定して)。ほとんどの場合、CPU は間接的なレベルをまったく使用せずに正しい分岐を選択します。ただし、支店が間違った場所に行くケースはほとんどありません。言語の性質によっては、統計的にはパフォーマンスが向上する可能性があります。

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

他のヒント

読むことをお勧めします switch() とルックアップテーブル？ ソフトウェアに関するジョエルより。特に、この応答は興味深いです。

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

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

仮想マシンでは、通常、呼び出すために計算されたアドレスを格納するルックアップ テーブルがスイッチよりも優先されます。(直接スレッド、または「値としてラベルを付ける」。ルックアップ テーブルに格納されているラベル アドレスを直接呼び出します)。これは、特定の条件下で、 分岐の予測ミス, これは、長いパイプラインの CPU では非常に高価です (パイプラインのフラッシュが強制されます)。ただし、コードの移植性が低くなります。

この問題は VM コミュニティで広く議論されています。さらに詳しく読みたい場合は、この分野の学者の論文を探すことをお勧めします。Ertl と Gregg は 2001 年にこのトピックに関する素晴らしい記事を書きました。 の振る舞い 効率的 最新のアーキテクチャにおける仮想マシン インタプリタ

しかし、前述したように、これらの詳細は、 あなたの コード。これらは細かいことなので、あまり重視しないでください。Python インタープリターはスイッチを使用しています。これは、スイッチを使用するとコードが読みやすくなると考えているためです。自分の使いやすい使い方を選んでみてはいかがでしょうか？パフォーマンスへの影響はかなり小さいため、今はコードの読みやすさに重点を置いた方がよいでしょう ;)

編集:重要な場合は、ハッシュ テーブルを使用すると、 いつも ルックアップテーブルよりも遅くなります。ルックアップ テーブルの場合、「キー」に列挙型を使用し、単一の間接ジャンプを使用して値を取得します。これは 1 回の組み立て操作です。○(1)。ハッシュ テーブルの検索では、まずハッシュを計算し、次に値を取得する必要がありますが、これは非常にコストがかかります。

関数アドレスが格納され、列挙型の値を使用してアクセスされる配列を使用するのが適切です。ただし、ハッシュ テーブルを使用して同じことを行うと、重要なオーバーヘッドが追加されます

要約すると、次のようになります。

  • コスト(ハッシュテーブル) >> コスト(ダイレクトルックアップテーブル)
  • コンパイラがスイッチをルックアップ テーブルに変換する場合、cost(direct_lookup_table) ~=cost(switch)。
  • コンパイラがスイッチを変換せず、条件文を使用しない場合は、cost(switch) >>cost(direct_lookup_table) (O(N) vs O(1)) ですが、これを行うコンパイラは思いつきません。
  • ただし、インライン ダイレクト スレッドを使用すると、コードが読みにくくなります。

「効率的」のあなたの定義は何ですか？あなたがより速く意味ならば、あなたはおそらく明確な答えのためのいくつかのテストコードをプロファイリングする必要があります。あなたがが柔軟かつ容易に拡張するコードを後にしている場合は、自分を支持を行うと、マップのアプローチを使用します。他のすべては、ちょうど時期尚早最適化です...

yossi1981は言っ

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

あなたの値は以下のルールを満たしている必要があり、高速スイッチを得るために： 彼らは連続である必要があり、それは例えばあります0,1,2,3,4。あなたは、いくつかの値を除外することができますが、0,1,2,34,43のようなものを最適化することが極めて低いです。

質問は本当にです：あなたのアプリケーションでこのような意義の性能はありますか？ そして、ファイルから動的に値をロードマップではなく、コードの複数のページにまたがる巨大な文の読みやすくかつ保守のではないでしょうか？

あなたは、あなたのトークンがあるタイプ何を言っていません。彼らが整数でない場合は、選択肢を持っていない - のスイッチは整数型で動作します。

C ++標準では、機能があるはずだけで、その要件のパフォーマンスについては何も言いません。

に関する質問のこれらのソート順は、より良いまたはより高速またはより効率的に無意味である、あなたはをどの状態がない限り実装のあなたは話をしています。たとえば、JavaScriptの特定の実装の特定のバージョンで扱う文字列が凶悪だったが、あなたは、関連する標準の機能であることにそれを推定することはできません。

私もswitchとstd::mapによって提供される機能が異なるため（重複ありますが）、それは実装にかかわらず、問題ではないと言うようにこれまで行くだろう。

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top