SortedList の循環 - なぜこれが速いのでしょうか?

Question

次の例の List1 は SortedList(Of MyClass) であり、251 のメンバーが含まれています。

最初の 2 つのコードブロックは 15.5 秒で実行されます。

 For cnt As Integer = 1 To 1000000
        For Each TempDE In List1
            Dim F As String = TempDE.Key
            TempDE.Value.x1 = 444
        Next
    Next

 

    For cnt As Integer = 1 To 1000000
        For Each TempDE As KeyValuePair(Of String, phatob) In List2
            Dim F As String = TempDE.Key
            TempDE.Value.x1 = 444
        Next
    Next

これは 5.6 秒で実行されます。

    For cnt As Integer = 0 To 999999
        For cnt2 As Integer = 0 To 250
            Dim F As String = List1.Keys(cnt2)
            List1.Values(cnt2).x1 = 444
        Next

    Next

最初の 2 つのコードブロックが非常に遅いのはなぜですか?

Answer 1

SortedList は、並べ替え機能を提供する IComparer を実装することによって Collection を拡張します。内部的には、リストの要素を格納するために 2 つの配列 (キー用の配列と値用の配列) を実装します。.NET 配列は、高速な順序アクセスと高速なランダム アクセス向けに最適化されています。

最初の 2 つが遅い理由は、SortedList の foreach ステートメントが Enumerator のラッパーであるためではないかと考えています。foreach を呼び出すと列挙子がクエリされ、MoveNext と Current が呼び出されます。さらに、汎用リストを参照すると、リストを横断する際にボックス化とボックス化解除が行われる可能性があり、インデックスによるアクセスでは通常発生しないようなパフォーマンスのオーバーヘッドが発生する可能性があります。

Answer 2

正確な方法についてのドキュメントを探してみました For Each 動作しますが、見つかりませんでした。

私の理論では、 For Each ステートメントは、リスト内のオブジェクトをメモリ内の別の場所にコピーし、ループの各反復が終了するときにそれをリストにコピーして戻します。

もう 1 つの可能性は、各反復の開始時にコンストラクターを呼び出し、その後分解してコンストラクターを再度呼び出して、次の反復でリセットすることです。

どちらの理論についてもよくわかりませんが、3 と (1 または 2) の大きな違いは、 For Each.

編集：次の場所にドキュメントが見つかりました MSDN.

以下にその抜粋を示します。

For Each...Next ループの実行が開始されると、Visual Basic はグループが有効なコレクション オブジェクトを参照しているかどうかを確認します。そうでない場合は、例外がスローされます。それ以外の場合は、MoveNext メソッドと列挙子オブジェクトの Current プロパティを呼び出して、最初の要素を返します。MoveNext が次の要素がないことを示している場合、つまりコレクションが空の場合、For Each ループは終了し、制御は Next ステートメントに続くステートメントに渡されます。それ以外の場合、Visual Basic は要素を最初の要素に設定し、ステートメント ブロックを実行します。

全体的には次のようになります For Each より「管理」されており、すべてが一致していることを確認するために多くのオーバーヘッドが発生します。その結果、速度が遅くなります。

Answer 3

ループ範囲が固定されているため、コンパイラはブロック 3 をより適切に最適化できると思います。ブロック 1 と 2 では、コンパイラーはリストを評価するまでループの上限がわからないため、処理が遅くなります。

Answer 4

私の勝手な推測：List1 には、最大 750 個の要素が含まれています (250 個だけではありません)。3 番目のケースは、List1 が持つ各要素を反復処理しないため、より高速です。