Comparando dos IEnumerable para detectar cambios

Question

Para mi primera publicación aquí, tengo una pregunta sobre la comparación de IEnumerable. Tengo una estructura enlazable basada en una lógica de enumeración. El contenido de IEnumerable cambia con el tiempo y tengo que activar manualmente los eventos CollectionChanged.

Tengo un algoritmo muy ingenuo que me permite detectar cambios simples entre dos estados de IEnumerable (simple, simple, múltiple, múltiple) pero no es muy eficiente y no detecta todo.

Un ejemplo rápido de lo que necesito:

estado 1 de la IEnumerable: A * B * C * D * E

2 del estado de la IEnumerable: A * C * B * D * D1

para este ejemplo, tendría que detectar

• Una operación de movimiento: B cambió índice desde 1 hasta 2
• Una operación Añadir: D1 se insertó en el índice 4
• Una operación de eliminación: E se eliminó

¿Existe un algoritmo para resolver este problema tan eficientemente como sea posible (O (n log (n)) sería un buen comienzo)?

Gracias!

Answer 1

Ésta es sin compilar, código no comprobado y al menos parcialmente psuedo.

Dada una única detección de movimiento siendo suficiente Artículos sólo puede moverse hacia delante, moviéndose hacia atrás será el resultado de otro artículo que es movimiento o eliminado

por ejemplo estado 1 del IEnumerable: A * B * C * D * E

2 del estado de la IEnumerable: A * B * D * C * D1

Resultado B en tanto y C se mueve hacia adelante.

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

Resultado: comparación A y A
Siguiente
Compare B y D
Encontrar B
B movido -> 2
Añadir 2 a la lista Ignorar
Restablecer Enum2
Compara C y D
Buscar C
C Movido -> 3
Agregar 3 a Ignorar la lista de
Restablecer Enum2
Siguiente
Comparar D y D
Siguiente
de salto (2)
de salto (3)
Comparar E y D1
Encuentre E
Eliminado (E)
Siguiente
End of Enum1 Agregado (D1,4)

Creo que hay un ahorro en algún lugar si enum2pos se queda muy atrás para ver si ha sido eliminado y si no ha agregado un salto para su posición original en enum1, esto ayudaría con la posición de enum2 siendo reiniciada todo el tiempo.

Answer 2

Si prefiere utilizar LINQ, que aquí hay una solución simple basada en su ejemplo .. Lo sentimos pero no está seguro de los resultados ..

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 simplemente

var newlyAdded = b.Except(a);