Сравнение двух коллекций для равенства независимо от порядка элементов в них

Question

Я хотел бы сравнить две коллекции (на C#), но я не уверен в том, что вы сможете эффективно реализовать это.

Я прочел другую тему о Enumerable.SequenceEqual, но это не совсем то, что я ищу.

В моем случае две коллекции будут равны, если оба они содержат одинаковые элементы (независимо от порядка).

Пример:

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

collection1 == collection2; // true 

То, что я обычно делаю цикл по каждому элементу одной коллекции и посмотреть, если он существует в другой коллекции, а затем цикл по каждому элементу другой коллекции и посмотреть, если она существует в первой коллекции. (Я начинаю с сравнения длин).

if (collection1.Count != collection2.Count) 
    return false; // the collections are not equal 

foreach (Item item in collection1) 
{ 
    if (!collection2.Contains(item)) 
     return false; // the collections are not equal 
} 

foreach (Item item in collection2) 
{ 
    if (!collection1.Contains(item)) 
     return false; // the collections are not equal 
} 

return true; // the collections are equal 

Однако это не совсем правильно, и, вероятно, это не самый эффективный способ сравнения двух коллекций для равенства.

пример я могу думать о том, что было бы неправильно это:

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

Какой была бы равна с моей реализации. Должен ли я просто подсчитать количество раз, когда каждый элемент будет найден, и убедитесь, что подсчеты равны в обеих коллекциях?

---

примеры в какой-то C# (назовем его псевдо-C#), но дать ответ на любой язык, который вы хотите, это не имеет значения.

Примечание: Я использовал целые числа в примерах для простоты, но я хочу, чтобы иметь возможность использовать ссылки типа объекты тоже (они не ведут себя правильно, как ключи, так как только ссылка на объект сравнивается, а не содержание).

Answer 1

Оказывается, Microsoft уже это покрывается в рамках тестирования: CollectionAssert.AreEquivalent

Замечания

Две коллекции эквивалентны, если они имеют одни и те же элементы в том же количестве, но и в любом порядке , Элементы равны, если их значения равны, нет, если они относятся к одному и тому же объекту.

Используя отражатель, я изменил код позади AreEquivalent(), чтобы создать соответствующий сопоставитель сравнений. Он более полна, чем существующие ответы, поскольку он учитывает нулевые значения, реализует IEqualityComparer и имеет определенную эффективность и проверку кросс-кейсов. плюс, это Microsoft :) использование

public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>> 
{ 
    private readonly IEqualityComparer<T> m_comparer; 
    public MultiSetComparer(IEqualityComparer<T> comparer = null) 
    { 
     m_comparer = comparer ?? EqualityComparer<T>.Default; 
    } 

    public bool Equals(IEnumerable<T> first, IEnumerable<T> second) 
    { 
     if (first == null) 
      return second == null; 

     if (second == null) 
      return false; 

     if (ReferenceEquals(first, second)) 
      return true; 

     if (first is ICollection<T> firstCollection && second is ICollection<T> secondCollection) 
     { 
      if (firstCollection.Count != secondCollection.Count) 
       return false; 

      if (firstCollection.Count == 0) 
       return true; 
     } 

     return !HaveMismatchedElement(first, second); 
    } 

    private bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second) 
    { 
     int firstNullCount; 
     int secondNullCount; 

     var firstElementCounts = GetElementCounts(first, out firstNullCount); 
     var secondElementCounts = GetElementCounts(second, out secondNullCount); 

     if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count) 
      return true; 

     foreach (var kvp in firstElementCounts) 
     { 
      var firstElementCount = kvp.Value; 
      int secondElementCount; 
      secondElementCounts.TryGetValue(kvp.Key, out secondElementCount); 

      if (firstElementCount != secondElementCount) 
       return true; 
     } 

     return false; 
    } 

    private Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount) 
    { 
     var dictionary = new Dictionary<T, int>(m_comparer); 
     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; 
    } 

    public int GetHashCode(IEnumerable<T> enumerable) 
    { 
     if (enumerable == null) throw new ArgumentNullException(nameof(enumerable)); 

     int hash = 17; 

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

     return hash; 
    } 
} 

Пример:

var set = new HashSet<IEnumerable<int>>(new[] {new[]{1,2,3}}, new MultiSetComparer<int>()); 
Console.WriteLine(set.Contains(new [] {3,2,1})); //true 
Console.WriteLine(set.Contains(new [] {1, 2, 3, 3})); //false 

Или если вы просто хотите, чтобы сравнить две коллекции непосредственно:

var comp = new MultiSetComparer<string>(); 
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","c","b"})); //true 
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","b"})); //false 

Наконец, вы можете использовать ап равенство по вашему выбору:

var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase); 
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true 

Answer 2

Создать словарь «dict», а затем для каждого члена в первой коллекции, do dict [member] ++;

Затем, переверните вторую коллекцию таким же образом, но для каждого члена do dict [member] -.

В конце концов, перебираем все члены в словаре:

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: Насколько я могу сказать, что это на том же порядке, как наиболее эффективный алгоритм. Этот алгоритм O (N), предполагая, что Словарь использует поиск O (1).

Answer 3

erickson практически прав: поскольку вы хотите совместить число совпадений, вы хотите получить Bag. В Java это выглядит примерно так:

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

