比较两个列表并找到这两个列表之间的差异的最有效模式/算法是什么？

我们有两个列表，让我们说学生和他们的分数。 我想比较这两个列表并找到新列表和旧列表之间的增量，然后找到插入或更新到新列表中的任何更改的最不具侵入性的方法。 解决这个问题的最佳算法是什么？ 希望专注于对新列表和性能的最小量更改。

示例代码：

List existingList = new List(); List newList = new List(); 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; } } 

**编辑：所需输出***

所需的输出是实际更改带有增量的newList。 例如，在这种情况下：

 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 

//彼得以70分的成绩从这份名单中脱颖而出，因为我只想要前10名。

所以变化将是：

更新“Steve”的记录2，得分已更改在第9位插入新记录“Roger”将“Peter”的记录从前10名中删除。

Answer 1

你能用Linq：

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

你的具体例子：

 var diff = newList.Except(existingList); 

不确定它是否最有效但它简洁:)

Answer 2

如果您正在寻找一种通用的，与语言无关的解决方案，那么您正在寻找有序列表的某种数据同步 。 基本算法是：

 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

如果您的列表中没有两次相同的名称，这应该可以解决问题。 在您的示例中，您有2x Steve，但您需要一种方法来区分它们。

 public static List CompareLists(List existingList, List newList) { List mergedList = new List(); mergedList.AddRange(newList); mergedList.AddRange(existingList.Except(newList, new ListItemComparer())); return mergedList.OrderByDescending(x => x.Score).Take(10).ToList(); } public class ListItemComparer : IEqualityComparer { public bool Equals(ListItem x, ListItem y) { return x.Name == y.Name; } public int GetHashCode(ListItem obj) { return obj.Name.GetHashCode(); } } 

你可以这样称呼它：

 newList = CompareLists(existingList, newList);