Desempenho durante a verificação de duplicatas

Question

Eu tenho trabalhado em um projeto onde eu preciso para percorrer uma coleção de dados e entradas remove onde a "chave primária" é duplicada. Eu tentei usar um

List<int>

e

Dictionary<int, bool>

Com o dicionário eu encontrei um desempenho ligeiramente melhor, embora eu nunca precisa do booleana marcados com cada entrada. Minha expectativa é que isso é porque uma lista permite o acesso indexado e um dicionário não. O que eu queria saber é, existe uma melhor solução para este problema. Eu não precisam de acesso as entradas novamente, eu só precisa acompanhar o que "as chaves primárias" Eu vi e me certificar de que só executar o trabalho além de entradas que têm uma nova chave primária. Eu estou usando C # e .NET 2.0. E eu não tenho controle sobre que fixa os dados de entrada para remover as duplicatas da fonte (infelizmente!). E assim você pode ter uma idéia de escala, no geral eu estou verificando para duplicatas cerca de 1.000.000 vezes na aplicação, mas em subconjuntos de não mais do que cerca de 64.000 que precisam ser único.

Answer 1

Eles acrescentaram a classe HashSet no .NET 3.5. Mas eu acho que vai ser a par com o dicionário. Se você tem menos do que dizer um 100 elementos de uma lista provavelmente terá um desempenho melhor.

Answer 2

Editar: o Nevermind o meu comentário. Achei que você está falando de C ++. Eu não tenho idéia se meu post é relevante no mundo do C # ..

Um hash-table poderia ser um pouco mais rápido. árvores binárias (que é o usado no dicionário) tendem a ser relativamente lento por causa da forma como a memória é acessada. Isto é especialmente verdadeiro se a sua árvore se torna muito grande.

No entanto, antes de mudar sua estrutura de dados, você já tentou usar um pool alocador personalizado para o seu dicionário? Aposto que o tempo não é gasto percorrer a árvore em si, mas na casa dos milhões de alocações e deallocations o dicionário vai fazer por você.

Você pode ver um fator de 10 velocidade-boost apenas ligar um simples alocador piscina para o modelo dicionário. Afaik impulso tem um componente que pode ser usado diretamente.

Outra opção: Se você sabe apenas 64.000 entradas em seus números inteiros existem você pode escrever os para um arquivo e criar uma função hash perfeito para ele. Dessa forma, você pode simplesmente usar a função hash para mapear seus números inteiros para o 0 a 64,000 gama e índice um pouco-matriz.

Provavelmente a maneira mais rápida, mas menos flexível. Você tem que refazer a sua função hash perfeita (pode ser feito automaticamente) cada vez que seu conjunto de inteiros alterações.

Answer 3

Eu não realmente o que você está pedindo.

Em primeiro lugar é exatamente o oposto do que você diz. O dicionário tem acesso indexado (é uma tabela hash), enquanto de Lista não tem.

Se você já tem os dados em um dicionário, em seguida, todas as chaves são únicas, não pode haver duplicatas.

Eu susspect você tem os dados armazenados em outro tipo de dados e você está armazenando-o no dicionário. Se for esse o caso, os inserindo os dados irá trabalhar com dois dictionarys.

foreach (int key in keys)
{
  if (!MyDataDict.ContainsKey(key))
  {
    if (!MyDuplicatesDict.ContainsKey(key))
      MyDuplicatesDict.Add(key);
  }
  else
    MyDataDict.Add(key); 
}

Answer 4

Se você está verificando para a singularidade de inteiros, ea gama de números inteiros é constrangido o suficiente, então você pode simplesmente usar um array.

Para melhor embalagem você poderia implementar uma estrutura de dados bitmap (basicamente um conjunto, mas cada um int na matriz representa 32 ints no espaço chave usando 1 bit por chave). Dessa forma, se você número máximo é 1.000.000 você só precisa ~ 30.5KB de memória para a estrutura de dados.

Realiza de um bitmap seria O (1) (por cheque), que é difícil de bater.

Answer 5

Houve uma pergunta um pouco para trás na remover duplicatas de uma matriz. Para efeitos do desempenho questão não era muito de uma consideração, mas você pode querer dar uma olhada nas respostas, já que podem lhe dar algumas idéias. Além disso, eu poderia estar fora da base aqui, mas se você está tentando remover duplicatas a partir da matriz, em seguida, um comando LINQ como Enumerable.Distinct pode dar-lhe um melhor desempenho do que algo que você escrever sozinho. Como se vê, há uma maneira de obter LINQ trabalhando em .NET 2.0 então isso pode ser um valor de rota investigar.

Answer 6

Se você estiver indo para usar uma lista, use o BinarySearch:

 // initailize to a size if you know your set size
List<int> FoundKeys = new List<int>( 64000 );
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>();

foreach ( int Key in MyKeys )
{
   // this is an O(log N) operation
   int index = FoundKeys.BinarySearch( Key );
   if ( index < 0 ) 
   {
       // if the Key is not in our list, 
       // index is the two's compliment of the next value that is in the list
       // i.e. the position it should occupy, and we maintain sorted-ness!
       FoundKeys.Insert( ~index, Key );
   }
   else 
   {
       if ( DuplicateKeys.ContainsKey( Key ) )
       {
           DuplicateKeys[Key]++;
       }
       else
       {
           DuplicateKeys.Add( Key, 1 );
       }
   } 
} 

Você também pode usar isso para qualquer tipo para o qual você pode definir um IComparer usando uma sobrecarga: BinarySearch (ponto T, IComparer );