Mẫu/thuật toán hiệu quả nhất để so sánh hai danh sách và tìm đồng bằng giữa hai danh sách đó là gì?

Question

Chúng tôi có hai danh sách, giả sử sinh viên và điểm số của họ. Tôi muốn so sánh hai danh sách này và tìm đồng bằng giữa danh sách mới và danh sách cũ, sau đó tìm cách xâm nhập ít nhất để Chèn hoặc Cập nhật vào danh sách mới bất kỳ thay đổi nào. Thuật toán tốt nhất để tiếp cận điều này là gì? Bạn muốn tập trung vào số lượng thay đổi tối thiểu đối với danh sách và hiệu suất mới.

Ví dụ mã:

List<ListItem> existingList = new List<ListItem>(); 
List<ListItem> newList = new List<ListItem>(); 

public TopLists() 
{ 
    InitTwoLists(); 
} 

private void InitTwoLists() 
{ 
    existingList.Add(new ListItem { Name = "Shane", Score = 100 }); 
    existingList.Add(new ListItem { Name = "Mark", Score = 95 }); 
    existingList.Add(new ListItem { Name = "Shane", Score = 94 }); 
    existingList.Add(new ListItem { Name = "Steve", Score = 90 }); 
    existingList.Add(new ListItem { Name = "Brian", Score = 85 }); 
    existingList.Add(new ListItem { Name = "Craig", Score = 85 }); 
    existingList.Add(new ListItem { Name = "John", Score = 82 }); 
    existingList.Add(new ListItem { Name = "Steve", Score = 81 }); 
    existingList.Add(new ListItem { Name = "Philip", Score = 79 }); 
    existingList.Add(new ListItem { Name = "Peter", Score = 70 }); 

    newList.Add(new ListItem { Name = "Shane", Score = 100 }); 
    newList.Add(new ListItem { Name = "Steve", Score = 96 }); // This is change 
    newList.Add(new ListItem { Name = "Mark", Score = 95 }); 
    newList.Add(new ListItem { Name = "Shane", Score = 94 }); 
    newList.Add(new ListItem { Name = "Brian", Score = 85 }); 
    newList.Add(new ListItem { Name = "Craig", Score = 85 }); 
    newList.Add(new ListItem { Name = "John", Score = 82 }); 
    newList.Add(new ListItem { Name = "Steve", Score = 81 }); 
    newList.Add(new ListItem { Name = "Philip", Score = 79 }); 
    newList.Add(new ListItem { Name = "Peter", Score = 70 }); 
} 
} 

public void CompareLists() 
{ 
    // How would I find the deltas and update the new list with any changes from old? 
} 
} 

public class ListItem 
{ 
    public string Name { get; set; } 
    public int Score { get; set; } 
} 

** EDIT: mong muốn Output ***

Các đầu ra mong muốn là để thực sự thay đổi newList với đồng bằng châu thổ. Ví dụ trong kịch bản này:

newList.Add(new ListItem { Name = "Shane", Score = 100 }); 
    newList.Add(new ListItem { Name = "Steve", Score = 96 }); // This is change 
    newList.Add(new ListItem { Name = "Mark", Score = 95 }); 
    newList.Add(new ListItem { Name = "Shane", Score = 94 }); 
    newList.Add(new ListItem { Name = "Brian", Score = 85 }); 
    newList.Add(new ListItem { Name = "Craig", Score = 85 }); 
    newList.Add(new ListItem { Name = "John", Score = 82 }); 
    newList.Add(new ListItem { Name = "Steve", Score = 81 }); 
    newList.Add(new ListItem { Name = "Roger", Score = 80 }); // Roger is a new entry 
    newList.Add(new ListItem { Name = "Phillip", Score = 79 }); // Philip moved down one 

// Peter rơi ra khỏi danh sách này với điểm số của mình là 70, vì tôi chỉ muốn top 10.

Vì vậy, những thay đổi sẽ là:

Cập nhật kỷ lục 2 cho "Steve", điểm số đã thay đổi Chèn bản ghi mới "Roger" tại vị trí 9 Thả bản ghi cho "Peter" ra khỏi đầu 10.

Answer 1

Bạn có thể sử dụng LINQ:

List<ListItem> list1 = GetYourList1(); 
List<ListItem> list2 = GetYourList2(); 
var diff = list1.Except(list2); 

dụ của bạn cụ thể:

var diff = newList.Except(existingList); 

Không chắc chắn nếu nó là hiệu quả nhất nhưng nó súc tích :)

Answer 2

Nếu bạn đang tìm kiếm một giải pháp chung, ngôn ngữ-agnostic, sau đó bạn đang tìm kiếm một số loại data synchronization của danh sách được sắp xếp. Thuật toán cơ bản sẽ là:

i1 = 0 
i2 = 0 
while (i1 < list1.size && i2 < list2.size) 
{ 
    if (list1[i1] < list2[i2]) 
    { 
    //list1[i1] is not in list2 
    i1++ 
    } 
    else if (list1[i1] > list2[i2]) 
    { 
    //list2[i2] is not in list1 
    i2++ 
    } 
    else 
    { 
    //item is in both lists 
    i1++ 
    i2++ 
    } 
} 
if (i1 < list1.size) 
    //all remaining list1 items are not in list2 
if (i2 < list2.size) 
    //all remaining list2 items are not in list1 

Answer 3

Điều này sẽ có thể thực hiện thủ thuật nếu bạn không có cùng tên hai lần trong danh sách của mình. Trong ví dụ của bạn, bạn có 2x Steve, nhưng bạn cần một cách để phân biệt giữa chúng.

public static List<ListItem> CompareLists(List<ListItem> existingList, List<ListItem> newList) 
{ 
    List<ListItem> mergedList = new List<ListItem>(); 
    mergedList.AddRange(newList); 
    mergedList.AddRange(existingList.Except(newList, new ListItemComparer())); 
    return mergedList.OrderByDescending(x => x.Score).Take(10).ToList(); 
} 

public class ListItemComparer : IEqualityComparer<ListItem> 
{ 
    public bool Equals(ListItem x, ListItem y) 
    { 
     return x.Name == y.Name; 
    } 

    public int GetHashCode(ListItem obj) 
    { 
     return obj.Name.GetHashCode(); 
    } 
} 

Bạn có thể gọi nó như thế này:

newList = CompareLists(existingList, newList);