Каков наиболее эффективный шаблон/алгоритм для сравнения двух списков и найти дельта между этими двумя списками?

У нас есть два списка, скажем, студенты и их оценки. Я хочу сравнить эти два списка и найти дельту между новым списком и старым списком, а затем найти наименее интрузивный способ вставки или обновления в новый список любых изменений. Какой лучший алгоритм подходит к этому? Хотите сосредоточиться на минимальном количестве изменений в новом списке и производительности.

Пример кода:

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

//Питер уходит из этого списка с его счетом 70, так как я хочу только 10 лучших.

Таким образом, изменения будут следующими:

Обновить запись 2 для "Стива", счет изменился Вставить новую запись "Роджер" в позицию 9 Снимите запись для "Питера" из лучших 10.

Ответ 1

Можно ли использовать Linq:

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

Ваш конкретный пример:

var diff = newList.Except(existingList);

Не уверен, что это самый эффективный, но он краткий:)

Ответ 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

Ответ 3

Это должно быть в состоянии сделать трюк, если вы не имеете то же имя дважды в своем списке. В вашем примере у вас есть 2x Steve, но вам нужен способ различать между ними.

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

Вы можете называть это следующим образом:

newList = CompareLists(existingList, newList);