Maneira mais rápida de descobrir se duas coleções iCollection contêm os mesmos objetos

Question

Qual é a maneira mais rápida de descobrir se dois ICollection<T> As coleções contêm com precisão as mesmas entradas? A força bruta é clara, eu queria saber se existe um método mais elegante.

Estamos usando o C# 2.0, portanto, não há métodos de extensão, se possível, por favor!

EDIT: A resposta seria interessante para coleções ordenadas e não ordenadas, e esperamos ser diferentes para cada uma.

Answer 1

Use C5

http://www.itu.dk/research/c5/

Containsl

"Verifique se todos os itens de uma coleção fornecida estão nesta bolsa
(Contando multiplicidades).
Os itens a serem procurados.

É verdade que todos os itens forem encontrados. "

[Tested]

public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T
{
  HashBag<T> res = new HashBag<T>(itemequalityComparer);

  foreach (T item in items)
    if (res.ContainsCount(item) < ContainsCount(item))
      res.Add(item);
    else
      return false;

  return true;
}

Answer 2

Primeiro compare o.Contar Das coleções se elas tiverem a mesma contagem, a força bruta se compara em todos os elementos. O pior dos cenários é O (n). Isso ocorre no caso de a ordem dos elementos precisa ser a mesma.

O segundo caso em que a ordem não é a mesma, você precisa usar um dicionário para armazenar a contagem de elementos encontrados nas coleções: aqui está um possível algoritmo

• Compare a contagem de coleções: retorne falsa se forem diferentes
• Itera a primeira coleção
  • Se o item não existir no dicionário, adicione e entrada com key = item, valor = 1 (a contagem)
  • Se o item existir incremento a contagem do item no dicionário;
• Itera a segunda coleção
  • Se o item não estiver no dicionário, o retorno falso
  • Se o item estiver na contagem de decréscios do dicionário para o item
    • Se count == 0 o item remover;
• retornar dicionário.count == 0;

Answer 3

Para coleções ordenadas, você pode usar o SequenceEqual() Método de extensão definido por System.Linq.Enumerable:

if (firstCollection.SequenceEqual(secondCollection))

Answer 4

Você quer dizer as mesmas entradas ou as mesmas entradas na mesma ordem?

De qualquer forma, supondo que você queira comparar se eles contêm as mesmas entradas na mesma ordem, "Força Brute" é realmente sua única opção no C# 2.0. Eu sei o que você quer dizer com não elegante, mas se a própria comparação atômica é O (1), todo o processo deve estar em O (n), o que não é este mau.

Answer 5

Se as entradas precisarem estar na mesma ordem (além de serem as mesmas), sugiro - como uma otimização - que você itera as duas coleções ao mesmo tempo e compare a entrada atual em cada coleção. Caso contrário, a força bruta é o caminho a percorrer.

Ah, e outra sugestão - você pode substituir iguais para a classe de coleta e implementar o material da igualdade lá (depende do projeto).

Answer 6

Novamente, usando a biblioteca C5, com dois conjuntos, você pode usar:

C5.ICollection<T> set1 = C5.ICollection<T> ();
C5.ICollection<T> set2 = C5.ICollecton<T> ();
if (set1.UnsequencedEquals (set2)) {
  // Do something
}

A biblioteca C5 inclui uma heurística que realmente testa os códigos de hash não sequenciados dos dois sets primeiro (ver C5.ICollection<T>.GetUnsequencedHashCode()) para que, se os códigos de hash dos dois conjuntos forem desiguais, ele não precisará iterar em todos os itens para testar a igualdade.

Também algo de nota para você é que C5.ICollection<T> herda de System.Collections.Generic.ICollection<T>, para que você possa usar as implementações C5 enquanto ainda estiver usando as interfaces .NET (embora você tenha acesso a menos funcionalidade através das interfaces mesquinhas do .NET).

Answer 7

A força bruta toma O (n) - comparando todos os elementos (supondo que sejam classificados), o que eu acho que é o melhor que você poderia fazer - a menos que haja alguma propriedade dos dados que facilitam.

Eu acho que, para o caso de não ser classificado, seu O (n*n).

Nesse caso, eu pensaria uma solução baseada em um mesclar classificar provavelmente ajudaria.

Por exemplo, você poderia modelá-lo novamente para que houvesse apenas uma coleção? Ou 3 coleções, uma para aquelas apenas na coleção A, apenas uma para B e para ambos - então, se apenas a A e B estiverem vazios - então eles são iguais ... provavelmente estou saindo totalmente da tangente errada aqui...