Porównywanie dwóch zbiorów dla równości niezależnie od kolejności elementów w nich

Prostym i dość skutecznym rozwiązaniem jest sortowanie obu zbiorów, a następnie porównywanie ich dla równości:

bool equal = collection1.OrderBy(i => i).SequenceEqual(
                 collection2.OrderBy(i => i));

Ten algorytm to O (N*logN) , podczas gdy Twoje rozwiązanie powyżej to O (N^2).

Jeśli zbiory mają pewne właściwości, możesz być w stanie zaimplementować szybsze rozwiązanie. Na przykład, jeśli obie kolekcje są zestawami skrótów, nie mogą one zawierać duplikatów. Również sprawdzenie, czy zestaw hashów zawiera jakiś element jest bardzo szybkie. W takim przypadku algorytm podobny do twojego prawdopodobnie będzie najszybszy.

Utwórz Słownik "dict", a następnie dla każdego członka w pierwszej kolekcji, wykonaj dict [member]++;

Następnie pętla nad drugim zbiorem w ten sam sposób, ale dla każdego członka wykonaj dict [member]--.

Na końcu pętla na wszystkich członach w słowniku:

    private bool SetEqual (List<int> left, List<int> right) {

        if (left.Count != right.Count)
            return false;

        Dictionary<int, int> dict = new Dictionary<int, int>();

        foreach (int member in left) {
            if (dict.ContainsKey(member) == false)
                dict[member] = 1;
            else
                dict[member]++;
        }

        foreach (int member in right) {
            if (dict.ContainsKey(member) == false)
                return false;
            else
                dict[member]--;
        }

        foreach (KeyValuePair<int, int> kvp in dict) {
            if (kvp.Value != 0)
                return false;
        }

        return true;

    }

Edit: z tego, co wiem, Jest to w tej samej kolejności, co najbardziej efektywny algorytm. Algorytm ten to O (N), zakładając, że słownik używa wyszukiwań O (1).

Oto moja (pod dużym wpływem D. Jenningsa) ogólna implementacja metody porównawczej (w C#):

/// <summary>
/// Represents a service used to compare two collections for equality.
/// </summary>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
public class CollectionComparer<T>
{
    /// <summary>
    /// Compares the content of two collections for equality.
    /// </summary>
    /// <param name="foo">The first collection.</param>
    /// <param name="bar">The second collection.</param>
    /// <returns>True if both collections have the same content, false otherwise.</returns>
    public bool Execute(ICollection<T> foo, ICollection<T> bar)
    {
        // Declare a dictionary to count the occurence of the items in the collection
        Dictionary<T, int> itemCounts = new Dictionary<T,int>();

        // Increase the count for each occurence of the item in the first collection
        foreach (T item in foo)
        {
            if (itemCounts.ContainsKey(item))
            {
                itemCounts[item]++;
            }
            else
            {
                itemCounts[item] = 1;
            }
        }

        // Wrap the keys in a searchable list
        List<T> keys = new List<T>(itemCounts.Keys);

        // Decrease the count for each occurence of the item in the second collection
        foreach (T item in bar)
        {
            // Try to find a key for the item
            // The keys of a dictionary are compared by reference, so we have to
            // find the original key that is equivalent to the "item"
            // You may want to override ".Equals" to define what it means for
            // two "T" objects to be equal
            T key = keys.Find(
                delegate(T listKey)
                {
                    return listKey.Equals(item);
                });

            // Check if a key was found
            if(key != null)
            {
                itemCounts[key]--;
            }
            else
            {
                // There was no occurence of this item in the first collection, thus the collections are not equal
                return false;
            }
        }

        // The count of each item should be 0 if the contents of the collections are equal
        foreach (int value in itemCounts.Values)
        {
            if (value != 0)
            {
                return false;
            }
        }

        // The collections are equal
        return true;
    }
}

Możesz użyć Hashset . Spójrz na metodę SetEquals .

EDIT: zdałem sobie sprawę, jak tylko pozowałem, że to naprawdę działa tylko dla zestawów-nie będzie prawidłowo radzić sobie ze zbiorami, które mają duplikaty przedmiotów. Na przykład { 1, 1, 2 } i { 2, 2, 1 } będą uważane za równe z punktu widzenia tego algorytmu. Jeśli jednak twoje zbiory są zbiorami (lub ich równość można zmierzyć w ten sposób), mam nadzieję, że poniżej znajdziesz przydatne.

Rozwiązanie, którego używam to:

return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;

Linq robi słownik pod okładkami, więc jest to również O (N). (Uwaga, to O(1), jeśli zbiory nie są tego samego rozmiaru).

Wykonałem test zdrowego rozsądku przy użyciu metody" SetEqual " sugerowanej przez Daniela, metody OrderBy/Sequencequals sugerowanej przez Igora i mojej sugestii. W 2011 roku, po raz pierwszy w historii, pojawiła się nowa wersja gry, która została wydana na konsolę Xbox 360.]}

