Comparando duas coleções para igualdade, independentemente da ordem dos itens nelas

162

Gostaria de comparar duas coleções (em C #), mas não tenho certeza da melhor maneira de implementar isso com eficiência.

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

No meu caso, duas coleções seriam iguais se ambas contivessem 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 existe na outra coleção, depois percorrer cada item da outra coleção e ver se existe na primeira coleção. (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 está totalmente correto e provavelmente não é a maneira mais eficiente de comparar duas coleções de igualdade.

Um exemplo em que posso pensar que seria errado é:

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

O que seria igual à minha implementação. Devo apenas contar o número de vezes que cada item é encontrado e garantir que as contagens sejam iguais nas duas coleções?


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

Nota: Eu usei números inteiros nos exemplos por simplicidade, mas quero poder usar objetos do tipo referência também (eles não se comportam corretamente como chaves porque apenas a referência do objeto é comparada, não o conteúdo).

mbillard
fonte
1
E o algoritmo? Todas as respostas estão relacionadas por comparar algo, listas genéricas comparam linq etc. Realmente prometemos a alguém que nunca usaremos o algoritmo como um programador antiquado?
Nuri YILMAZ
Você não está verificando a Igualdade, mas sim a Equivalência. É nitpicky, mas uma distinção importante. E há muito tempo. Este é um bom Q + A.
Bloke CAD 23/03/15
Você pode estar interessado nesta postagem , que discute uma versão ajustada do método baseado em dicionário descrito abaixo. Um problema com a maioria das abordagens simples de dicionário é que elas não tratam nulos corretamente porque a classe Dictionary do .NET não permite chaves nulas.
ChaseMedallion

Respostas:

112

Acontece que a Microsoft já abordou isso em sua estrutura de teste: CollectionAssert.AreEquivalent

Observações

Duas coleções 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 eles se referirem ao mesmo objeto.

Usando o refletor, modifiquei o código por trás de AreEquivalent () para criar um comparador de igualdade correspondente. É mais completo que as respostas existentes, uma vez que leva em consideração os nulos, implementa o IEqualityComparer e possui algumas verificações de eficiência e de casos extremos. além disso, é a 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;
    }
}

Uso da amostra:

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ê quiser 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

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

var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true
Ohad Schneider
fonte
7
Não tenho 100% de certeza, mas acho que sua resposta viola os termos de uso da Microsoft contra a engenharia reversa.
9302 Ian Dallas
1
Olá Ohad, Leia o longo debate a seguir no tópico stackoverflow.com/questions/371328/… Se você alterar o código hash do objeto, enquanto estiver em um hashset, ele será interrompido com a ação apropriada do hashset e poderá causar uma exceção. A regra é a seguinte: Se dois objetos são iguais - eles devem ter o mesmo código de hash. Se dois objetos têm o mesmo código hash - não é obrigatório que sejam iguais. O código hash deve permanecer o mesmo durante toda a vida útil do objeto! É por isso que você impulsiona ICompareable e IEqualrity.
James Roeiter
2
@ JamesRoeiter Talvez meu comentário tenha sido enganador. Quando um dicionário encontra um código hash que ele já contém, ele verifica a igualdade real com um EqualityComparer(o que você forneceu ou EqualityComparer.Defaultvocê pode verificar o Reflector ou a fonte de referência para verificar isso). É verdade que, se os objetos mudarem (e especificamente o seu código de hash) mudar enquanto esse método estiver em execução, os resultados serão inesperados, mas isso significa que esse método não é seguro para threads nesse contexto.
Ohad Schneider 02/02
1
@JamesRoeiter Suponha que xey sejam dois objetos que queremos comparar. Se eles tiverem códigos de hash diferentes, sabemos que eles são diferentes (porque itens iguais têm códigos de hash iguais) e a implementação acima está correta. Se eles tiverem o mesmo código hash, a implementação do dicionário verificará a igualdade real usando o especificado EqualityComparer(ou EqualityComparer.Defaultse nenhum foi especificado) e, novamente, a implementação está correta.
Ohad Schneider
1
@CADbloke, o método deve ser nomeado Equalspor causa da IEqualityComparer<T>interface. O que você deve observar é o nome do próprio comparador . Nesse caso, é o MultiSetComparerque faz sentido.
Ohad Schneider
98

