comparar dos matrices de diferentes longitudes y Mostrar diferencias

Question

Problema:
Tengo dos matrices que posiblemente pueden ser diferentes longitudes. Necesito iterar a través de ambas matrices y encontrar similitudes, adiciones y eliminaciones.

¿Cuál es la forma más rápida y eficiente de lograr esto en C#?

Edit: Las matrices están pre-clasificadas y pueden contener entre 50-100 elementos. También, no hay limitaciones en la velocidad y/o uso de la memoria (sin embargo, no le gusta un cerdo de la memoria;)

---

Por ejemplo:

String[] Foo_Old = {"test1", "test2", "test3"}; 
String[] Foo_New = {"test1", "test2", "test4", "test5"}; 

Y

String[] Bar_Old = {"test1", "test2", "test4"}; 
String[] Bar_New = {"test1", "test3"}; 

---

diferencias:

(con respecto a la matriz foo_new)

 
[Same] "test1" 
[Same] "test2" 
[Removed] "test3" 
[Added] "test4" 
[Added] "test5" 

(con respecto a la matriz Bar_New)

 
[Same] "test1" 
[Removed] "test2" 
[Removed] "test4" 
[Added] "test3" 

Answer 1

Puede utilizar Except y Intersect ...

var Foo_Old = new[] { "test1", "test2", "test3" }; 
var Foo_New = new[] { "test1", "test2", "test4", "test5" }; 

var diff = Foo_New.Except(Foo_Old); 
var inter = Foo_New.Intersect(Foo_Old); 
var rem = Foo_Old.Except(Foo_New); 

foreach (var s in diff) 
{ 
    Console.WriteLine("Added " + s); 
} 

foreach (var s in inter) 
{ 
    Console.WriteLine("Same " + s); 
} 

foreach (var s in rem) 
{ 
    Console.WriteLine("Removed " + s); 
} 

Answer 2

Dado que las matrices están ordenados, debe ser capaz de simplemente ir a través de las matrices simultáneamente, y en una pasada y determinar si cada elemento está en la otra matriz. (. Al igual que en la etapa de mezcla en fusión de tipo) Usted puede ver una muestra de que a continuación:

string[] oldVersion = { "test1", "test2", "test3" }; 
string[] newVersion = { "test1", "test2", "test4", "test5" }; 

int oldIndex = 0, newIndex = 0; 

while ((oldIndex < oldVersion.Length) && (newIndex < newVersion.Length)) { 
    int comparison = oldVersion[oldIndex].CompareTo(newVersion[newIndex]); 

    if (comparison < 0) 
     Console.WriteLine("[Removed]\t" + oldVersion[oldIndex++]); 
    else if (comparison > 0) 
     Console.WriteLine("[Added]\t\t" + newVersion[newIndex++]); 
    else { 
     Console.WriteLine("[Same]\t\t" + oldVersion[oldIndex++]); 
     newIndex++; 
    } 
} 

while (oldIndex < oldVersion.Length) 
    Console.WriteLine("[Removed]\t" + oldVersion[oldIndex++]); 

while (newIndex < newVersion.Length) 
    Console.WriteLine("[Added]\t\t" + newVersion[newIndex++]); 

alternativa que había necesidad de ir a través de una matriz, y para cada elemento de este vector, hace una sola pasada de la otra matriz buscando una coincidencia.

Editar: JP tiene una buena sugerencia sobre cómo hacer esto utilizando el marco. Aunque, suponiendo que los arreglos estén ordenados, el beneficio de mi enfoque es que solo tiene que hacer una pasada para encontrar todos los resultados. No tendrías que hacer tres pases.

Answer 3

de escribir este hace un tiempo:

Uso:

foreach (var diff in Foo_Old.Diff(Foo_New)){ 
    Console.WriteLine ("{0} action performed on {1}",diff.DiffAction,diff.Value); 
} 

