for/whileループとforeachループのパフォーマンスリストの表示<T>

Question

forとforeachループのパフォーマンスについては多くの投稿とIEnumerableが一般的です。残念ながら、ほとんどの場合、foreachループに関連するオーバーヘッドが処理されており、リンクされたリストのパフォーマンスについては何もわかりません（List<T>）。

---

簡単にするために、私は2つの前提として質問を提示し、正しいかどうか質問します。

私は次のコードを実行すると仮定1

：

List<Foo> list = new List<Foo>(); 

//(list is filled here) 

foreach (Foo f in list) 
{ 
    f.baz(); 
} 

ループの反復は次のように実行しようとしている。

0：あなたは0コールをノードへのポインタを持っていますノード0のアイテムのbaz()。ノード0

1後ノードへのポインタを移動します：あなたは、ノード1の項目には1.通話baz()をノードへのポインタを持っています。ノード1

2後ノードへのポインタを移動します：あなたは、ノード2の項目に2.コールbaz()をノードへのポインタを持っています。 ...ノード2

後のノードに

nはポインタを移動：あなたはn個のノードへのポインタを持っています。ノードnの項目のbaz()に電話してください。ノードnの後のノードにポインタを移動します。

つまり、上記のコードは複雑さがO（n）です。

仮定2

私は次のコードを実行します。

List<Foo> list = new List<Foo>(); 

//(list is filled here) 

for (int i = 0; i < list.Count; i++) 
{ 
    list[i].baz(); 
} 

または以下のコード：

List<Foo> list = new List<Foo>(); 

//(list is filled here) 

int i = 0; 
while (i < list.Count) 
{ 
    list[i].baz(); 
    i++; 
} 

ループの反復は次のように実行しようとしている。

を

0：01へのポインタがあります。ノード0へのポインタをlistから取得します。ノード0の項目でbaz()と呼び出してください。

1：あなたがlistへのポインタを持っています。ノード0へのポインタをlistから取得します。ノード0の後にノードへのポインタを移動します。ノード1のアイテムのbaz()を呼び出します。

2：あなたはlistへのポインタを持っています。ノード0へのポインタをlistから取得します。ノード0の後のノードへのポインタの移動ノード1の後のノードへのポインタの移動ノード2のアイテムのbaz()を呼び出します。

...

N：あなたはlistへのポインタを持っています。ノード0へのポインタをlistから取得します。ノード0の後にノードへポインタを移動する。ノード1の後にノードへポインタを移動する。ノード2の後にノードへポインタを移動する。[...]ノード（n-2）の後のノードへのポインタを移動する。ノード（n-1）の後にノードへポインタを移動する。ノードnの項目のbaz()に電話してください。

つまり、上記のコードでは、O（n ）の複雑さがあります。

---

私の前提は正しいですか？

Answer 1

いいえ、あなたの前提は正しくありません。 List<T>データ型は、リンクされたリストではなく配列によってサポートされています。ロジックは

です。リストする項目があります。内部配列を取得し、直接0番目のインデックスにジャンプします。ノード0の項目で baz（）を呼び出します。

1：リストすることがあります。内部配列を取得し、最初のインデックスのオフセットに直接ジャンプします。ノード1の項目で baz（）を呼び出します。

2：あなたにはリストがあります。内部配列を取得し、2番目のインデックスのオフセットに直接ジャンプします。ノード2の項目で baz（）を呼び出します。

...

n：リストすることがあります。内部配列を取得し、n番目のインデックスのオフセットに直接ジャンプします。ノードnの項目で baz（）を呼び出します。あなたの場合は正しいだろうLinkedList<T>あなたの説明で作業場所

しかしLinkedList<T>ので、あなたのコード例がありませんように取得するために、インデックスを渡すことができないだろうインデクサプロパティ[i]を持っていません。