Quel est le modèle/algorithme le plus efficace pour comparer deux listes et trouver le delta entre ces deux listes?

Question

Nous avons deux listes, disons les étudiants et leurs scores. Je veux comparer ces deux listes et trouver le delta entre la nouvelle liste et l'ancienne liste, puis trouver le moyen le moins intrusif d'insérer ou de mettre à jour dans la nouvelle liste les changements. Quel est le meilleur algorithme pour aborder cela? Vous voulez vous concentrer sur le nombre minimal de modifications apportées à la nouvelle liste et à la performance.

code Exemple:

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: Débit désiré ***

La sortie souhaitée est réellement changer la newList avec les deltas. Par exemple, dans ce scénario:

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 tombe cette liste avec son score de 70, puisque je veux seulement le top 10.

Ainsi, les changements seraient:

Mise à jour fiche 2 pour "Steve", le score a changé Insérer nouveau record "Roger" à la position 9 enregistrement drop pour "Peter" hors du top 10.

Answer 1

Peut-on utiliser LINQ:

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

Votre exemple spécifique:

var diff = newList.Except(existingList); 

Je ne sais pas si elle est la plus efficace, mais il est concis :)

Answer 2

Si vous êtes à la recherche d'une solution générale, la langue agnostique, vous recherchez une sorte de data synchronization des listes ordonnées. L'algorithme de base serait:

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

Cela devrait être en mesure de faire l'affaire si vous n'avez pas le même nom deux fois dans votre liste. Dans votre exemple, vous avez 2x Steve, mais vous avez besoin d'un moyen de distinguer entre eux.

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

Vous pouvez l'appeler comme ceci:

newList = CompareLists(existingList, newList);