Qual è il pattern/algoritmo più efficiente per confrontare due liste e trovare il delta tra queste due liste?

Question

Abbiamo due elenchi, diciamo gli studenti e i loro punteggi. Voglio confrontare questi due elenchi e trovare il delta tra la nuova lista e la vecchia lista, quindi trovare il modo meno intrusivo di inserire o aggiornare nel nuovo elenco eventuali modifiche. Qual è il miglior algoritmo per avvicinarsi a questo? Vuoi concentrarti sulla quantità minima di modifiche apportate alla nuova lista e al rendimento.

codice Esempio:

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: uscita desiderata ***

L'output desiderato è quello di cambiare la realtà newList con delta. Ad esempio, in questo scenario:

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 cade questa lista con il suo punteggio di 70, perché voglio solo la top 10.

Così i cambiamenti sarebbero:

Aggiornamento record di 2 per "Steve", il punteggio è cambiato Inserire un nuovo record "Roger" nella posizione 9 record di goccia per "Peter" fuori della top 10.

Answer 1

si può utilizzare Linq:

012.

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

Il tuo esempio specifico:

var diff = newList.Except(existingList); 

Non so se è il più efficiente, ma è conciso :)

Answer 2

Se siete alla ricerca di una soluzione generale, indipendente dal linguaggio, allora si Sto cercando una specie di data synchronization di liste ordinate. L'algoritmo di base sarebbe:

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

questo dovrebbe essere in grado di fare il trucco se non si ha lo stesso nome due volte nella vostra lista. Nel tuo esempio, hai 2x Steve, ma hai bisogno di un modo per distinguerli.

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

Si può chiamare in questo modo:

newList = CompareLists(existingList, newList);