Comparação de duas coleções para a igualdade, independentemente da ordem de itens
https://stackoverflow.com/questions/50098
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu gostaria de comparar duas coleções (em C#), mas não tenho a certeza de que a melhor forma de implementar esta forma eficiente.
Eu li o outro thread sobre Enumeráveis.SequenceEqual, mas ele não é exatamente o que eu estou procurando.
No meu caso, duas coleções seria igual se eles contêm os mesmos itens (não importa 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 ele existe na outra coleção, em seguida, um loop através de cada item da coleção e ver se ele existe na primeira coleta.(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 é inteiramente correto, e provavelmente não é a maneira mais eficiente de fazer comparar duas coleções para a igualdade.
Um exemplo que eu posso pensar que seria errado é:
collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}
O que seria igual com a minha implementação.Eu deveria apenas contar o número de vezes que cada item é encontrado e certifique-se de que as contagens são iguais em ambas as coleções?
Os exemplos estão em algum tipo de C# (vamos chamá-lo de pseudo-C#), mas dê a sua resposta, no idioma que você deseja, não importa.
Nota: Eu usei inteiros nos exemplos de simplicidade, mas eu quero ser capaz de usar de referência-tipo de objetos muito (eles não se comportam corretamente como chaves, porque apenas a referência para o objeto é comparado, não o conteúdo).
Solução
Acontece que a Microsoft já tem esta coberto em seu quadro de testes: CollectionAssert.AreEquivalent
Comentários
Dois conjuntos são equivalentes se eles tem os mesmos elementos na mesma a quantidade, mas em qualquer ordem.Elementos são iguais, se os seus valores forem iguais, não se referem ao mesmo objeto.
Usando refletor, eu modifiquei o código por trás de AreEquivalent() para criar um correspondente comparador de igualdade.Ele é mais completo do que o existente respostas, uma vez que leva nulos em conta, implementa IEqualityComparer e tem algumas eficiência e da borda do caso de cheques.além disso, é 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;
}
}
Exemplo de uso:
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
Ou se você apenas deseja comparar duas coleções diretamente:
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
Finalmente, você pode usar o seu igualdade comparador de sua escolha:
var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true
Outras dicas
Uma simples e bastante eficiente solução é classificar ambas as coleções e, em seguida, compará-los para a igualdade:
bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));
Este algoritmo é O(N*logN), enquanto a solução acima é de O(N^2).
Se as coleções têm determinadas propriedades, você pode ser capaz de implementar uma solução mais rápida.Por exemplo, se ambas as coleções são hash conjuntos, eles não podem conter valores duplicados.Além disso, verificar se um hash conjunto contém algum elemento, é muito rápido.Nesse caso, um algoritmo semelhante ao seu, provavelmente seria mais rápido.
Criar um Dicionário "dict" e, em seguida, para cada membro, na primeira coleta, fazer dict[membro]++;
Em seguida, um loop sobre a segunda coleção da mesma maneira, mas para cada membro dict[membro]--.
No final, fazer um loop através de todos os membros no dicionário:
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;
}
Editar:Tanto quanto eu posso dizer que isso é da mesma ordem como o mais eficiente do algoritmo.Este algoritmo é O(N), supondo-se que o Dicionário que usa O(1) as pesquisas.
Este é o meu (fortemente influenciado por D. Jennings) implementação genérica do método de comparação (em 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;
}
}
EDITAR:Eu percebi logo que eu colocava que isso realmente funciona apenas para conjuntos -- ele não lidar adequadamente com as coleções de itens duplicados.Por exemplo, { 1, 1, 2 } e { 2, 2, 1 } será considerado igual a partir deste algoritmo perspectiva.Se suas coleções são conjuntos (ou de sua igualdade pode ser medido de que maneira), no entanto, eu espero que você encontre abaixo útil.
A solução que eu uso é:
return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;
Linq o dicionário coisa sob o cobre, de modo que este também é O(N).(Observe, é O(1) se as coleções não são do mesmo tamanho).
Eu fiz uma verificação de sanidade usando o "SetEqual" método sugerido por Daniel, o OrderBy/SequenceEquals método sugerido pelo Igor, e a minha sugestão.Os resultados estão abaixo, mostrando O(N*LogN) para o Igor e O(N) para meu e do Daniel.
Eu acho que a simplicidade do Linq se cruzam código torna-se 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 não se repete e sem ordem, as seguintes EqualityComparer pode ser usado para permitir coleções como chaves de dicionário:
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;
}
}
Aqui é o ToHashSet() implementação utilizada.O hash do código de algoritmo vem Eficaz Java (por meio de Jon Skeet).
static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
var setXOR = new HashSet<T>(set1);
setXOR.SymmetricExceptWith(set2);
return (setXOR.Count == 0);
}
Solução requer .NET 3.5 e o System.Collections.Generic espaço de nomes. De acordo com a Microsoft, SymmetricExceptWith é um O(n + m) a operação, com n representando o número de elementos do primeiro conjunto e m representando o número de elementos na segunda.Você sempre pode adicionar uma igualdade comparador para esta função, se necessário.
Por que não usar .Exceto()
// 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);
Se você usar Shouldly, você pode usar ShouldAllBe com o Contém.
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<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
{
list.ShouldAllBe(l => equivalent.Contains(l));
}
}
ATUALIZAÇÃO
Um parâmetro opcional existe no ShouldBe o método.
collection1.ShouldBe(collection2, ignoreOrder: true); // true
Uma duplicata post do tipo, mas confira a minha solução para a comparação de coleções.É muito simples:
Isso irá realizar uma comparação de igualdade, independentemente de ordem:
var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;
Este irá 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 os itens no dicionário alterado:
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
Post Original aqui.
erickson é quase certo:desde que você deseja corresponder na conta de duplicatas, você quer um Saco.Em Java, isso se parece com algo como:
(new HashBag(collection1)).equals(new HashBag(collection2))
Eu tenho certeza que o C# tem um Conjunto integrado de implementação.Eu gostaria de usar em primeiro lugar;se o desempenho for um problema, você sempre pode usar um Conjunto diferente de implementação, mas usar a mesma configuração de interface.
Aqui está o meu método de extensão variante de ohadsc a resposta, no caso, é útil para alguém
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;
}
}
Aqui está uma solução que é uma melhoria em relação este.
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]);
}
Existem muitas soluções para esse problema.Se você não gosta de duplicatas, você não tem a classificação de ambos.Primeiro certifique-se de que eles têm o mesmo número de itens.Depois que classificar uma das coleções.Em seguida, binsearch cada item da segunda coleção na coleção classificada.Se você não encontrar um determinado item de parar e retornar false.A complexidade deste:- classificação da primeira coleção:NLog(N) - procurando em cada item da segunda para a primeira:NLOG(N) assim você acaba com 2*N*LOG(N), supondo-se que eles correspondem e você olhar para cima de tudo.Isso é semelhante a complexidade da classificação de ambos.Também este dá-lhe a vantagem de parar mais cedo se há uma diferença.No entanto, tenha em mente que, se ambos são classificados antes de você entrar nesta comparação e tentar a classificação por usar algo como um qsort, a classificação vai ser mais caro.Existem otimizações para isso.Outra alternativa, o que é ótimo para pequenas coleções de onde você conhece a gama de elementos é usar uma máscara de bits de índice.Isso dará a você um tempo O(n) o desempenho.Outra alternativa é a utilização de um hash e procure.Para coleções pequenas geralmente é muito melhor para fazer a ordenação ou a máscara de bits de índice.Hashtable tem a desvantagem de pior localidade de modo manter isso em mente.Novamente, isso é só se você não se preocupa em duplicatas.Se você deseja que a conta duplicatas ir com a classificação de ambos.
Em muitos casos, a única resposta adequada é a de Igor Ostrovsky , outras respostas são baseadas em objetos de código hash.Mas quando você gerar um código de hash para um objeto, você fazê-lo apenas com base em sua IMUTÁVEL campos - como objeto de campo de Identificação (no caso de uma entidade de banco de dados) - Por que é importante para substituir GetHashCode quando o método de Equals é substituído?
Isto significa que , se você comparar duas coleções , o resultado pode ser verdade de que o método de comparação, mesmo que os campos dos diferentes itens não são iguais .A profunda comparar coleções , você precisa usar Igor método e implementar IEqualirity .
Leia os comentários de mim e o senhor.Schnider sobre o seu mais votado para o cargo.
James
Permitindo a duplicatas a IEnumerable<T> (se define não são desejáveis\possível) e "ignorando a ordem" você deve ser capaz de usar um .GroupBy().
Eu não sou um especialista sobre a complexidade de medições, mas o meu entendimento rudimentar é de que este deve ser O(n).Eu entendo O(n^2) como proveniente da execução de uma operação O(n) dentro de outra operação O(n) como ListA.Where(a => ListB.Contains(a)).ToList().Cada item em Listab é avaliada para a igualdade em relação a cada item na ListA.
Como eu disse, o meu entendimento sobre a complexidade é limitado, então me corrija caso eu esteja errado.
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;
}
Esta simples solução força a IEnumerable's tipo genérico para implementar IComparable.Porque de
OrderBy's definição.
Se você não quiser fazer tal suposição, mas ainda quero usar essa solução, você pode usar o seguinte pedaço de código :
bool equal = collection1.OrderBy(i => i?.GetHashCode())
.SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));
