Làm thế nào để so sánh hai danh sách lớn được sắp xếp một cách hiệu quả trong C#?

Question

Tôi có hai danh sách chung với 20.000 và 30.000 đối tượng trong mỗi danh sách.

class Employee 
{ 
    string name; 
    double salary; 
} 

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

Danh sách cũng có thể được sắp xếp theo tên nếu nó cải thiện tốc độ.

tôi muốn so sánh hai danh sách này để tìm hiểu

1. nhân viên mà tên tuổi và mức lương phù hợp với
2. nhân viên có tên phù hợp nhưng không lương

là gì cách nhanh nhất để so sánh danh sách dữ liệu lớn như vậy với các điều kiện trên?

Answer 1

Tôi sẽ sắp xếp cả hai danh sách newEmployeeList và oldEmployeeList theo name - O(n*log(n)). Và sau đó bạn có thể sử dụng thuật toán tuyến tính để tìm kiếm các kết quả phù hợp. Vì vậy, tổng số sẽ là O(n+n*log(n)) nếu cả hai danh sách có cùng kích thước. Điều này sẽ nhanh hơn thuật toán "brute force" của O(n^2).

Answer 2

Một của giải pháp khả thi nhanh nhất trên sắp xếp danh sách là sử dụng BinarySearch để tìm một mục trong danh sách khác.

Nhưng khi mantioned người khác, bạn nên đánh nó chống lại yêu cầu dự án của bạn, như hiệu suất thường có xu hướng trở thành một chủ điều.

Answer 3

Bạn có thể tạo ra một từ điển sử dụng

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

Điều đó sẽ cung cấp cho bạn gần với O (1) tra cứu và gần O (n) hành vi nếu bạn đang tìm kiếm các giá trị từ một vòng lặp trong khác danh sách.

(Tôi giả định ở đây rằng ToDictionary là O (n) trong đó sẽ có ý nghĩa với một thực hiện thẳng về phía trước, nhưng tôi đã không kiểm tra này là trường hợp)

Điều này sẽ làm cho một rất thẳng về phía trước thuật toán, và tôi đang suy nghĩ đi dưới O (n) với hai danh sách chưa phân loại là khá khó.

Answer 4

Tôi có thể đề nghị hai danh sách được lưu trữ trong một tên Dictionary<string, Employee> dựa trên tên để bắt đầu, sau đó bạn có thể lặp qua các khóa trong một và tra cứu để xem chúng tồn tại và tiền lương khớp với nhau. Điều này cũng sẽ tiết kiệm chi phí phân loại chúng sau này hoặc đưa chúng vào một cấu trúc hiệu quả hơn.

Điều này là khá nhiều O (n) - tuyến tính để xây dựng cả hai từ điển, tuyến tính để đi qua các phím và tra cứu trong khác. Kể từ O (n + m + n) giảm đến O (n)

Nhưng, nếu bạn phải sử dụng List<T> để giữ danh sách các lý do khác, bạn cũng có thể sử dụng phương pháp Join() LINQ, và xây dựng một danh sách mới với trường Match cho bạn biết chúng có khớp hay không khớp ...

 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 
       }); 

Sau đó bạn có thể lọc này với một khoản Where() cho Match hoặc !Match.

Answer 5

Cập nhật: Tôi giả định (bằng tiêu đề câu hỏi của bạn) rằng 2 danh sách đã được sắp xếp. Có lẽ chúng được lưu trữ trong một cơ sở dữ liệu với một chỉ số nhóm hoặc một cái gì đó. Câu trả lời này, do đó, dựa trên giả định đó.

Dưới đây là triển khai có độ phức tạp O(n) và cũng rất nhanh, VÀ cũng khá đơn giản.
Tôi tin rằng đây là một biến thể của Merge Algorithm.

Dưới đây là ý tưởng:

1. Bắt đầu liệt kê cả hai danh sách
2. Hãy so sánh 2 mặt hàng hiện hành.
3. Nếu chúng khớp nhau, hãy thêm vào kết quả của bạn.
   Nếu mục thứ nhất là "nhỏ hơn", hãy chuyển danh sách thứ nhất.
   Nếu mục thứ 2 là "nhỏ hơn", hãy thăng tiến danh sách thứ 2.

Vì cả hai danh sách đều được sắp xếp để sắp xếp, điều này sẽ hoạt động rất tốt. Triển khai này giả định rằng name là duy nhất trong mỗi danh sách.

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; 
       } 

      } 
     } 
    } 
}