Myślę, że prostota kodu Intersektu Linq sprawia, że jest to preferowane rozwiązanie.

__Test Latency(ms)__
N, SetEquals, OrderBy, Intersect    
1024, 0, 0, 0    
2048, 0, 0, 0    
4096, 31.2468, 0, 0    
8192, 62.4936, 0, 0    
16384, 156.234, 15.6234, 0    
32768, 312.468, 15.6234, 46.8702    
65536, 640.5594, 46.8702, 31.2468    
131072, 1312.3656, 93.7404, 203.1042    
262144, 3765.2394, 187.4808, 187.4808    
524288, 5718.1644, 374.9616, 406.2084    
1048576, 11420.7054, 734.2998, 718.6764    
2097152, 35090.1564, 1515.4698, 1484.223

W przypadku braku powtórzeń i braku porządku, można użyć następującego EqualityComparer, aby zezwolić kolekcjom jako kluczom słownikowym:

public class SetComparer<T> : IEqualityComparer<IEnumerable<T>> 
where T:IComparable<T>
{
    public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
    {
        if (first == second)
            return true;
        if ((first == null) || (second == null))
            return false;
        return first.ToHashSet().SetEquals(second);
    }

    public int GetHashCode(IEnumerable<T> enumerable)
    {
        int hash = 17;

        foreach (T val in enumerable.OrderBy(x => x))
            hash = hash * 23 + val.GetHashCode();

        return hash;
    }
}

Tutaj jest implementacja ToHashSet (), której użyłem. Algorytm hash code pochodzi z efektywnej Javy (według Jona Skeeta).

static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
    var setXOR = new HashSet<T>(set1);
    setXOR.SymmetricExceptWith(set2);
    return (setXOR.Count == 0);
}

Rozwiązanie wymaga. NET 3.5 i przestrzeni nazw System.Collections.Generic. według Microsoftu, SymmetricExceptWith jest operacją O(n + m), z n reprezentującą liczbę elementów w pierwszym zbiorze i m reprezentującą liczbę elementów w drugim zbiorze. W razie potrzeby można zawsze dodać do tej funkcji porównywarkę równości.

Dlaczego nie używać .Except ()

// Create the IEnumerable data sources.
string[] names1 = System.IO.File.ReadAllLines(@"../../../names1.txt");
string[] names2 = System.IO.File.ReadAllLines(@"../../../names2.txt");
// Create the query. Note that method syntax must be used here.
IEnumerable<string> differenceQuery =   names1.Except(names2);
// Execute the query.
Console.WriteLine("The following lines are in names1.txt but not names2.txt");
foreach (string s in differenceQuery)
     Console.WriteLine(s);

Http://msdn.microsoft.com/en-us/library/bb397894.aspx

Duplikat pewnego rodzaju posta, ale Sprawdź moje rozwiązanie do porównywania zbiorów . To całkiem proste:

To wykona porównanie równości niezależnie od kolejności:

var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;

To sprawdzi, czy elementy zostały dodane / usunięte:

var list1 = new[] { "Billy", "Bob" };
var list2 = new[] { "Bob", "Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added;   //Sally
var inbothlists = diff.Equal;   //Bob

To zobaczy jakie pozycje w słowniku zostały zmienione:

var original = new Dictionary<int, string>() { { 1, "a" }, { 2, "b" } };
var changed = new Dictionary<int, string>() { { 1, "aaa" }, { 2, "b" } };
var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value);
foreach (var item in diff.Different)
  Console.Write("{0} changed to {1}", item.Key.Value, item.Value.Value);
