comparer deux tableaux de différentes longueurs et Afficher les différences

Question

Problème:
J'ai deux tableaux qui peuvent éventuellement être différentes longueurs. J'ai besoin de parcourir les deux tableaux et trouver des similitudes, des ajouts et des suppressions.

Quelle est la manière la plus rapide et la plus efficace d'accomplir ceci en C#?

Édition: Les tableaux sont pré-triés et peuvent contenir entre 50 et 100 éléments. En outre, il n'y a pas de contraintes sur la vitesse et/ou l'utilisation de la mémoire (mais personne n'aime un porc de mémoire;)

---

Par exemple:

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

ET

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

---

Différences:

(par rapport au tableau foo_new)

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

(par rapport au tableau Bar_New)

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

Answer 1

Vous pouvez utiliser Except et 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

Étant donné que vos tableaux sont classés, vous devriez être en mesure juste Parcourez les tableaux simultanément et en un seul passage et déterminez si chaque élément est dans l'autre tableau. (. Similaire à l'étape de fusion dans une sorte de fusion) Vous pouvez voir un échantillon de ce ci-dessous:

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++]); 

Sinon, vous auriez besoin de passer par un tableau, et pour chaque élément de ce tableau, faites une seule passe de l'autre tableau à la recherche d'un match.

Modifier: JP a une bonne suggestion sur la façon de le faire en utilisant le framework. Bien que, en supposant que les tableaux sont triés, l'avantage de mon approche est que vous n'avez à faire qu'une seule passe pour trouver tous les résultats. Vous n'auriez pas à faire trois passes.

Answer 3

J'ai écrit ce un certain temps:

Utilisation:

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

Mise en œuvre:

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

Je suis allé de l'avant et codé à la main et utiliser l'exemple dans la réponse acceptée, et le code à la main fonctionne un peu mieux. J'ai géré la sortie de mes chaînes un peu différemment.Les autres facteurs à prendre en compte sont les suivants: Excepté faire une copie triée du tableau (puisqu'il ne peut pas supposer qu'il est trié) ou fait une sorte de hachage ou de recherche linéaire (en fait limité à IEnumerable - pour les très grands tableaux déjà triés , cela pourrait être un problème). Vous pouvez changer le mien pour comparer IEnumerable (qui est plus général) au lieu 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()); 
}