Un dizionario generico .NET deve essere inizializzato con una capacità pari al numero di elementi che conterrà?

Question

Se ho, diciamo, 100 elementi che verranno memorizzati in un dizionario, dovrei inizializzarlo così?

var myDictionary = new Dictionary<Key, Value>(100);

La mia comprensione è che il dizionario .NET si ridimensiona internamente quando raggiunge un determinato caricamento e che la soglia di caricamento è definita come un rapporto della capacità.

Ciò suggerirebbe che se fossero stati aggiunti 100 articoli al dizionario sopra, si ridimensionerebbe se uno degli elementi fosse aggiunto. Il ridimensionamento di un dizionario è qualcosa che vorrei evitare in quanto ha un impatto sulle prestazioni ed è uno spreco di memoria.

La probabilità di collisioni con hash è proporzionale al caricamento in un dizionario. Pertanto, anche se il dizionario non si ridimensiona (e utilizza tutti i suoi slot), le prestazioni devono ridursi a causa di queste collisioni.

Come si dovrebbe decidere a quale capacità inizializzare il dizionario, supponendo che tu sappia quanti elementi ci saranno nel dizionario?

Answer 1

Ciò a cui dovresti inizializzare la capacità del dizionario dipende da due fattori: (1) La distribuzione della funzione gethashcode e (2) Quanti elementi devi inserire.

La tua funzione hash dovrebbe essere distribuita casualmente o dovrebbe essere formulata appositamente per il tuo set di input. Supponiamo il primo, ma se sei interessato alla seconda ricerca funzioni hash perfette.

Se hai 100 elementi da inserire nel dizionario, una funzione hash distribuita casualmente e imposti la capacità su 100, quindi quando inserisci l'elemento I nella tabella hash hai una probabilità (i-1) / 100 che l'oggetto con cui si scontrerà con un altro oggetto al momento dell'inserimento. Se si desidera ridurre questa probabilità di collisione, aumentare la capacità. Raddoppiare la capacità prevista dimezza le possibilità di collisione.

Inoltre, se si conosce la frequenza con cui si accederà a ciascun elemento nel dizionario, è possibile che si desideri inserire gli elementi in ordine di frequenza decrescente poiché gli elementi che si inseriscono per primi saranno mediamente più veloci per accedervi.

Answer 2

Ho fatto un test rapido, probabilmente non scientifico, ma se ho impostato la dimensione ci sono voluti 1,2207780 secondi per aggiungere un milione di articoli e ci sono voluti 1,5024960 secondi da aggiungere se non ho dato una dimensione al Dizionario ... questo sembra trascurabile per me.

Ecco il mio codice di prova, forse qualcuno può fare un test più rigoroso ma dubito che sia importante.

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary<string, string>(1000000);

            for (int i = 0; i < 1000000; i++)
                dict1.Add(i.ToString(), i.ToString());

            DateTime stop1 = DateTime.Now;

            DateTime start2 = DateTime.Now;
            var dict2 = new Dictionary<string, string>();

            for (int i = 0; i < 1000000; i++)
                dict2.Add(i.ToString(), i.ToString());

            DateTime stop2 = DateTime.Now;

            Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
            Console.ReadLine();
        }

Answer 3

Penso che tu stia complicando troppo le cose. Se sai quanti elementi ci saranno nel tuo dizionario, allora specifica quello sulla costruzione. Ciò aiuterà il dizionario a allocare lo spazio necessario nelle sue strutture di dati interne per evitare la riallocazione e il rimpasto dei dati.

Answer 4

Specificare la capacità iniziale per il costruttore Dizionario aumenta le prestazioni perché ci sarà un minor numero di ridimensionamenti alle strutture interne che memorizzano i valori del dizionario durante le operazioni ADD.

Considerando che si specifica una capacità iniziale di k al costruttore Dizionario quindi:

1. Il Dizionario riserva la quantità di memoria necessaria per memorizzare k elementi;
2. Le prestazioni di QUERY sul dizionario non sono interessate e non saranno più veloci o più lente;
3. Le operazioni ADD non richiederanno più allocazioni di memoria (forse costose) e quindi saranno più veloci.

Da MSDN :

  

La capacità di un dizionario (TKey,   TValue) è il numero di elementi che   può essere aggiunto al dizionario (TKey,   TValue) prima di ridimensionare è necessario.   Come elementi vengono aggiunti a   Dizionario (TKey, TValue), la capacità   viene automaticamente aumentato secondo necessità   riallocando l'array interno.

     

Se la dimensione della raccolta può essere   stimato, specificando l'iniziale   la capacità elimina la necessità   eseguire un numero di ridimensionamento   operazioni durante l'aggiunta di elementi a   il dizionario (TKey, TValue).

Answer 5

Sì, contrariamente a una HashTable che utilizza il rehashing come metodo per risolvere le collisioni, Dictionary utilizzerà il concatenamento. Quindi sì, è bene usare il conteggio. Per una HashTable probabilmente vuoi usare count * (1 / fillfactor)

Answer 6

La dimensione iniziale è solo un suggerimento. Ad esempio, alla maggior parte delle tabelle hash piace avere dimensioni che sono numeri primi o una potenza di 2.