//Will output: a changed to aaa

Original post here .

Jeśli używasz Shouldly , możesz użyć ShouldAllBe z Contains.

collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};

collection1.ShouldAllBe(item=>collection2.Contains(item)); // true

I na koniec możesz napisać rozszerzenie.

public static class ShouldlyIEnumerableExtensions
{
    public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
    {
        list.ShouldAllBe(l => equivalent.Contains(l));
    }
}

UPDATE

Opcjonalny parametr istnieje w metodzie ShouldBe .

collection1.ShouldBe(collection2, ignoreOrder: true); // true

Erickson ma prawie rację: ponieważ chcesz dopasować liczbę duplikatów, chcesz Torba . W Javie wygląda to mniej więcej tak:

(new HashBag(collection1)).equals(new HashBag(collection2))

Jestem pewien, że C# ma wbudowaną implementację Set. Użyłbym tego jako pierwszy; jeśli wydajność jest problemem, zawsze można użyć innej implementacji zestawu, ale użyć tego samego interfejsu zestawu.

Oto mój wariant metody rozszerzenia odpowiedzi ohadsc, na wypadek, gdyby komuś się przydała

static public class EnumerableExtensions 
{
    static public bool IsEquivalentTo<T>(this IEnumerable<T> first, IEnumerable<T> second)
    {
        if ((first == null) != (second == null))
            return false;

        if (!object.ReferenceEquals(first, second) && (first != null))
        {
            if (first.Count() != second.Count())
                return false;

            if ((first.Count() != 0) && HaveMismatchedElement<T>(first, second))
                return false;
        }

        return true;
    }

    private static bool HaveMismatchedElement<T>(IEnumerable<T> first, IEnumerable<T> second)
    {
        int firstCount;
        int secondCount;

        var firstElementCounts = GetElementCounts<T>(first, out firstCount);
        var secondElementCounts = GetElementCounts<T>(second, out secondCount);

        if (firstCount != secondCount)
            return true;

        foreach (var kvp in firstElementCounts)
        {
            firstCount = kvp.Value;
            secondElementCounts.TryGetValue(kvp.Key, out secondCount);

            if (firstCount != secondCount)
                return true;
        }

        return false;
    }

    private static Dictionary<T, int> GetElementCounts<T>(IEnumerable<T> enumerable, out int nullCount)
    {
        var dictionary = new Dictionary<T, int>();
        nullCount = 0;

        foreach (T element in enumerable)
        {
            if (element == null)
            {
                nullCount++;
            }
            else
            {
                int num;
                dictionary.TryGetValue(element, out num);
                num++;
                dictionary[element] = num;
            }
        }

        return dictionary;
    }

    static private int GetHashCode<T>(IEnumerable<T> enumerable)
    {
        int hash = 17;

        foreach (T val in enumerable.OrderBy(x => x))
            hash = hash * 23 + val.GetHashCode();

        return hash;
    }
}

Oto rozwiązanie, które jest ulepszeniem w stosunku do tego .

public static bool HasSameElementsAs<T>(
        this IEnumerable<T> first, 
        IEnumerable<T> second, 
        IEqualityComparer<T> comparer = null)
    {
        var firstMap = first
            .GroupBy(x => x, comparer)
            .ToDictionary(x => x.Key, x => x.Count(), comparer);

        var secondMap = second
            .GroupBy(x => x, comparer)
            .ToDictionary(x => x.Key, x => x.Count(), comparer);

        if (firstMap.Keys.Count != secondMap.Keys.Count)
            return false;

        if (firstMap.Keys.Any(k1 => !secondMap.ContainsKey(k1)))
            return false;

        return firstMap.Keys.All(x => firstMap[x] == secondMap[x]);
    }

