Porównywanie zawartości tablic w C#

Przykład:

{
    int[] a1 = new int[] { 145, 2, 3 };
    int[] a2 = new int[] { 145, 2, 3 };
    object[] a3 = new object[] { 145, 2, 3 };
    object[] a4 = new object[] { 145, 2, 3 };

    Debug.Assert((a1[0].Equals(a2[0])));
    Debug.Assert(a1[0] == a2[0]);

    Debug.Assert((a3[0].Equals(a4[0])));
    Debug.Assert(a3[0] != a4[0]);

    Debug.Assert((a1[0].Equals(a3[0])));
    //Debug.Assert(a1[0] == a3[0]);

    Debug.Assert((a3[0].Equals(a1[0])));
    //Debug.Assert(a3[0] == a1[0]);

    Debug.Assert(a1 != a2);
    Debug.Assert(!a1.Equals(a2));
    Debug.Assert(!Array.Equals(a1, a2));

    Debug.Assert(a3 != a4);
    Debug.Assert(!a3.Equals(a4));
    Debug.Assert(!Array.Equals(a3, a4));

    //Debug.Assert(a1 == a3);
    Debug.Assert(!a1.Equals(a3));
    Debug.Assert(!Array.Equals(a1, a3));

    //Debug.Assert(a3 == a1);
    Debug.Assert(!a3.Equals(a1));
    Debug.Assert(!Array.Equals(a3, a1));

    Debug.Assert(a1.SequenceEqual(a2));
    Debug.Assert(a3.SequenceEqual(a4));
    //Debug.Assert(a1.SequenceEqual(a3));
    //Debug.Assert(a3.SequenceEqual(a1));
}

Linie zakomentowane nie kompilują się. Jak widać obiekt typu Array, po którym dziedziczą wszystkie tablice, jak i te tablice nie przeładowują operatora ==, ani metody Equals(), dzięki temu wszystkie porównania tablic sprowadzają się do porównania referencji do nich. Sam obiekt Array nie udostępnia żadnej metody, która by nam w takim porównaniu pomogła. Więcej, samo środowisko czegoś takiego nam nie udostępnia, poza metodą SequenceEqual dostarczoną przez LINQ. Musimy więc sami zająć się sprawą porównywania tablic. Poniższy kod prezentuje 6 różnych metod porównywania tablic dla typów wartościowych i 5 dla typów referencyjnych. W metodzie Test1() porównywane są typy wartościowe. W metodzie Test2 porównywane są typy referencyjne. Dla każdej metody testowej najpierw sprawdzana jest poprawność algorytmów porównujących. A później wykonywane są dwie serie pomiarów. Najpierw duża tablica i mało sprawdzeń, później mała tablica i dużo sprawdzeń. Ilość porównań elementów tablicy jest taka sama w obu przypadkach. Chodzi tutaj o sprawdzenie kosztu samego porównania tablic.

public void Measure(int repeats, Action a)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();

    for (int i = 0; i < repeats; i++)
        a();

    sw.Stop();
    System.Console.WriteLine(sw.ElapsedMilliseconds);
}

public bool Compare1<T>(T[] ar1, T[] ar2)
{
    if (ar1.Length != ar2.Length)
        return false;

    for (int i = 0; i < ar1.Length; i++)
        if (!ar1[i].Equals(ar2[i]))
            return false;

    return true;
}

public bool Compare2<T>(T[] ar1, T[] ar2, Func<T, T, bool> comparer)
{
    if (ar1.Length != ar2.Length)
        return false;

    for (int i = 0; i < ar1.Length; i++)
        if (!comparer(ar1[i], ar2[i]))
            return false;

    return true;
}

public bool Compare3<T>(T[] ar1, T[] ar2, IEqualityComparer<T> comparer)
{
    if (ar1.Length != ar2.Length)
        return false;

    for (int i = 0; i < ar1.Length; i++)
        if (!comparer.Equals(ar1[i], ar2[i]))
            return false;

    return true;
}

public bool Compare4a(int[] ar1, int[] ar2)
{
    if (ar1.Length != ar2.Length)
        return false;

    for (int i = 0; i < ar1.Length; i++)
        if (ar1[i] != ar2[i])
            return false;

    return true;
}

public bool Compare4b(object[] ar1, object[] ar2)
{
    if (ar1.Length != ar2.Length)
        return false;

    for (int i = 0; i < ar1.Length; i++)
        if (!ar1[i].Equals(ar2[i]))
            return false;

    return true;
}

class Comparer1 : IEqualityComparer<int>
{
    public bool Equals(int x, int y)
    {
        return x == y;
    }

    public int GetHashCode(int obj)
    {
        throw new NotImplementedException();
    }
}

class Comparer2 : IEqualityComparer<object>
{
    public bool Equals(object x, object y)
    {
        return x.Equals(y);
    }

    public int GetHashCode(object obj)
    {
        throw new NotImplementedException();
    }
}

