13 
var dict = new Dictionary<int, string>();
for (int i = 0; i < 200000; i++)
    dict[i] = "test " + i;

以下のコードを使用して、この辞書を反復処理しました。

foreach (var pair in dict)
    Console.WriteLine(pair.Value);

次に、これを使用して繰り返しました：

foreach (var key in dict.Keys)
    Console.WriteLine(dict[key]);

そして、2 回目の反復は 3 秒ほど短縮されました。両方の方法でキーと値の両方を取得できます。私が疑問に思っているのは、2 番目のアプローチに欠点があるかどうかです。これについて私が見つけることができる最も評価の高い質問には、辞書を反復するこの方法が含まれていないため、誰もそれを使用しない理由と、どのように高速に動作するかを知りたいと思いました.

4

1 に答える 1

23

あなたの時間テストにはいくつかの根本的な欠陥があります:

  • Console.Writeline は I/O 操作であり、メモリ アクセスや CPU 計算よりも桁違いに時間がかかります。反復時間の違いは、おそらくこの操作のコストによって小さくなっています。これは、鋳鉄製のストーブで 1 セント硬貨の重さを測るようなものです。
  • 全体的な操作にかかった時間については言及していないため、ある操作が別の操作よりも 3 秒短かったと言っても意味がありません。最初の実行に 300 秒、2 番目の実行に 303 秒かかった場合は、マイクロ最適化を行っています。
  • 実行時間をどのように測定したかについては言及していません。実行時間には、プログラム アセンブリをロードしてブートストラップする時間が含まれていましたか?
  • 再現性については言及していません。これらの操作を数回実行しましたか? 数百回？順不同で？

これが私のテストです。for反復の方法だけが変更されるように最善を尽くしていることに注意してください。また、ループと代入だけでどれだけの時間が費やされているかを確認するためのコントロールを含めています。

void Main()
{
    // Insert code here to set up your test: anything that you don't want to include as
    // part of the timed tests.
    var dict = new Dictionary<int, string>();
    for (int i = 0; i < 2000; i++)
        dict[i] = "test " + i;
    string s = null;
    var actions = new[]
    {
        new TimedAction("control", () => 
        {
    for (int i = 0; i < 2000; i++)
            s = "hi";
        }),
        new TimedAction("first", () => 
        {
            foreach (var pair in dict)
            s = pair.Value;
        }),
        new TimedAction("second", () => 
        {
            foreach (var key in dict.Keys)
            s = dict[key];
        })
    };
    TimeActions(100, // change this number as desired.
        actions);
}


#region timer helper methods
// Define other methods and classes here
public void TimeActions(int iterations, params TimedAction[] actions)
{
    Stopwatch s = new Stopwatch();
    foreach(var action in actions)
    {
        var milliseconds = s.Time(action.Action, iterations);
        Console.WriteLine("{0}: {1}ms ", action.Message, milliseconds);
    }

}

public class TimedAction
{
    public TimedAction(string message, Action action)
    {
        Message = message;
        Action = action;
    }
    public string Message {get;private set;}
    public Action Action {get;private set;}
}

public static class StopwatchExtensions
{
    public static double Time(this Stopwatch sw, Action action, int iterations)
    {
        sw.Restart(); 
        for (int i = 0; i < iterations; i++)
        {
            action();
        }
        sw.Stop();

        return sw.Elapsed.TotalMilliseconds;
    }
}
#endregion

結果

制御: 1.2173ms
1 回目: 9.0233ms
2 回目: 18.1301ms

したがって、これらのテストでは、インデクサーを使用すると、キーと値のペアを反復するのに約 2 倍の時間がかかります。エントリの数と繰り返しの数を 1 桁増やしても、これはほぼ比例したままであり、2 つのテストを逆の順序で実行しても同じ結果が得られます。

* なぜこの結果が期待できるのですか? Dictionary クラスはおそらくそのエントリを内部で KeyValuePairs として表しているため、直接反復するときに実際に行う必要があるのは、データ構造を 1 回調べて、呼び出し元に各エントリを渡すことだけです。Keys だけを反復する場合でも、各 KeyValuePair を見つけて、Keyそのため、ステップだけで、最初にそれを反復するのとほぼ同じ量のコストがかかります。次に、提供されたキーのハッシュを計算し、正しいハッシュテーブル バケットにジャンプし、そこで見つかった KeyValuePairs のキーに対して等価性チェックを行う必要があるインデクサーを呼び出す必要があります。これらの操作はそれほど高価ではありませんが、一度 N 回実行すると、内部ハッシュテーブル構造を再度反復した場合とほぼ同じくらい高価になります。

于 2012-07-17T19:30:25.697 に答える