Uma solução simples e bastante eficiente é classificar as duas coleções e compará-las para 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 coleções tiverem certas propriedades, você poderá implementar uma solução mais rápida. Por exemplo, se as duas coleções forem conjuntos de hash, elas não poderão conter duplicatas. Além disso, verificar se um conjunto de hash contém algum elemento é muito rápido. Nesse caso, um algoritmo semelhante ao seu provavelmente seria o mais rápido.

Sani Singh Huttunen
fonte
1
Você apenas precisa adicionar um using System.Linq; primeiro a fazê-lo funcionar
Junior Mayhé 21/05
se esse código estiver dentro de um loop e a coleção1 for atualizada e a coleção2 permanecer intocada, observe que mesmo quando as duas coleções tiverem o mesmo objeto, o depurador mostrará false para essa variável "igual".
Junior Mayhé
5
@ Chaulky - Eu acredito que o OrderBy é necessário. Veja: dotnetfiddle.net/jA8iwE
Brett
Qual foi a outra resposta referida como "acima"? Possivelmente stackoverflow.com/a/50465/3195477 ?
UuDdLrLrSs 11/12/19
32

Crie um dicionário "dict" e, em seguida, para cada membro da primeira coleção, faça dict [member] ++;

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

No final, faça um loop sobre todos os membros do 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;

    }

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

Daniel Jennings
fonte
Isso é quase o que eu quero. No entanto, eu gostaria de poder fazer isso mesmo se não estiver usando números inteiros. Eu gostaria de usar objetos de referência, mas eles não se comportam corretamente como chaves nos dicionários.
mbillard
Mono, sua pergunta é discutível se seus itens não são comparáveis. Se eles não puderem ser usados ​​como chaves no Dicionário, não há solução disponível.
Skolima 16/09/08
1
Acho que Mono significava que as chaves não são classificáveis. Mas a solução de Daniel claramente se destina a ser implementada com uma tabela de hash, não uma árvore, e funcionará desde que exista um teste de equivalência e uma função de hash.
Erickson
Promovido, é claro, pela ajuda, mas não aceito, pois está faltando um ponto importante (que abordarei na minha resposta).
mbillard
1
FWIW, você pode simplificar o seu loop foreach passado e instrução de retorno com este:return dict.All(kvp => kvp.Value == 0);
Tyson Williams
18

Esta é minha implementação genérica (fortemente influenciada por D.Jennings) 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;
    }
}
mbillard
fonte
12
Bom trabalho, mas Nota: 1. Ao contrário da solução de Daniel Jennings, isso não é O (N), mas O (N ^ 2), devido à função find dentro do loop foreach na coleção de barras; 2. Você pode generalizar o método de aceitar IEnumerable <T> em vez de ICollection <T> sem qualquer modificação no código
Ohad Schneider
The keys of a dictionary are compared by reference, so we have to find the original key that is equivalent to the "item"- isso não é verdade. O algoritmo é baseado em suposições erradas e, enquanto funciona, é terrivelmente ineficiente.
Antonín Lejsek
10

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

Joel Gauvreau
fonte
2
é claro, usando um HashSet assume nenhuma duplicata mas se assim for HashSet é o melhor caminho a percorrer
Mark Cidade
7

Se você usar o Shouldly , poderá usar o ShouldAllBe with 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<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
    {
        list.ShouldAllBe(l => equivalent.Contains(l));
    }
}

ATUALIZAR

Existe um parâmetro opcional no método ShouldBe .

collection1.ShouldBe(collection2, ignoreOrder: true); // true
Pier-Lionel Sgard
fonte
1
Acabei de descobrir na versão mais recente que existe um parâmetro bool ignoreOrderno método ShouldBe .
Pier-Lionel Sgard 14/11
5