public void Test1()
{
    int[] ar1 = Enumerable.Range(1, 1000000).ToArray();
    int[] ar2 = Enumerable.Range(1, 1000000).ToArray();
    int[] ar3 = Enumerable.Range(2, 1000000).ToArray();
    int[] ar4 = Enumerable.Range(1, 1000000 - 1).ToArray();

    Debug.Assert(Compare1(ar1, ar2));
    Debug.Assert(Compare1(ar1, ar1));
    Debug.Assert(!Compare1(ar1, ar3));
    Debug.Assert(!Compare1(ar1, ar4));

    Debug.Assert(Compare2(ar1, ar2, (a, b) => (a == b)));
    Debug.Assert(Compare2(ar1, ar1, (a, b) => (a == b)));
    Debug.Assert(!Compare2(ar1, ar3, (a, b) => (a == b)));
    Debug.Assert(!Compare2(ar1, ar4, (a, b) => (a == b)));

    Debug.Assert(Compare2(ar1, ar2, (a, b) => (a.Equals(b))));
    Debug.Assert(Compare2(ar1, ar1, (a, b) => (a.Equals(b))));
    Debug.Assert(!Compare2(ar1, ar3, (a, b) => (a.Equals(b))));
    Debug.Assert(!Compare2(ar1, ar4, (a, b) => (a.Equals(b))));

    Debug.Assert(Compare3(ar1, ar2, new Comparer1()));
    Debug.Assert(Compare3(ar1, ar1, new Comparer1()));
    Debug.Assert(!Compare3(ar1, ar3, new Comparer1()));
    Debug.Assert(!Compare3(ar1, ar4, new Comparer1()));

    Debug.Assert(Compare4a(ar1, ar2));
    Debug.Assert(Compare4a(ar1, ar1));
    Debug.Assert(!Compare4a(ar1, ar3));
    Debug.Assert(!Compare4a(ar1, ar4));

    Measure(100, () => ar1.SequenceEqual(ar2));
    Measure(100, () => Compare1(ar1, ar2));
    Measure(100, () => Compare2(ar1, ar2, (a, b) => (a == b)));
    Measure(100, () => Compare2(ar1, ar2, (a, b) => (a.Equals(b))));
    Measure(100, () => Compare3(ar1, ar2, new Comparer1()));
    Measure(100, () => Compare4a(ar1, ar2));

    System.Console.WriteLine("----");

    ar1 = Enumerable.Range(1, 1000000 / 100000).ToArray();
    ar2 = Enumerable.Range(1, 1000000 / 100000).ToArray();

    Measure(100 * 100000, () => ar1.SequenceEqual(ar2));
    Measure(100 * 100000, () => Compare1(ar1, ar2));
    Measure(100 * 100000, () => Compare2(ar1, ar2, (a, b) => (a == b)));
    Measure(100 * 100000, () => Compare2(ar1, ar2, (a, b) => (a.Equals(b))));
    Measure(100 * 100000, () => Compare3(ar1, ar2, new Comparer1()));
    Measure(100 * 100000, () => Compare4a(ar1, ar2));

    System.Console.WriteLine("----");
}

void Test2()
{
    object[] ar1 = (from n in Enumerable.Range(1, 1000000) select (object)n).ToArray();
    object[] ar2 = (from n in Enumerable.Range(1, 1000000) select (object)n).ToArray();
    object[] ar3 = (from n in Enumerable.Range(2, 1000000) select (object)n).ToArray();
    object[] ar4 = (from n in Enumerable.Range(1, 1000000-1) select (object)n).ToArray();

    Debug.Assert(Compare1(ar1, ar2));
    Debug.Assert(Compare1(ar1, ar1));
    Debug.Assert(!Compare1(ar1, ar3));
    Debug.Assert(!Compare1(ar1, ar4));

    Debug.Assert(Compare2(ar1, ar2, (a, b) => (a.Equals(b))));
    Debug.Assert(Compare2(ar1, ar1, (a, b) => (a.Equals(b))));
    Debug.Assert(!Compare2(ar1, ar3, (a, b) => (a.Equals(b))));
    Debug.Assert(!Compare2(ar1, ar4, (a, b) => (a.Equals(b))));

    Debug.Assert(Compare3(ar1, ar2, new Comparer2()));
    Debug.Assert(Compare3(ar1, ar1, new Comparer2()));
    Debug.Assert(!Compare3(ar1, ar3, new Comparer2()));
    Debug.Assert(!Compare3(ar1, ar4, new Comparer2()));

    Debug.Assert(Compare4b(ar1, ar2));
    Debug.Assert(Compare4b(ar1, ar1));
    Debug.Assert(!Compare4b(ar1, ar3));
    Debug.Assert(!Compare4b(ar1, ar4));

    Measure(100, () => ar1.SequenceEqual(ar2));
    Measure(100, () => Compare1(ar1, ar2));
    Measure(100, () => Compare2(ar1, ar2, (a, b) => (a.Equals(b))));
    Measure(100, () => Compare3(ar1, ar2, new Comparer2()));
    Measure(100, () => Compare4b(ar1, ar2));

    System.Console.WriteLine("----");

    ar1 = (from n in Enumerable.Range(1, 1000000 / 100000) select (object)n).ToArray();
    ar2 = (from n in Enumerable.Range(1, 1000000 / 100000) select (object)n).ToArray();

    Measure(100 * 100000, () => ar1.SequenceEqual(ar2));
    Measure(100 * 100000, () => Compare1(ar1, ar2));
    Measure(100 * 100000, () => Compare2(ar1, ar2, (a, b) => (a.Equals(b))));
    Measure(100 * 100000, () => Compare3(ar1, ar2, new Comparer2()));
    Measure(100 * 100000, () => Compare4b(ar1, ar2));

    System.Console.WriteLine("----");
}

