Findとfindindexは厄介なリスト<Object>のために遅い？

Question

私はIntensively Listを使用するプロジェクトで作業しています。私は名前（オブジェクトのメンバー）を介してオブジェクトを見つけようとしています。

私のコードは、1つのfor-nextループ（関数find1）を使用して検索することなく機能しましたが、ビルドインのfind関数を使用して同じことが可能であることがわかりました。しかし、それは少し遅く感じる。

私は次のコード

public List<MyObject> varbig = new List<MyObject>(); 
    public Dictionary<string,string> myDictionary=new Dictionary<string, string>(); 
    public Form1() { 
     InitializeComponent(); 
    } 

    private void button1_Click(object sender, EventArgs e) { 
     myDictionary.Clear(); 
     varbig.Clear(); 

     for (int i = 0; i < 5000; i++) { 
      varbig.Add(new MyObject("name" + i.ToString(),"value"+i.ToString())); 
      myDictionary.Add("name" + i.ToString(), i.ToString()); 
     } 
     // first test 
     var start1 = Environment.TickCount; 
     for (int i = 0; i < 3000; i++) { 
      var ss=find1("name499"); 
     } 
     var end1 = Environment.TickCount; 
     Console.WriteLine("time 1 :" + (end1 - start1)); 
     // second test 
     var start2 = Environment.TickCount; 
     for (int i = 0; i < 3000; i++) { 
      var ss=find2("name499"); 
     } 
     var end2 = Environment.TickCount; 
     Console.WriteLine("time 2 :" + (end2 - start2)); 
     // third test 
     var start3 = Environment.TickCount; 
     for (int i = 0; i < 3000; i++) { 
      var ss = find3("name499"); 
     } 
     var end3 = Environment.TickCount; 
     Console.WriteLine("time 3 :" + (end3 - start3)); 

     // first test b 
     var start1b = Environment.TickCount; 
     for (int i = 0; i < 3000; i++) { 
      var ss=find1("name4999"); 
     } 
     var end1b = Environment.TickCount; 
     Console.WriteLine("timeb 1 :" + (end1b - start1b)); 
     // second test 
     var start2b = Environment.TickCount; 
     for (int i = 0; i < 3000; i++) { 
      var ss=find2("name4999"); 
     } 
     var end2b = Environment.TickCount; 
     Console.WriteLine("timeb 2 :" + (end2b - start2b)); 
     // third test 
     var start3b = Environment.TickCount; 
     for (int i = 0; i < 3000; i++) { 
      var ss = find3("name4999"); 
     } 
     var end3b = Environment.TickCount; 
     Console.WriteLine("timeb 3 :" + (end3b - start3b)); 

    } 

    public int find1(string name) { 
     for (int i = 0; i < varbig.Count; i++) { 
      if(varbig[i].Name == name) { 
       return i; 
      } 
     } 
     return -1; 
    } 

    public int find2(string name) { 
     int idx = varbig.FindIndex(tmpvar => Name == name); 
     return idx; 
    } 
    public int find3(string name) { 
     var ss=myDictionary[name]; 
     return int.Parse(ss); 
    } 
} 

を持っていると私は次のオブジェクト

public class MyObject { 
    private string _name = ""; 
    private string _value = ""; 
    public MyObject() {} 

    public MyObject(string name, string value) { 
     _name = name; 
     _value = value; 
    } 

    public string Name { 
     get { return _name; } 
     set { _name = value; } 
    } 

    public string Value { 
     get { return _value; } 
     set { _value = value; } 
    } 
} 

ほとんどが、それは次のことを行うを使用します：私は作成 だから、私はテストのためにプロジェクトの速度をしました5000要素の配列

時間1 =単純なfor-nextを使用して499番目のオブジェクト（インデックス）を検索します。

時間2 =リスト

時間3の関数findでビルドを使用して第四百九十九を検索=それは辞書を使用して第四百九十九要素の検索を行います。

Timeb 1、timeb 2、およびtimeb 3は同じことを行いますが、499番目の要素の代わりに4999番目の要素を検索してみます。

• 時間1：141
• 時間2：1248
• 時間3：0
• TIMEB 1：811
• TIMEB 2：1170
は、私は数回を走りました

• 時間b 3：0

• 時間1：109

• 時間2：1170
• 時間3：0
• TIMEB 1：796
• TIMEB 2：1170
• TIMEB 3：0

（小次いで速い）

私の驚きは、機能の組み込みfindindexは非常に遅いです（場合によっては、10倍近く遅くなります）。また、辞書のアプローチはほぼ即座に行われます。

私の質問は、なぜですか？それは述語なのか？ Find1はFind2が、あなたはそれと一緒に述語に合格したことを除いて、（上記の正確find1ある）Findメソッドに建て使用しています（I = 0カウントする）ための簡単な方法

を使用している

Answer 1

• 私はそれが減速していると信じています。
• 辞書を使用してFind3、私が引き受けるすべてのタイマーなしで最速で、辞書が0（1）（Contantを時間）を調べているカバーの下にハッシュテーブルを使用していますbecuase

Answer 2

にエラーがありますあなたのコード - find2メソッドは、コレクションオブジェクト名の代わりに比較のためにForm.Nameを使用します。問題は、このラインである

time 1 :54 
time 2 :50 
time 3 :0 
timeb 1 :438 
timeb 2 :506 
timeb 3 :0 

Answer 3

：

int idx = varbig.FindIndex(tmpvar => Name == name); 

Name == nameは間違っている、

public int find2(string name) { 
    return varbig.FindIndex((obj) => obj.Name == name); 
} 

Form.Nameを使用せずに結果がより一貫している：それはすべきで、このようになります。代わりにtmpvar.Name == nameと記述してください。

コードでは、name引数をフォームのNameプロパティと比較しています。彼らは明らかに異なっているので、検索された値が見つかったときに停止するのではなく、リスト全体を常に調べます。実際には数字を見るとわかるように、find2()が費やす時間は基本的には常に同じです。

ディクショナリについては、ディクショナリが特に高速キーアクセスを提供するように構築されたメモリ構造であるため、明らかに他の方法よりも高速です。

実際には、O(1)の複雑さに近づいていますが、リストをループするときには、複雑度はO(n)になります。