Una sostituzione più veloce al dizionario <TKey, TValue>

Question

Ho bisogno di una sostituzione rapida per il System.Collections.Generic.Dictionary<TKey, TValue>. La mia applicazione dovrebbe essere davvero veloce. Così, la sostituzione dovrebbe sostenere:

• Generics
• Aggiungi
• Diventa
• Contiene

... e il gioco è fatto. Non ho bisogno di alcun supporto in LINQ o altro. E dovrebbe essere veloce.

Un codice semplice come:

Stopwatch stopWatch = Stopwatch.StartNew(); 

Dictionary<string, string> dictionary = new Dictionary<string, string>(); 
dictionary.Add("fieldName", "fieldValue"); 
dictionary.Add("Title", "fieldVaaaaaaaaaaaaaaaaalue"); 

Console.WriteLine(stopWatch.Elapsed); 

... stampe 00: 00: 00,0001274, che è un sacco di tempo per me, perché la mia domanda sta facendo molte altre cose, alcuni dei quali provenienti da vecchio librerie lente che devo usare e non dipendono da me.

Qualche idea su come implementare uno più veloce?

Grazie.

Answer 1

È probabile che tu stia vedendo la compilation JIT. Sulla mia casella, vedo:

00:00:00.0000360 
00:00:00.0000060 

quando l'eseguo due volte in rapida successione all'interno dello stesso processo - e non nel debugger. (Assicurati di non eseguirlo nel debugger, o è un test inutile.)

Ora, misurare in qualsiasi momento che minuscolo è generalmente una cattiva idea. Dovresti eseguire l'iterazione milioni di volte per avere un'idea migliore di quanto tempo impiega.

Avete buone ragioni per credere che sia effettivamente rallentare il codice - o stai basando tutto sulla vostra sincronizzazione originale?

dubito che troverete qualcosa di molto più velocemente rispetto Dictionary<TKey, TValue> e sarei molto sorpreso di scoprire che è il collo di bottiglia.

EDIT: ho appena benchmark l'aggiunta di un milione di elementi per un Dictionary<TKey, TValue> dove tutte le chiavi erano di oggetti esistenti (le stringhe in un array), riutilizzando lo stesso valore (come è irrilevante) e specificando una capacità di un milione per la costruzione - e ci sono voluti circa 0,15 sul mio computer portatile di due anni.

È proprio questo il probabilmente un collo di bottiglia per te, visto che hai già detto che stai utilizzando alcune "vecchie librerie lente" altrove nella tua app? Tenete a mente che più lente sono le altre librerie, minore sarà l'impatto di una classe di raccolta migliorata. Se le modifiche al dizionario rappresentano solo l'1% del tempo complessivo di applicazione, anche se potessimo fornire un dizionario istantaneo , accelereresti la tua app dell'1%.

Come sempre, ottieni un profiler - ti darà un'idea migliore di dove sta andando il tuo tempo.

Answer 2

Sono d'accordo con supposizione Jon Skeet s' che questo è più probabile compilazione JIT.

Detto questo, ho voluto aggiungere alcune altre informazioni qui:

La maggior parte dei problemi di velocità relative all'utilizzo Dictionary<T,U> non sono legati alla realizzazione del dizionario. Dictionary<T,U> è MOLTO veloce, fuori dalla scatola. Sarebbe difficile batterlo.

I problemi di velocità relativi alle istanze del dizionario sono quasi sempre problemi di implementazione del codice hash. Se si verificano problemi di velocità durante l'utilizzo di, rivedere l'implementazione GetHashCode() definita in MyCustomClass. Questo è ancora più critico se stai usando una struttura personalizzata come chiave.

Al fine di ottenere buone prestazioni dal dizionario, GetHashCode() dovrebbe essere:

1. veloce
2. In grado di fornire i codici di hash che generano pochi conflitti. Le istanze univoche dovrebbero, quando possibile, generare valori hash univoci.

Se avete capito bene, penso che sarete molto soddisfatti dell'implementazione predefinita del dizionario.

Answer 3

Se davvero bisogno di migliorare le prestazioni, si sta andando ad avere per rinunciare a qualcosa di importante - come farmaci generici, allocazione dinamica della memoria, ecc Tutte queste caratteristiche sacrificano alcune prestazioni.

vorrei evitare di usare Contiene se possibile e guardare TryGetValue ecc

Answer 4

le probabilità sono che non stanno andando a trovare qualcosa di molto più veloce di dizionario. Vorrei solo usare il dizionario. Quindi, quando vedi che non raggiungi i tuoi obiettivi perf e un profiler indica che aggiungere/rimuovere dal dizionario sono i tuoi colli di bottiglia, puoi prendere in considerazione la sostituzione con una classe più mirata.

Si noti che funzionalità come LINQ non comportano alcuna perdita di prestazioni se non vengono utilizzate.

Answer 5

Non dimenticare, stai calcolando anche il costruttore del dizionario in quel codice. Ho fatto un test, trasferendo la chiamata al costruttore fuori dalla misurazione e ripetuta 10 volte. Ecco il mio codice di prova:

for (int i = 0; i < 10; i++) 
{ 
    Dictionary<string, string> test = new Dictionary<string, string>(); 

    System.Diagnostics.Stopwatch watch = System.Diagnostics.Stopwatch.StartNew(); 

    test.Add("fieldName", "fieldValue"); 
    test.Add("Title", "fieldavlkajlkdjflkjalkjslkdjfiajwelkrjelrkjavoijl"); 

    Console.WriteLine(watch.Elapsed); 
} 

Console.ReadKey(); 

Di seguito i risultati:

00:00:00.0000607 
00:00:00.0000025 
00:00:00.0000015 
00:00:00.0000015 
00:00:00.0000016 
00:00:00.0000017 
00:00:00.0000016 
00:00:00.0000016 
00:00:00.0000016 
00:00:00.0000015 

io non sono sicuro di quanto velocemente si potrebbe ottenere di così ...

Aggiornamento

Sembra che questo specchi sia anche Jon Skeets ... JIT.

Answer 6

Hai bisogno di un elenco e definire un enum tale che, per esempio, fieldName = 0, Title = 1 e utilizzare indice univoco di ogni propery come un indice di ricerca nella lista? Questa sarebbe la soluzione più veloce, anche se la meno flessibile dal momento che saresti legato a un enum.

Answer 7

Quanti elementi si prevede di aggiungere al dizionario?Mentre Dictionary/Hashtable è solitamente il più veloce, a seconda di quello che stai facendo, potrebbe esserci qualcosa di più veloce (meglio conosciuto) di un Hashtable (la struttura sottostante in un dizionario). In base all'utilizzo, è possibile che SortedList sia più veloce se combinato con una sorta di elenco salti o anche con un albero di auto-bilanciamento o tentativi. Soprattutto se si desidera restituire un intervallo di valori piuttosto che un singolo valore.

una tabella hash è una buona misura in cui:

1. sai quanti elementi si intende memorizzare, prima popolazione del tavolo ha inizio. Il ridimensionamento dinamico sarà molto doloroso!
2. di avere un buon algoritmo di hash con distribuzione uniforme, che fa .NET
3. C'è un buon meccanismo in atto per la risoluzione di collisione, che .NET fa
4. Siete alla ricerca di un singolo valore
5. Puoi garantiscono che tutti i valori saranno unici

Se stai facendo un po 'di compressione, per esempio, un RB-Tree è meglio di una Hashtable.

Fonte: http://en.wikipedia.org/wiki/Hashtable#Dynamic_resizing