Istnieje wiele rozwiązań tego problemu. Jeśli nie dbasz o duplikaty, nie musisz sortować obu. Najpierw upewnij się, że mają taką samą liczbę elementów. Po tym sortować jedną z kolekcji. Następnie przeszukaj binsearch każdy element z drugiej kolekcji w sortowanej kolekcji. Jeśli nie znajdziesz danego elementu Zatrzymaj i zwróć false. Złożoność tego: - sortowanie pierwszego zbioru: NLog(N) - wyszukiwanie każdej pozycji od drugiej do pierwszej: NLOG (N) więc kończysz z 2*n * LOG(N) zakładając, że pasują i sprawdzasz wszystko. Jest to podobne do złożoności sortowania obu. Daje to również korzyść, aby zatrzymać się wcześniej, jeśli jest różnica. Należy jednak pamiętać, że jeśli oba są sortowane przed przystąpieniem do tego porównania i spróbujesz sortować za pomocą czegoś takiego jak qsort, sortowanie będzie droższe. Istnieją do tego optymalizacje. Inną alternatywą, która świetnie sprawdza się w małych kolekcjach, w których znasz zakres elementów, jest użyj indeksu maski bitowej. Daje to wydajność O (n). Inną alternatywą jest użycie hasha i sprawdzenie go. W przypadku małych kolekcji zwykle dużo lepiej jest sortować lub indeksować maskę bitową. Hashtable mają wadę gorszej lokalizacji, więc miej to na uwadze. Znowu, tylko jeśli nie dbasz o duplikaty. Jeśli chcesz rozliczać duplikaty, przejdź do sortowania obu.

W wielu przypadkach jedyną odpowiednią odpowiedzią jest odpowiedź Igora Ostrovsky ' ego, inne odpowiedzi opierają się na kodzie hashowym obiektów. Ale kiedy generujesz kod skrótu dla obiektu, robisz to tylko na podstawie jego niezmiennych pól - takich jak Pole object Id (w przypadku jednostki bazy danych) - Dlaczego ważne jest, aby nadpisać GetHashCode, gdy metoda Equals jest nadpisana?

Oznacza to, że jeśli porównasz dwie kolekcje, wynik może być prawdziwy dla metody compare, nawet jeśli pola z różnych pozycji nie są równe . Aby dokładnie porównać zbiory, należy użyć metody Igora i zaimplementować Ieequalicity .

Proszę przeczytać komentarze mnie i Pana Schnidera na jego najczęściej głosowanym poście.

Jakub

Zezwalając na duplikaty w IEnumerable<T> (jeśli zestawy nie są pożądane\możliwe) i "ignorując kolejność" powinieneś być w stanie użyć .GroupBy().

Nie jestem ekspertem w pomiarach złożoności, ale moje podstawowe zrozumienie jest takie, że powinno to być O (n). Rozumiem O(N^2) jako wynik operacji O(n) wewnątrz innej operacji o (n), takiej jak ListA.Where(a => ListB.Contains(a)).ToList(). Każdy element listy B jest oceniany pod kątem równości względem każdego elementu listy.

Jak mówiłem, moje zrozumienie złożoności jest ograniczone, więc popraw mnie, jeśli się mylę.

public static bool IsSameAs<T, TKey>(this IEnumerable<T> source, IEnumerable<T> target, Expression<Func<T, TKey>> keySelectorExpression)
    {
        // check the object
        if (source == null && target == null) return true;
        if (source == null || target == null) return false;

        var sourceList = source.ToList();
        var targetList = target.ToList();

        // check the list count :: { 1,1,1 } != { 1,1,1,1 }
        if (sourceList.Count != targetList.Count) return false;

        var keySelector = keySelectorExpression.Compile();
        var groupedSourceList = sourceList.GroupBy(keySelector).ToList();
        var groupedTargetList = targetList.GroupBy(keySelector).ToList();

        // check that the number of grouptings match :: { 1,1,2,3,4 } != { 1,1,2,3,4,5 }
        var groupCountIsSame = groupedSourceList.Count == groupedTargetList.Count;
        if (!groupCountIsSame) return false;

        // check that the count of each group in source has the same count in target :: for values { 1,1,2,3,4 } & { 1,1,1,2,3,4 }
        // key:count
        // { 1:2, 2:1, 3:1, 4:1 } != { 1:3, 2:1, 3:1, 4:1 }
        var countsMissmatch = groupedSourceList.Any(sourceGroup =>
                                                        {
                                                            var targetGroup = groupedTargetList.Single(y => y.Key.Equals(sourceGroup.Key));
                                                            return sourceGroup.Count() != targetGroup.Count();
                                                        });
        return !countsMissmatch;
    }