次のようなコードがあるとします。
private static int DoSwitch(string arg)
{
switch (arg)
{
case "a": return 0;
case "b": return 1;
case "c": return 2;
case "d": return 3;
}
return -1;
}
private static Dictionary<string, Func<int>> dict = new Dictionary<string, Func<int>>
{
{"a", () => 0 },
{"b", () => 1 },
{"c", () => 2 },
{"d", () => 3 },
};
private static int DoDictionary(string arg)
{
return dict[arg]();
}
両方の方法を反復して比較すると、「a」、「b」、「c」、「d」が拡張されてより多くのキーが含まれる場合でも、辞書がわずかに高速化されることがわかります。なぜそうなるのでしょうか?
これは循環的複雑性と関係があるのでしょうか？ジッターが辞書内の戻り文をネイティブコードに一度だけコンパイルするからでしょうか？辞書の検索がO(1)であるためでしょうか？switch文の場合はそうではないかもしれない? (あくまで推測です)
ベストアンサー1
簡単に答えると、switch ステートメントは線形に実行されますが、辞書は対数的に実行されます。
IL レベルでは、小さな switch ステートメントは通常、切り替えられた変数と各ケースの等価性を比較する一連の if-elseif ステートメントとして実装されます。したがって、このステートメントは、myVar の有効なオプションの数に比例した時間で実行されます。ケースは出現順に比較され、最悪のシナリオでは、すべての比較が試行され、最後のケースが一致するか、どれも一致しないかのいずれかになります。したがって、32 個のオプションがある場合、最悪のシナリオではどれも一致せず、コードはこれを判断するために 32 回の比較を行うことになります。
一方、Dictionary は、インデックスが最適化されたコレクションを使用して値を格納します。.NET では、Dictionary はハッシュテーブルに基づいており、実質的にアクセス時間が一定です (欠点はスペース効率が非常に悪いことです)。Dictionary などのコレクションを「マッピング」するためによく使用されるその他のオプションには、赤黒木などのバランスのとれたツリー構造があり、対数アクセス (および線形スペース効率) を提供します。これらのいずれかを使用すると、コードは、コレクション内の適切な「ケース」に対応するキーを (またはキーが存在しないことを判断して) 見つけることができ、switch ステートメントで同じことを行うよりもはるかに高速になります。
編集: 他の回答やコメント投稿者がこれについて触れているので、完全性のために私も触れます。Microsoftコンパイラはない最初に推測したように、常に switch を if/elseif にコンパイルします。通常、少数のケースや「スパース」ケース (1、200、4000 などの非増分値) でコンパイルされます。隣接するケースのセットが大きい場合、コンパイラは CIL ステートメントを使用して switch を「ジャンプ テーブル」に変換します。スパース ケースのセットが大きい場合、コンパイラはバイナリ検索を実装してフィールドを絞り込み、少数のスパース ケースを「通過」するか、隣接するケースのジャンプ テーブルを実装できます。
ただし、コンパイラは通常、パフォーマンスとスペース効率の最も妥協した実装を選択するため、密集したケースが多数ある場合にのみジャンプ テーブルを使用します。これは、ジャンプ テーブルがカバーする必要があるケースの範囲と同程度のメモリ領域を必要とするためです。これは、疎なケースではメモリの面で非常に非効率的です。ソース コードで Dictionary を使用すると、基本的にコンパイラに強制することになります。つまり、パフォーマンスを犠牲にしてメモリ効率を上げるのではなく、コンパイラがユーザーのやり方で処理するようになります。
したがって、ソース内で switch ステートメントまたは Dictionary のいずれかを使用できるほとんどのケースでは、Dictionary を使用するとパフォーマンスが向上すると予想されます。 switch ステートメント内の case の数が多いと、保守性が低下するため、いずれにしても避ける必要があります。