Я уверен, что C# имеет встроенную реализацию Set. Я бы использовал это первым; если производительность является проблемой, вы всегда можете использовать другую реализацию Set, но использовать тот же интерфейс Set.

Answer 4

Простой и довольно эффективным решением для сортировки обеих коллекций, а затем сравнить их на равенство:

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

Этот алгоритм O (N * LogN), в то время как ваше решение выше O (N^2) ,

Если коллекции имеют определенные свойства, возможно, вы сможете реализовать более быстрое решение. Например, если обе ваши коллекции являются хэш-наборами, они не могут содержать дубликатов. Кроме того, проверка того, содержит ли хэш-набор какой-то элемент, очень быстро. В этом случае алгоритм, похожий на ваш, скорее всего, будет самым быстрым.

Answer 5

Это мой (под сильным влиянием D.Jennings) родовое реализация метода сравнения (в 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; 
    } 
} 

Answer 6

Вы можете использовать Hashset. Посмотрите на метод SetEquals.

Answer 7

Существует много решений этой проблемы. Если вам не нужны дубликаты, вам не нужно сортировать их. Сначала убедитесь, что у них одинаковое количество элементов. После этого есть одна из коллекций. Затем binsearch каждый элемент из второго набора в отсортированной коллекции. Если вы не обнаружите, что данный пункт остановлен и возвращает false. Сложность этого: - сортировка первая коллекция: N Log (N) - поиск каждого элемента из второй в первую: N LOG (N) , так что вы в конечном итоге с 2 * N * LOG (N) предполагая, что они совпадают, и вы все смотрите. Это похоже на сложность сортировки обоих. Кроме того, это дает вам преимущество остановиться раньше, если есть разница. Однако имейте в виду, что если оба они отсортированы до того, как вы перейдете на это сравнение, и попробуйте сортировать, используя что-то вроде qsort, сортировка будет дороже. Для этого есть оптимизация. Другая альтернатива, которая отлично подходит для небольших коллекций, где вы знаете диапазон элементов, заключается в использовании индекса битовой маски. Это даст вам производительность O (n). Другой вариант - использовать хэш и посмотреть его. Для небольших коллекций обычно намного лучше выполнять сортировку или индекс битовой маски. Hashtable имеет недостаток в худшем месте, поэтому имейте это в виду. Опять же, это только если вам не нужны дубликаты. Если вы хотите учитывать дубликаты, перейдите к сортировке обоих.

Answer 8

EDIT: Я понял, как только я поставил, что это действительно работает только для множеств - он не будет иметь дело с коллекциями с дублирующими элементами. Например, {1, 1, 2} и {2, 2, 1} будут считаться равными с точки зрения этого алгоритма. Однако, если ваши коллекции являются наборами (или их равенство можно измерить таким образом), я надеюсь, что вы найдете ниже полезное.

Решение я использую:

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

Linq делает словарную вещь под одеялом, так что это также O (N). (Обратите внимание: это O (1), если коллекции не одного размера).

Я проверил проверку работоспособности, используя метод «SetEqual», предложенный Даниэлем, метод OrderBy/SequenceEquals, предложенный Игорем, и мое предложение. Ниже приведены результаты, показывающие O (N * LogN) для Игоря и O (N) для моего и Даниэля.

Я думаю, что простота кода пересечения Linq делает его предпочтительным решением.

__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 

Answer 9

В случае отсутствия повторов и не в порядке, следующие EqualityComparer могут быть использованы, чтобы позволить коллекции в качестве ключей словаря:

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

Here является реализация ToHashSet() я использовал. hash code algorithm - это эффективная Java (через Jon Skeet).

Answer 10

Повторяющееся сообщение, но check out my solution for comparing collections. Это довольно просто:

Это будет выполнять сравнение равенства, независимо от того:

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

Это будет проверять, чтобы увидеть, если были добавлены элементы/удалены:

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 

Это будет увидеть, какие элементы в словарь изменен:

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 

Оригинальный пост here.

Answer 11

Почему бы не использовать.За исключением()

// 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

Answer 12

Вот мой метод расширения вариант ответа ohadsc, в в случае, если это кому-то пригодится

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

Answer 13

Во многих случаях единственным подходящим ответом является один Игоря Островского , другие ответы основаны на хеш-коде объектов. Но при генерации хэш-кода для объекта вы делаете это только на основании его неизменяемых полей - таких как объект поля Id (в случае объекта базы данных) - Why is it important to override GetHashCode when Equals method is overridden?

Это означает, что, если сравнить две коллекции , результат может быть справедливым для метода сравнения, даже если поля разных элементов не равны. Для глубокого сравнения коллекций вам необходимо использовать метод Игоря и реализовать IEqualirity.

Пожалуйста, прочтите комментарии меня и mr.Schnider на его наиболее голосовавшие пост.

Джеймс

Answer 14

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

Решение требует .NET 3.5 и System.Collections.Generic пространства имен. According to Microsoft, SymmetricExceptWith является O (N + M) операции с п, представляющее количество элементов в первом наборе и м, представляющее количество элементов в секунду. При необходимости вы всегда можете добавить сопоставитель равенства к этой функции.

Answer 15

Вот решение, которое является улучшением по сравнению this one.

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

Answer 16

Если вы используете Shouldly, вы можете использовать ShouldAllBe с Содержит.

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

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

И, наконец, вы можете написать расширение.

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

ОБНОВЛЕНИЕ

А Опциональный параметр существует на ShouldBe метода.

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