Edição: Percebi, logo que afirmei, que isso realmente funciona apenas para conjuntos - ele não lidará adequadamente com coleções com itens duplicados. Por exemplo, {1, 1, 2} e {2, 2, 1} serão considerados iguais da perspectiva desse algoritmo. Se suas coleções são conjuntos (ou sua igualdade pode ser medida dessa maneira), espero que você ache o que é útil abaixo.

A solução que eu uso é:

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

O Linq faz o dicionário sob as cobertas, então isso também é O (N). (Observe que é O (1) se as coleções não tiverem o mesmo tamanho).

Fiz uma verificação de integridade 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 do Linq o 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

fonte
O único problema com esse código é que ele funciona apenas ao comparar tipos de valor ou comparar ponteiros com tipos de referência. Eu poderia ter duas instâncias diferentes do mesmo objeto nas coleções, portanto, preciso especificar como comparar cada uma. Você pode passar um delegado de comparação para o método de interseção?
mbillard
Claro, você pode passar um delegado comparador. Mas observe a limitação acima em relação aos conjuntos que adicionei, o que coloca um limite significativo em sua aplicabilidade.
O método Intersect retorna uma coleção distinta. Dado a = {1,1,2} eb = {2,2,1}, a.Intersect (b) .Count ()! = A.Count, que faz com que sua expressão retorne false corretamente. {1,2} .Count = {1,1,2} .Count Veja! Ligação [/ link] (Note-se que ambos os lados são feitos distintos antes de comparação.)
Griffin
5

No caso de sem repetições e sem ordem, o seguinte 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 está a implementação ToHashSet () que eu usei. O algoritmo de código hash vem do Java efetivo (por meio de Jon Skeet).

Ohad Schneider
fonte
Qual é o objetivo da classe Serializable for Comparer? : o Você também pode alterar a entrada para ISet<T>expressá-la para conjuntos (ou seja, sem duplicatas).
Nawfal
@nawfal obrigado, não sei o que eu estava pensando quando o marquei Serializable ... Quanto a ISet, a idéia aqui era tratar o IEnumerableconjunto (porque você tem um IEnumerablepara começar), apesar de considerar os 0 votos positivos em mais de 5 anos que podem não ter sido a ideia mais nítida: P
Ohad Schneider
4
static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
    var setXOR = new HashSet<T>(set1);
    setXOR.SymmetricExceptWith(set2);
    return (setXOR.Count == 0);
}

A solução requer o .NET 3.5 e o System.Collections.Genericespaço para nome. 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 função, se necessário.

palswim
fonte
3

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

Korayem
fonte
2
Exceptnão funcionará para contar itens duplicados. Retornará true para os conjuntos {1,2,2} e {1,1,2}.
Cristian Diaconescu 31/01
@CristiDiaconescu você poderia fazer um ".Distinct ()" primeiro para remover todas as duplicatas
Korayem
O OP está pedindo [1, 1, 2] != [1, 2, 2]. Usar os Distinctfaria parecer iguais.
Cristian Diaconescu
2

Uma publicação duplicada, mas confira minha solução para comparar coleções . É 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

Isso verá quais itens do dicionário foram alterados:

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 .

user329244
fonte
1

erickson está quase certo: como você deseja corresponder à contagem de duplicatas, você quer uma bolsa . Em Java, isso se parece com:

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

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

James A. Rosen
fonte
1

Aqui está minha variante do método de extensão da resposta do ohadsc, caso seja ú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;
    }
}
Eric J.
fonte
Quão bem isso funciona, alguma idéia?
Nawfal
Eu o uso apenas para coleções pequenas, por isso não pensei na complexidade do Big-O ou fiz testes comparativos. O HaveMismatchedElements sozinho é O (M * N), portanto, pode não ter um bom desempenho para coleções grandes.
Eric J.
Se IEnumerable<T>s são consultas, chamar Count()não é uma boa ideia. A abordagem da resposta original de Ohad para verificar se estão ICollection<T>é a melhor idéia.
Nawfal
1

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

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

