Comparando duas collections para igualdade, independentemente da ordem dos itens nelas

Eu gostaria de comparar duas collections (em c #), mas não tenho certeza da melhor maneira de implementar isso de forma eficiente.

Eu li o outro tópico sobre Enumerable.SequenceEqual , mas não é exatamente o que estou procurando.

No meu caso, duas collections seriam iguais se ambas contiverem os mesmos itens (não importando a ordem).

Exemplo:

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

O que eu costumo fazer é percorrer cada item de uma coleção e ver se ela existe na outra coleção, depois percorrer cada item da outra coleção e ver se ela existe na primeira coleção. (Eu começo comparando os comprimentos).

 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 

No entanto, isso não é totalmente correto, e provavelmente não é a maneira mais eficiente de comparar duas collections por igualdade.

Um exemplo que posso pensar que seria errado é:

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

Qual seria o mesmo com a minha implementação. Devo apenas contar o número de vezes que cada item é encontrado e me certificar de que as contagens são iguais nas duas collections?


Os exemplos estão em algum tipo de C # (vamos chamá-lo de pseudo-C #), mas dê sua resposta em qualquer idioma que você desejar, não importa.

Nota: Eu usei inteiros nos exemplos para simplificar, mas eu quero poder usar objects de tipo de referência também (eles não se comportam corretamente como chaves porque somente a referência do object é comparada, não o conteúdo).

Acontece que a Microsoft já tem isso coberto em sua estrutura de testes: CollectionAssert . ÉEquivalent

Observações

Duas collections são equivalentes se tiverem os mesmos elementos na mesma quantidade, mas em qualquer ordem. Os elementos são iguais se seus valores forem iguais, não se se referirem ao mesmo object.

Usando o reflector, modifiquei o código por trás de AreEquivalent () para criar um comparador de igualdade correspondente. É mais completo do que as respostas existentes, uma vez que leva em conta nulos, implementa o IEqualityComparer e tem algumas verificações de eficiência e de caso de borda. Além disso, é a Microsoft 🙂

 public class MultiSetComparer : IEqualityComparer> { private readonly IEqualityComparer m_comparer; public MultiSetComparer(IEqualityComparer comparer = null) { m_comparer = comparer ?? EqualityComparer.Default; } public bool Equals(IEnumerable first, IEnumerable second) { if (first == null) return second == null; if (second == null) return false; if (ReferenceEquals(first, second)) return true; if (first is ICollection firstCollection && second is ICollection secondCollection) { if (firstCollection.Count != secondCollection.Count) return false; if (firstCollection.Count == 0) return true; } return !HaveMismatchedElement(first, second); } private bool HaveMismatchedElement(IEnumerable first, IEnumerable 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 GetElementCounts(IEnumerable enumerable, out int nullCount) { var dictionary = new Dictionary(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 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; } } 

Uso da amostra:

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

Ou se você quiser apenas comparar duas collections diretamente:

 var comp = new MultiSetComparer(); 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 

Finalmente, você pode usar seu comparador de igualdade de sua escolha:

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

Uma solução simples e bastante eficiente é ordenar as duas collections e depois compará-las por igualdade:

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

Esse algoritmo é O (N * logN), enquanto sua solução acima é O (N ^ 2).

Se as collections tiverem certas propriedades, você poderá implementar uma solução mais rápida. Por exemplo, se as duas collections forem conjuntos de hash, elas não poderão conter duplicatas. Além disso, verificar se um conjunto hash contém algum elemento é muito rápido. Nesse caso, um algoritmo semelhante ao seu provavelmente seria o mais rápido.

Crie um dictionary “dict” e, em seguida, para cada membro da primeira coleção, do dict [member] ++;

Em seguida, faça um loop sobre a segunda coleção da mesma maneira, mas para cada membro do dict [membro] -.

No final, faça um loop sobre todos os membros no dictionary:

  private bool SetEqual (List left, List right) { if (left.Count != right.Count) return false; Dictionary dict = new Dictionary(); 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 kvp in dict) { if (kvp.Value != 0) return false; } return true; } 

Edit: Tanto quanto eu posso dizer isso é na mesma ordem que o algoritmo mais eficiente. Este algoritmo é O (N), assumindo que o Dicionário usa pesquisas O (1).

Esta é a minha implementação genérica (fortemente influenciada por D.Jennings) do método de comparação (em C #):

 ///  /// Represents a service used to compare two collections for equality. ///  /// The type of the items in the collections. public class CollectionComparer { ///  /// Compares the content of two collections for equality. ///  /// The first collection. /// The second collection. /// True if both collections have the same content, false otherwise. public bool Execute(ICollection foo, ICollection bar) { // Declare a dictionary to count the occurence of the items in the collection Dictionary itemCounts = new Dictionary(); // 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 keys = new List(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; } } 

Você poderia usar um Hashset . Veja o método SetEquals .

EDIT: percebi logo que posou que isso realmente só funciona para conjuntos – não irá lidar adequadamente com collections que têm itens duplicados. Por exemplo, {1, 1, 2} e {2, 2, 1} serão considerados iguais da perspectiva deste algoritmo. Se suas collections são conjuntos (ou sua igualdade pode ser medida dessa forma), no entanto, espero que você ache útil a seguir.

A solução que uso é:

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

Linq faz o dictionary sob as capas, então isso também é O (N). (Note, é O (1) se as collections não são do mesmo tamanho).

Eu fiz uma verificação de sanidade usando o método “SetEqual” sugerido por Daniel, o método OrderBy / SequenceEquals sugerido por Igor, e minha sugestão. Os resultados estão abaixo, mostrando O (N * LogN) para Igor e O (N) para o meu e o de Daniel.

Eu acho que a simplicidade do código de interseção Linq torna a solução preferível.

 __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 

No caso de nenhuma repetição e nenhuma ordem, o EqualityComparer a seguir pode ser usado para permitir collections como chaves de dictionary:

 public class SetComparer : IEqualityComparer> where T:IComparable { public bool Equals(IEnumerable first, IEnumerable second) { if (first == second) return true; if ((first == null) || (second == null)) return false; return first.ToHashSet().SetEquals(second); } public int GetHashCode(IEnumerable enumerable) { int hash = 17; foreach (T val in enumerable.OrderBy(x => x)) hash = hash * 23 + val.GetHashCode(); return hash; } } 

Aqui está a implementação ToHashSet () que usei. O algoritmo de código de hash vem de Java efetivo (por meio de Jon Skeet).

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

A solução requer o .NET 3.5 e o namespace System.Collections.Generic . Segundo a Microsoft , SymmetricExceptWith é uma operação O (n + m) , com n representando o número de elementos no primeiro conjunto e m representando o número de elementos no segundo. Você sempre pode adicionar um comparador de igualdade a essa function, se necessário.

Por que não usar .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 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/pt-br/library/bb397894.aspx

Um post duplicado, mas confira minha solução para comparar collections . É bem simples:

Isso executará uma comparação de igualdade, independentemente da ordem:

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

Isso verificará se os itens foram adicionados / removidos:

 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 

Isto irá ver quais itens no dictionary mudaram:

 var original = new Dictionary() { { 1, "a" }, { 2, "b" } }; var changed = new Dictionary() { { 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 

Postagem original aqui .

Erickson está quase certo: desde que você queira combinar na contagem de duplicatas, você quer um saco . Em Java, isso parece algo como:

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

Tenho certeza de que o C # possui uma implementação do conjunto interna. Eu usaria isso primeiro; Se o desempenho for um problema, você poderá sempre usar uma implementação Set diferente, mas usar a mesma interface Set.

Aqui está a minha variante de método de extensão da resposta de ohadsc, no caso de ser útil para alguém

 static public class EnumerableExtensions { static public bool IsEquivalentTo(this IEnumerable first, IEnumerable 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(first, second)) return false; } return true; } private static bool HaveMismatchedElement(IEnumerable first, IEnumerable second) { int firstCount; int secondCount; var firstElementCounts = GetElementCounts(first, out firstCount); var secondElementCounts = GetElementCounts(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 GetElementCounts(IEnumerable enumerable, out int nullCount) { var dictionary = new Dictionary(); 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(IEnumerable enumerable) { int hash = 17; foreach (T val in enumerable.OrderBy(x => x)) hash = hash * 23 + val.GetHashCode(); return hash; } } 

Aqui está uma solução que é uma melhoria em relação a esta .

 public static bool HasSameElementsAs( this IEnumerable first, IEnumerable second, IEqualityComparer 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]); } 

Se você usar Shouldly , você pode usar ShouldAllBe com Contains.

 collection1 = {1, 2, 3, 4}; collection2 = {2, 4, 1, 3}; collection1.ShouldAllBe(item=>collection2.Contains(item)); // true 

E finalmente, você pode escrever uma extensão.

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

ATUALIZAR

Um parâmetro opcional existe no método ShouldBe .

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

Existem muitas soluções para esse problema. Se você não se importa com duplicatas, não precisa ordenar as duas coisas. Primeiro, certifique-se de que eles tenham o mesmo número de itens. Depois desse tipo uma das collections. Em seguida, binsearch cada item da segunda coleção na coleção ordenada. Se você não encontrar um determinado item, pare e retorne false. A complexidade disso: – classificar a primeira coleção: N Log (N) – pesquisando cada item de segundo para o primeiro: N LOG (N) então você acaba com 2 * N * LOG (N) assumindo que eles combinam e você procure tudo. Isso é semelhante à complexidade de classificar os dois. Isso também lhe dá o benefício de parar mais cedo se houver uma diferença. No entanto, tenha em mente que, se ambos forem classificados antes de você entrar nessa comparação e tentar classificar usando algo como um qsort, a sorting será mais cara. Existem otimizações para isso. Outra alternativa, que é ótima para pequenas collections onde você conhece o intervalo dos elementos, é usar um índice de bitmask. Isso lhe dará um desempenho O (n). Outra alternativa é usar um hash e procurá-lo. Para pequenas collections, geralmente é muito melhor fazer a sorting ou o índice de bitmask. Hashtable tem a desvantagem de pior localidade, então tenha isso em mente. Novamente, isso é somente se você não se importa com duplicatas. Se você deseja contabilizar os duplicados, classifique os dois.

Em muitos casos, a única resposta adequada é a de Igor Ostrovsky, outras respostas são baseadas em código de hash de objects. Mas quando você gera um código hash para um object, ele faz isso apenas com base em seus campos IMMUTABLE – como o campo Id do object (no caso de uma entidade de database) – Por que é importante replace GetHashCode quando o método Equals é substituído?

Isso significa que, se você comparar duas collections, o resultado poderá ser verdadeiro para o método de comparação, mesmo que os campos dos diferentes itens não sejam iguais. Para comparar as collections, você precisa usar o método de Igor e implementar o IEqualirity.

Por favor, leia os comentários de mim e mr.Schnider em seu post mais votado.

James

Permitindo duplicatas no IEnumerable (se os conjuntos não são desejáveis ​​\ possível) e “ignorando o pedido”, você deve ser capaz de usar um .GroupBy() .

Não sou especialista em medições de complexidade, mas minha compreensão rudimentar é que isso deve ser O (n). Eu entendo O (n ^ 2) como vindo de executar uma operação O (n) dentro de outra operação O (n) como ListA.Where(a => ListB.Contains(a)).ToList() . Cada item na ListB é avaliado quanto à igualdade em relação a cada item na ListA.

Como eu disse, meu entendimento sobre a complexidade é limitado, então me corrija se eu estiver errado.

 public static bool IsSameAs(this IEnumerable source, IEnumerable target, Expression> 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; }