public void Test()
{
    Test1();
    Test2();
}

Wyniki: 2317 1891 1338 1578 1307 596 ---- 3708 1957 1531 1740 1552 730 ---- 3293 1193 2059 2300 1192 ---- 4972 1261 2151 2448 1246 ---- Najpierw może jeśli chodzi o sam koszt uruchomienia porównania tablic. Widać, że milion razy więcej wywołań przekłada się na niewielki wzrost miliona porównań. Czyli czas samego wywołania porównania jest mały. Czas ten wzrasta znacznie dla SequenceEqual(). Jeśli chodzi o czas samego porównania to jak można się było spodziewać najwolniejsza jest metoda SequenceEqual(). Dla typów wartościowych najszybsze jest porównanie bezpośrednie tablic. Wolniejsze jest wykorzystanie IEqualityComparer. Prawie tak samo szybkie jest użycie jako metody porównawczej wyrażenia lambda z bezpośrednim porównaniem wartości. Dalej jest porównanie z użyciem wyrażenia lambda, ale wykorzystujące metodę Equals(). Dalej metoda Compare1(), która także wykorzystuje Equals() do porównania. Najwolniejsza jest wspomniana SequenceEqual(). Dla typów referencyjnych jest trochę inaczej. Nie ma tutaj sensu osobno porównywać za pomocą operatora == i Equals() stąd sposobów porównania jest o jeden mniej. Najszybciej działa bezpośrednie porównanie tablic. Dalej jest metoda Compare1 wykorzystująca Equals(). Dalej jest wykorzystanie wyrażenia lambda, które wykorzystuje Equals(). Dalej wykorzystanie IEqualityComparer. Na końcu wykorzystanie SequenceEqual(). Jeśli chodzi o metody, które nadają się zarówno do porównania typów wartościowych, jak i referencyjnych to w grę wchodzi tylko wykorzystanie SequenceEqual() lub Compare1. Compare1 jest szybsze, ale za to SequenceEqual() bardziej uniwersalne (działa na enumeratorach) i dostępne w standardzie. Jeśli chodzi o prędkość to niestety czym coś jest bardziej uniwersalne to tym jest wolniejsze. Skupmy się na metodzie Compare1(). Napiszmy ją tak by stała się uniwersalną metodą rozszerzoną:

public static class ArrayExtensions
{
    public static bool SameArrays<T>(this T[] ar1, T[] ar2)
    {
        if (Object.ReferenceEquals(ar1, ar2))
            return true;

        if (ar1.Length != ar2.Length)
            return false;

        for (int i = 0; i < ar1.Length; i++)
            if (!ar1[i].Equals(ar2[i]))
                return false;

        return true;
    }
}

public void Test3()
{
    {
        int[] ar1 = Enumerable.Range(1, 1000000).ToArray();
        int[] ar2 = Enumerable.Range(1, 1000000).ToArray();
        int[] ar3 = Enumerable.Range(2, 1000000).ToArray();
        int[] ar4 = Enumerable.Range(1, 1000000 - 1).ToArray();

        Debug.Assert(ar1.SameArrays(ar2));
        Debug.Assert(ar1.SameArrays(ar1));
        Debug.Assert(!ar1.SameArrays(ar3));
        Debug.Assert(!ar1.SameArrays(ar4));
    }

    {
        object[] ar1 = (from n in Enumerable.Range(1, 1000000) select (object)n).ToArray();
        object[] ar2 = (from n in Enumerable.Range(1, 1000000) select (object)n).ToArray();
        object[] ar3 = (from n in Enumerable.Range(2, 1000000) select (object)n).ToArray();
        object[] ar4 = (from n in Enumerable.Range(1, 1000000 - 1) select (object)n).ToArray();

        Debug.Assert(ar1.SameArrays(ar2));
        Debug.Assert(ar1.SameArrays(ar1));
        Debug.Assert(!ar1.SameArrays(ar3));
        Debug.Assert(!ar1.SameArrays(ar4));
    }
}

Dodatkowo, dodałem tam drobną optymalizację, by nie porównywać tych samych obiektów.