Existem muitas soluções para esse problema. Se você não se importa com duplicatas, não precisa classificar as duas. Primeiro, verifique se eles têm o mesmo número de itens. Depois disso, classifique uma das coleções. Em seguida, pesquise cada item da segunda coleção na coleção classificada. Se você não encontrar um determinado item, pare e retorne false. A complexidade disso: - classificando a primeira coleção: N Log (N) - pesquisando cada item do segundo ao primeiro: NLOG (N) para que você termine com 2 * N * LOG (N) assumindo que eles coincidem e você procure tudo. Isso é semelhante à complexidade da classificação de ambos. Além disso, você tem o benefício de parar mais cedo, se houver alguma diferença. No entanto, lembre-se de que, se os dois forem classificados antes de você entrar nessa comparação e tentar classificar usando algo como um qsort, a classificação será mais cara. Existem otimizações para isso. Outra alternativa, que é ótima para pequenas coleções em que você conhece o intervalo dos elementos, é usar um índice de máscara de bit. Isso lhe dará um desempenho O (n). Outra alternativa é usar um hash e procurá-lo. Para coleções pequenas, geralmente é muito melhor fazer a classificação ou o índice de máscara de bit. Hashtable tem a desvantagem de pior localidade, portanto, tenha isso em mente. Novamente, isso é apenas se você não não me importo com duplicatas. Se você deseja contabilizar duplicatas, escolha a classificação de ambas.


fonte
0

Em muitos casos, a única resposta adequada é a de Igor Ostrovsky, outras respostas são baseadas no código de hash dos objetos. Mas quando você gera um código de hash para um objeto, você o faz apenas com base nos campos IMMUTABLE - como o campo Id do objeto (no caso de uma entidade do banco de dados) - Por que é importante substituir GetHashCode quando o método Equals é substituído?

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

Por favor, leia os comentários meus e do Sr. Schnider em seu post mais votado.

James

James Roeiter
fonte
0

Permitindo duplicatas na IEnumerable<T>(se os conjuntos não forem desejáveis ​​\ possíveis) e na "ordem de ignorância", você poderá usar a .GroupBy().

Não sou especialista em medidas de complexidade, mas meu entendimento rudimentar é que isso deve ser O (n). Entendo O (n ^ 2) como decorrente 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 na Lista B é avaliado quanto à igualdade em relação a cada item na Lista A.

Como eu disse, meu entendimento sobre complexidade é limitado, então me corrija se estiver 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;
    }
Josh Gust
fonte
0

Esta solução simples força o IEnumerabletipo genérico a ser implementado IComparable. Por causa da OrderBydefinição de.

Se você não deseja fazer essa suposição, mas ainda deseja usar esta solução, pode usar o seguinte trecho de código:

bool equal = collection1.OrderBy(i => i?.GetHashCode())
   .SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));
Jo Ham
fonte
0

Ao comparar com o objetivo de Unit Testing Assertions, pode fazer sentido lançar alguma eficiência pela janela e simplesmente converter cada lista em uma representação de string (csv) antes de fazer a comparação. Dessa forma, a mensagem de Asserção de teste padrão exibirá as diferenças na mensagem de erro.

Uso:

using Microsoft.VisualStudio.TestTools.UnitTesting;

// define collection1, collection2, ...

Assert.Equal(collection1.OrderBy(c=>c).ToCsv(), collection2.OrderBy(c=>c).ToCsv());

Método de extensão auxiliar:

public static string ToCsv<T>(
    this IEnumerable<T> values,
    Func<T, string> selector,
    string joinSeparator = ",")
{
    if (selector == null)
    {
        if (typeof(T) == typeof(Int16) ||
            typeof(T) == typeof(Int32) ||
            typeof(T) == typeof(Int64))
        {
            selector = (v) => Convert.ToInt64(v).ToStringInvariant();
        }
        else if (typeof(T) == typeof(decimal))
        {
            selector = (v) => Convert.ToDecimal(v).ToStringInvariant();
        }
        else if (typeof(T) == typeof(float) ||
                typeof(T) == typeof(double))
        {
            selector = (v) => Convert.ToDouble(v).ToString(CultureInfo.InvariantCulture);
        }
        else
        {
            selector = (v) => v.ToString();
        }
    }

    return String.Join(joinSeparator, values.Select(v => selector(v)));
}
crokusek
fonte