Implementación:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace LinqExtensions { 

    enum DiffAction { 
     Added, 
     Removed, 
     Same 
    } 

    class DiffPair<T> { 
     public T Value { get; set; } 
     public DiffAction DiffAction { get; set; } 
    } 

    static class DiffExtension { 
     public static IEnumerable<DiffPair<T>> Diff<T> 
       (
        this IEnumerable<T> original, 
        IEnumerable<T> target 
       ) { 

      Dictionary<T, DiffAction> results = new Dictionary<T, DiffAction>(); 

      foreach (var item in original) { 
       results[item] = DiffAction.Removed; 
      } 

      foreach (var item in target) { 
       if (results.ContainsKey(item)) { 
        results[item] = DiffAction.Same; 
       } else { 
        results[item] = DiffAction.Added; 
       } 
      } 
      return results.Select(
       pair => new DiffPair<T> { 
        Value=pair.Key, 
        DiffAction = pair.Value 
       }); 
     } 
    } 

} 

Answer 4

Seguí y codifiqué a mano uno y uso el ejemplo en la respuesta aceptada, y el codificado a mano funciona un poco mejor. Manejé la salida de mis cadenas un poco diferente.Otros factores a considerar incluyen si el Excepto hace una copia ordenada de la matriz (ya que no puede suponer que está ordenada) o si realiza algún tipo de hash o una búsqueda lineal (en realidad está restringido a IEnumerable - para matrices muy grandes que ya están ordenadas , Esto podría ser un problema). Puede cambiar el mío para comparar IEnumerable (que es más general) en lugar de IComparable [].

static void ArrayCompare(IComparable[] Old, IComparable[] New) 
{ 
    int lpOld = 0; 
    int lpNew = 0; 
    int OldLength = Old.Length; 
    int NewLength = New.Length; 
    while (lpOld < OldLength || lpNew < NewLength) 
    { 
     int compare; 

     if (lpOld >= OldLength) compare = 1; 
     else if (lpNew >= NewLength) compare = -1; 
     else compare = Old[lpOld].CompareTo(New[lpNew]); 

     if (compare < 0) 
     { 
      Debug.WriteLine(string.Format("[Removed] {0}", Old[lpOld].ToString())); 
      lpOld++; 
     } 
     else if (compare > 0) 
     { 
      Debug.WriteLine(string.Format("[Added] {0}", New[lpNew].ToString())); 
      lpNew++; 
     } 
     else 
     { 
      Debug.WriteLine(string.Format("[Same] {0}", Old[lpOld].ToString())); 
      lpOld++; 
      lpNew++; 
     } 
    } 
} 

static void ArrayCompare2(IComparable[] Old, IComparable[] New) { 
    var diff = New.Except(Old); 
    var inter = New.Intersect(Old); 
    var rem = Old.Except(New); 

    foreach (var s in diff) 
    { 
     Debug.WriteLine("Added " + s); 
    } 

    foreach (var s in inter) 
    { 
     Debug.WriteLine("Same " + s); 
    } 

    foreach (var s in rem) 
    { 
     Debug.WriteLine("Removed " + s); 
    } 
} 

static void Main(string[] args) 
{ 
    String[] Foo_Old = {"test1", "test2", "test3"}; 
    String[] Foo_New = {"test1", "test2", "test4", "test5"}; 
    String[] Bar_Old = {"test1", "test2", "test4"}; 
    String[] Bar_New = {"test1", "test3"}; 

    Stopwatch w1 = new Stopwatch(); 
    w1.Start(); 
    for (int lp = 0; lp < 10000; lp++) 
    { 
     ArrayCompare(Foo_Old, Foo_New); 
     ArrayCompare(Bar_Old, Bar_New); 
    } 
    w1.Stop(); 

    Stopwatch w2 = new Stopwatch(); 
    w2.Start(); 
    for (int lp = 0; lp < 10000; lp++) 
    { 
     ArrayCompare2(Foo_Old, Foo_New); 
     ArrayCompare2(Bar_Old, Bar_New); 
    } 
    w2.Stop(); 

    Debug.WriteLine(w1.Elapsed.ToString()); 
    Debug.WriteLine(w2.Elapsed.ToString()); 
}