Confronto di due IEnumerable per rilevare le modifiche

Question

Per il mio primo post qui, ho una domanda riguardante il confronto IEnumerable. Ho una struttura bindable basata su una logica di enumerazione. Il contenuto di IEnumerable cambia nel tempo e devo attivare manualmente gli eventi CollectionChanged.

Ho un algoritmo molto ingenuo che mi consente di rilevare semplici cambiamenti tra due stati dell'IEnumerable (semplice aggiunta, rimozione semplice, aggiunta multipla, rimozione multipla) ma non è molto efficiente e non rileva tutto.

un rapido esempio di che cosa ho bisogno:

stato 1 del IEnumerable: A * B * C * D * E

Stato 2 del IEnumerable: A * C * B * D * D1

per questo esempio, avrei rilevare

• un'operazione di spostamento: B cambiato index dal 1 al 2
• Un'operazione Add: D1 è stato inserito all'indice 4
• Un'operazione di cancellazione: E stato rimosso

Esiste un algoritmo per risolvere questo problema nel modo più efficiente possibile (O (nCollegatevi (n)) sarebbe un buon inizio)?

Grazie!

Answer 1

Questo è non compilato, codice non testato e almeno parzialmente psuedo.

Dato un singolo rilevamento mossa essendo articoli sufficienti può muoversi solo in avanti, arretrando sarà il risultato di un altro elemento essendo mossa o rimosso

esempio Stato 1 del IEnumerable: A * B * C * D * E

stato 2 della IEnumerable: A * D * B * C * D1

risultati sia in B e C andare avanti.

enum1pos = -1; 
enum2pos = 0; 
    Value2 = enum2.Next() 
    enum2pos++; 
List<int> SkipList = new SkipList(); 
while(enum1 has values left) 
{ 
    Value1 = enum1.Next() 
    enum1pos++; 
    //Skip over moved items. 
    while (SkipList.Count > 0 && SkipList[0] == enum2.Position) 
    { 
    Value2 = enum2.Next() 
    enum2pos++; 
    } 
    if (Value1 == Value2) 
    Value2 = enum2.Next() 
    enum2pos++; 
    continue; 

    int temp = enum2pos; 
    while(Value1 !=Value and enum2 has more values) 
    { 
    Value2 = enum2.Next(); 
    enum2pos++; 
    } 
    if(Value1 != Value2) 
    ItemDeleted(Value1); 
    else 
    { 
    ItemMoved(Value1, enum2pos); 
    SkipList.Add(enum2pos); 
    } 
    //This is expensive for IEnumerable! 
    enum2.First(); 
    loop temp times 
    enum2.Next(); 
    //if 
} 
while (enum2 has values left) 
{ 
    while (SkipList.Count > 0 && SkipList[0] == enum2.Position) 
    { 
    Value2 = enum2.Next() 
    enum2pos++; 
    } 
    if (enum2 has values left) 
    Added(Value2, enum2pos) 
} 

Risultato: Confronta A e A
Successivo
Confronta B e D
Trova B
B Spostato -> 2
Aggiungi 2 a Salta lista
reset Enum2
Confronta C e D
Trova C
C spostato -> 3
Aggiungi 3 a Salta Lista
reset Enum2
Successivo
confrontare D e D
Successivo
Skip (2)
Skip (3)
Confronta E e D1
Trova E
Rimosso (E)
Avanti
End of Enum1 Aggiunto (D1,4)

Penso che ci sia un salvataggio da qualche parte se enum2pos si trova troppo indietro per vedere se è stato rimosso e se non ha aggiunto un salto per la sua posizione originale in enum1, questo aiuterebbe con la posizione di enum2 essere resettato tutto il tempo.

Answer 2

Se si preferisce usare LINQ, qui è una soluzione semplice, sulla base di esempio .. Ci dispiace, ma non sono sicuro delle prestazioni ..

var a = new List<string>{"A","B","C","D","E"}; 
var b = new List<string>{"A","C","B","D","D1"}; 

var removed = a.Except(b); 
var moved = a.Where(x => b[a.IndexOf(x)] != x && !removed.Contains(x)); 
List<string> newlyInserted = new List<string>(); 
foreach (var item in removed) 
{ 
    //Newly inserted into the list - D1 
    newlyInserted.Add(b[a.IndexOf(item)]); 
    //Index of D1 if required 
    var indexOfNewlyAddedItem = a.IndexOf(item); 
} 

o semplicemente

var newlyAdded = b.Except(a);