.net dictionary vs altre strutture dati personalizzate gestite, perché il dizionario .net è così veloce?

Question

Sono nel mezzo dello sviluppo di una struttura di dati del tipo di valore chiave persistente personalizzato, da confrontare con SqlLite e Berkley DB. Comunque prima di scrivere l'implementazione volevo trovare la migliore struttura dati da usare per questo scopo. Ho guardato il un paio:

• Un albero dei sorgenti redblack aperta.
• Mono implementazione del dizionario.

Volevo che le strutture che ho scelto presentassero numeri di prestazioni paragonabili al dizionario .net.

ho usato un semplice test per il ciclo con 500k iterazioni per gli inserti e usato il cronometro per misurare inserti e aspetto chiave di fino:

ho notato che

• Berkley DB tempo di ricerca chiave era circa la stessa come il dizionario.
• Ho provato il mio test del ciclo per C5 per il dizionario, un'implementazione dell'albero rosso e persino l'implementazione del dizionario mono.

Tempo di inserimento: 7% più lento del dizionario .net.
Tempo di ricerca: 1000% più lento del dizionario .net. Questo è ancora più lento della velocità di ricerca con sqllite !! Ho provato a eseguire il test con l'ottimizzazione del compilatore attivata e ho comunque ottenuto risultati simili.

Mi rendo conto che sto confrontando Hashtables vs alberi ecc., Ma mi sono soffermato sulla discrepanza delle prestazioni tra tutte le strutture dati.

Qualcuno ha qualche idea

Answer 1

due pensieri:

1. È necessario assicurarsi non si è inavvertitamente compreso il tempo JIT nei test - questo può aggiungere una notevole quantità di tempo al risultato. Dovresti eseguire due esecuzioni nella stessa esecuzione e scartare la prima corsa.

2. È necessario assicurarsi che non si stia eseguendo il debugger, in quanto ciò può drasticamente alterare i risultati delle prestazioni.

A parte forma che, eventuali differenze di prestazioni che vedi può benissimo essere il risultato della differenza di prestazioni tra una tabella hash e un albero. Generalmente una struttura ad albero ha prestazioni O (n * log (n)) per una ricerca. Un albero equilibrato può ridurlo a O (lon (n)). Hashtables, nel frattempo, può avvicinarsi al tempo O (1) per le ricerche quando si evitano le collisioni di hash.

Immagino anche che la classe .NET Dictionary sia altamente ottimizzata poiché è una struttura di dati bread-and-butter per così tante cose diverse in .NET. Inoltre, un dizionario generico <> potrebbe essere in grado di evitare la boxe e pertanto potresti notare alcune differenze di prestazioni.

Answer 2

Scegliere la struttura dati e il repository in base ai dati. Detto questo, non esiste una struttura dati perfetta. Mentre .NET Dictionary<,> è ottimizzato perché spesso è una buona scelta, non è la risposta a tutti i problemi - sarebbe 42 ...

Answer 3

Se tutto ciò che serve è una ricerca, un albero rosso/nero non sarà la migliore struttura dati. Fornisce l'ordinamento, che sarà sempre più lento di una ricerca hashtable. Se si desidera confrontare il dizionario .net con una struttura di dati C5 comparabile, si utilizzerà C5.HashDictionary.