比较两个不同长度的数组并显示差异

Question

问题：
我有两个数组，它们可能长度不同。我需要遍历这两个数组并找到相似之处、添加的元素和删除的元素。

在C#中，最快、最有效的方法是什么？

编辑： 这些数组是预排序的，它们可以包含50-100个元素。此外，速度和/或内存使用没有任何限制（但是，没有人喜欢内存占用量）;

---

例如：

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

AND

：并且。

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

---

区别：

（相对于Foo_New数组）

[相同]    "test1"
[相同]    "test2"
[已删除]  "test3"
[已添加]  "test4"
[已添加]  "test5"

（相对于Bar_New数组）

[相同]    "test1"
[已删除]  "test2"
[已删除]  "test4"
[已添加]  "test3"

- Sean

---

有点像作业。你尝试过解决方案了吗？如果是这样，请发表出来，Stack Overflow 社区成员可以高效地对其进行评论和批判。 - Charlie Salts

不，这不是作业，我要到秋季才回学校。 ;) 我会发布我目前想出来的东西。 - Sean

@Chris，对我来说这更像是源代码控制冲突报告。 - Spencer Ruport

你需要提供更多细节：数组是否预先排序？它们是否任意大？其他限制条件如内存使用和速度是什么？ 你是在寻找最短的代码吗？最简单的？还是资源效率最高的？ - Renaud Bompuis

@Renaud，我编辑了这个问题，希望现在更清晰了。感谢您的建议。 - Sean

Answer 1

您可以使用Except和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);
}

- JP Alioto

---

请注意，这个实现方法比我的方案稍微低效一些，也没有那么封装...但这并不是很重要，它已经解决了问题。 - Sam Saffron

@Sam，我实际上喜欢你的两个答案，但我不能选择两个答案。 :( 我可能会将它们合并。 - Sean

Answer 2

我自己手写了一份代码，并使用被接受的答案中的例子进行比较，我的手写代码表现稍微好一些。我对字符串的输出处理方式略有不同。其他需要考虑的因素包括 Except 方法是否会对数组进行排序（因为它不能假设数组已经排好序），或者它是否会创建某种哈希表或线性搜索（实际上它只能限制在 IEnumerable 上 - 对于非常大的已经排好序的数组，这可能是个问题）。你可以将我的代码更改为比较 IEnumerable（更通用）而不是 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());
}

- Cade Roux

---

感谢您抽出时间手动编写解决方案并测试其速度！ - Sean

Answer 3

由于您的数组已经排序，因此您应该能够同时遍历这些数组，并在一次遍历中确定每个元素是否在另一个数组中。 （类似于归并排序中的合并步骤。）您可以在下面看到示例：

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

或者你需要遍历一个数组，对于这个数组中的每个元素，在另一个数组中进行一次匹配。

编辑：JP提出了一个使用框架来完成此操作的好建议。但是，假设这些数组已经排序，我的方法的好处在于你只需要进行一次遍历就可以找到所有结果。你不需要进行三次遍历。

- Rob Rolnick

---

如果我需要将我的代码移植到另一种不依赖于.NET的语言中，这将非常有用。感谢您的编辑和示例！ - Sean

Answer 4

我之前写过这个：

用法：

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

实现：

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

}

- Sam Saffron