Prestazioni durante il controllo dei duplicati

Question

Ho lavorato su un progetto in cui ho bisogno di scorrere un insieme di dati e rimuovere le voci in cui la "chiave primaria" è duplicato.Ho provato con un

List<int>

e

Dictionary<int, bool>

Con il dizionario ho trovato leggermente migliore performance, anche se non ho mai bisogno di Boolean taggati con ogni voce.La mia aspettativa è che questo è a causa di un Elenco per l'accesso indicizzato e un Dizionario non.Quello che mi chiedevo è, c'è una soluzione migliore a questo problema.Non ho bisogno di accedere alle voci di nuovo, ho solo bisogno di tenere traccia di quali "chiavi primarie" ho visto e assicurarsi che l'ho solo eseguire addizioni lavoro sulle voci che hanno una nuova chiave primaria.Sto usando C# e .NET 2.0.E non ho alcun controllo su fissazione di dati di input per rimuovere i duplicati dalla sorgente (purtroppo!).E così si può avere un tatto per la scala, nel complesso sto controllando per i duplicati di circa 1.000.000 di volte la domanda, ma in sottoinsiemi di non più di circa 64.000 che devono essere univoci.

Answer 1

Hanno aggiunto la classe HashSet in .NET 3.5.Ma credo che sarà alla pari con il Dizionario.Se si dispone di meno di dire che un 100 elementi di un Elenco, sarà probabilmente fare di meglio.

Answer 2

Edit:Nevermind il mio commento.Ho pensato che tu stai parlando di C++.Non ho idea se il mio post è rilevante in C# mondo..

Una tabella hash potrebbe essere un po ' più veloce.Alberi binari (che è quello utilizzato nel dizionario) tendono a essere relativi a rilento a causa del modo in cui la memoria viene letta.Questo è particolarmente vero se il vostro albero diventa molto grande.

Tuttavia, prima di cambiare i vostri dati-struttura, hai provato ad usare un custom piscina allocatore per il tuo dizionario?Scommetto che il tempo non è passato l'attraversamento dell'albero in sé, ma in milioni di allocazioni e deallocazioni il dizionario è in grado di fare.

Si può vedere un fattore 10 velocità-boost basta collegare un semplice piscina allocatore nel dizionario modello.Afaik boost è un componente che può essere utilizzato direttamente.

Un'altra opzione:Se si conosce solo 64.000 voci interi esiste, è possibile scrivere a quelli di un file e creare una funzione di hash perfetta per farlo.In questo modo si può semplicemente utilizzare la funzione di hash per mappare i numeri interi in 0 a 64.000 gamma e indice di un array.

Probabilmente il modo più veloce, ma meno flessibile.È necessario ripristinare la funzione di hash perfetta (può essere eseguito automaticamente ogni volta che il set di numeri interi modifiche.

Answer 3

Non ho davvero ottenere quello che stai chiedendo.

In primo luogo è esattamente l'opposto di quello che dici.Il dizionario ha accesso indicizzato (è una tabella di hash), mentre de Lista non.

Se i dati sono già in un dizionario, tutti i tasti sono unici, non ci possono essere duplicati.

Ho susspect disporre di tutti i dati memorizzati in un altro tipo di dati e si memorizza nel dizionario.Se questo è il caso, l'inserimento dati e lavoro con due dictionarys.

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

Answer 4

Se si sta verificando per l'unicità di numeri interi, e l'intervallo di numeri interi è vincolata abbastanza allora si potrebbe utilizzare un array.

Per meglio imballaggio si potrebbe implementare una struttura di dati bitmap (in pratica un array, ma ogni int array rappresenta il 32 int il tasto spazio con l'uso di 1 bit per la chiave).In questo modo se un numero massimo di 1.000.000 hai solo bisogno di ~30.5 KB di memoria per la struttura dei dati.

Esegue una bitmap sarebbe O(1) (per controllare) che è difficile da battere.

Answer 5

C'è una domanda un po ' indietro su per la rimozione di duplicati da una matrice.Ai fini della domanda di prestazioni non era molto più di un corrispettivo, ma si potrebbe desiderare di dare un'occhiata alle risposte come potrebbe darvi alcune idee.Inoltre, potrei essere fuori base, ma se si sta tentando di rimuovere i duplicati da matrice, quindi un comando come LINQ Enumerabile.Distinti potrebbe dare prestazioni migliori rispetto a qualcosa che lei stesso ha scritto.A quanto pare c'è un modo per ottenere LINQ lavorando .NET 2.0 quindi questo potrebbe essere un percorso che vale la pena indagare.

Answer 6

Se avete intenzione di utilizzare un Elenco, utilizzare 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 );
       }
   } 
} 

È inoltre possibile utilizzare questo per qualsiasi tipo per il quale si può definire un IComparer utilizzando un sovraccarico:BinarySearch( T voce, IComparer< T > );