리스트 찾기에 대해 느리고 찾기가 힘들다 <Object> 왜?

Question

나는 집중적으로 List를 사용하는 프로젝트에서 작업하고 있으며 이름 (객체의 구성원)을 통해 객체를 찾으려고합니다.

내 코드는 for-next 루프 (function find1)를 사용하여 검색하지 않고도 작동했지만 동일한 find-in을 사용하여 동일한 코드를 찾을 수 있었고 코드가 작동합니다. 그러나 조금 느립니다. 내가 만들 : 나는 다음 코드

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의 기능 발견에 빌드를 사용하여 499번째 검색 =이 사전을 사용하여 4백99번째 요소의 검색을 수행.

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 : 1,170
• 시간 3 : 0
• timeb 1 : 796
• timeb 2 : 1,170
• timeb 3 : 0

(작은 그때 빨리)

놀랍게도, 기능을 빌드 findindex은 어색하게 느립니다 (경우에 따라 10 배 느리게 느림). 또한, 사전 접근 방식은 거의 즉시입니다.

내 질문은 무엇입니까? 그것은 술어 때문입니까?

Answer 1

Find1 당신이 그것을 함께 술어를 통과 한 것을 제외하고,
• Find2는 (위 정확히 find1 인) Find 메서드에 내장 된 사용 방법 (I = 0 세는)에 대한 간단한을 사용
• 하는 나는 그것이 느려지고 있다고 생각한다.사전은 0 (1) 오류가에있다

Answer 2

(CONTANT 시간)을 찾아이 내부적으로 해시 테이블을 사용 becuase

Find3 사전을 사용하여, 내가 생각할 겁니다는 어떤 타이머없이 가장 빠른 귀하의 코드 - find2 메서드는 컬렉션 개체 이름 대신 비교를 위해 Form.Name을 사용합니다. 그것은해야 다음과 같습니다 다음 Form.Name를 사용하지 않고

public int find2(string name) { 
    return varbig.FindIndex((obj) => obj.Name == 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 잘못이다, 대신 tmpvar.Name == name을 써야합니다.

코드에서 name 인수를 양식의 Name 속성과 비교합니다. 그들은 분명히 다르므로 검색된 값이 발견 될 때 중지하는 대신 전체 목록을 항상 검사합니다. 실제로 숫자를 볼 때 알 수 있듯이 find2()에 소비되는 시간은 기본적으로 항상 동일합니다.

사전에 대해서는 사전이 빠른 키 액세스를 제공하기 위해 특별히 설계된 메모리 구조이기 때문에 다른 방법보다 분명 빠릅니다.

사실 그들은 O(1) 시간 복잡도에 도달하고 목록을 반복하면 O(n)과 같은 시간 복잡도를 갖습니다.