C에서 두 개의 정렬 된 큰 목록을 효율적으로 비교하는 방법은 무엇입니까?

Question

각 목록에 20,000 개 및 30,000 개의 개체가있는 두 개의 일반 목록이 있습니다.

class Employee 
{ 
    string name; 
    double salary; 
} 

List<Employee> newEmployeeList = List<Employee>() {....} // contains 20,000 objects 
List<Employee> oldEmployeeList = List<Employee>() {....} // contains 30,000 objects 

속도를 향상 시키면 목록을 이름순으로 정렬 할 수도 있습니다.

내가 그의 이름과 이름

직원을 일치 급여 일치되어 있지만 급여

1. 직원을 찾으려면 다음 두 목록을 비교하려면 비교하는 가장 빠른 방법은 무엇

위의 조건과 같은 큰 데이터 목록?

Answer 1

-O(n*log(n))에 의해 newEmployeeList과 oldEmployeeList 목록을 모두 정렬합니다. 그런 다음 선형 알고리즘을 사용하여 일치 항목을 검색 할 수 있습니다. 따라서 두 목록이 거의 같은 크기 인 경우 합계는 O(n+n*log(n))입니다. 이것은 O(n^2) "brute force"알고리즘보다 빠릅니다. 가장 빠른 솔루션

Answer 2

한는 에 목록이 다른 목록에서 항목을 찾기 위해 BinarySearch의 사용이다 분류.

그러나 다른 사람을 mantioned으로 성능이 종종 주관적인 일이 될 경향이있다, 당신은, 당신의 프로젝트 요구 사항에 대해 그것을 측정해야한다.

Answer 3

당신이 다른 통해 루프에서 값을 찾고 있다면 당신은 O (1) 조회 및 O에 가까운 (n)의 행동 가까이 줄 것

var lookupDictionary = list1.ToDictionary(x=>x.name); 

를 사용하여 사전을 만들 수 있습니다 명부.

(나는 ToDictionary가 O 정직하고 구현 나을 (N)이라고 여기 있으리라 믿고있어,하지만 난 경우가이 테스트를하지 않은 경우)이 매우 똑 바른 앞으로를 위해 만들 것

알고리즘을 사용하고, 두 개의 정렬되지 않은 목록으로 O (n) 아래로가는 것이 꽤 어렵다고 생각합니다.

Answer 4

두 개의 목록은 이름을 기준으로 Dictionary<string, Employee>에 저장하는 것이 좋을 것입니다. 그런 다음 하나의 키를 반복하고 조회하여 다른 것이 있는지 확인하십시오. 이렇게하면 나중에 정렬하거나보다 효율적인 구조를 유지하는 데 드는 비용을 절약 할 수 있습니다.

두 사전을 모두 작성하는 선형 (O (n)) - 선형을 사용하여 키를 통과하고 다른 부분을 조회합니다. O는 (N + m + N) (N) O

그러나을로 줄일 수 있기 때문에 당신이 다른 이유에 대한 목록을 보유 List<T>를 사용해야하는 경우, 당신은 또한 Join() LINQ 방법을 사용하고, 새 목록을 만들 수 Match 필드는 일치 또는 불일치 여부를 알려줍니다.

 var results = newEmpList.Join(
      oldEmpList, 
      n => n.Name, 
      o => o.Name, 
      (n, o) => new 
       { 
        Name = n.Name, 
        Salary = n.Salary, 
        Match = o.Salary == n.Salary 
       }); 

그런 다음 Match 또는 !Match에 대한 Where() 절을이를 필터링 할 수 있습니다.

Answer 5

업데이트 : (귀하의 질문 제목으로) 2 목록이 이미 정렬되어 있다고 가정합니다. 아마도 클러스터 된 인덱스가있는 데이터베이스에 저장되어있을 것입니다. 따라서이 대답은 그 가정에 의존합니다.

여기는 O(n) 복잡도를 갖는 구현이며 매우 빠르며 매우 간단합니다.
이 변형은 Merge Algorithm입니다.

는 여기에 아이디어 :

는 2 개 현재 항목을 비교하여 두 목록을 열거

1. 시작.
2. 일치하는 항목이 있으면 결과에 추가하십시오.
   첫 번째 항목이 "더 작 으면"첫 번째 목록을 올리십시오.
   두 번째 항목이 "작음"인 경우 두 번째 목록을 올리십시오.

두 목록 모두 정렬로 알려져 있기 때문에 매우 잘 작동합니다. 이 구현에서는 name이 각 목록에서 고유하다고 가정합니다.

var comparer = StringComparer.OrdinalIgnoreCase; 
var namesAndSalaries = new List<Tuple<Employee, Employee>>(); 
var namesOnly = new List<Tuple<Employee, Employee>>(); 

// Create 2 iterators; one for old, one for new: 
using (IEnumerator<Employee> A = oldEmployeeList.GetEnumerator()) { 
    using (IEnumerator<Employee> B = newEmployeeList.GetEnumerator()) { 
     // Start enumerating both: 
     if (A.MoveNext() && B.MoveNext()) { 
      while (true) { 
       int compared = comparer.Compare(A.Current.name, B.Current.name); 
       if (compared == 0) { 
        // Names match 
        if (A.Current.salary == B.Current.salary) { 
         namesAndSalaries.Add(Tuple.Create(A.Current, B.Current)); 
        } else { 
         namesOnly.Add(Tuple.Create(A.Current, B.Current)); 
        } 
        if (!A.MoveNext() || !B.MoveNext()) break; 
       } else if (compared == -1) { 
        // Keep searching A 
        if (!A.MoveNext()) break; 
       } else { 
        // Keep searching B 
        if (!B.MoveNext()) break; 
       } 

      } 
     } 
    } 
}