c# - 比较两个列表并找到这两个列表之间的增量的最有效模式/算法是什么？

Question

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

示例代码:

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

** 编辑:期望的输出 ***

所需的输出是实际更改带有增量的 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

//Peter 以 70 分的成绩退出了这个列表，因为我只想要前 10 名。

所以变化是:

为“史蒂夫”更新记录2，分数有变化在第 9 位插入新记录“Roger”将“Peter”的记录从前 10 名中删除。

Answer 1

如果您正在寻找通用的、与语言无关的解决方案，那么您正在寻找某种 data synchronization有序列表。基本算法是:

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