Ottimizzazione delle ricerche:Ricerche chiave del dizionario vs.Ricerche nell'indice degli array

Question

Sto scrivendo un valutatore di mani di poker a 7 carte come uno dei miei progetti preferiti.Mentre cercavo di ottimizzarne la velocità (mi piace la sfida), sono rimasto scioccato nello scoprire che le prestazioni delle ricerche delle chiavi del dizionario erano piuttosto lente rispetto alle ricerche dell'indice dell'array.

Ad esempio, ho eseguito questo codice di esempio che enumera tutte le 52 scelte 7 = 133.784.560 possibili 7 mani di carte:

var intDict = new Dictionary<int, int>();
var intList = new List<int>();
for (int i = 0; i < 100000; i ++)
{
    intDict.Add(i, i);  
    intList.Add(i);
}

int result;

var sw = new Stopwatch();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intDict[32131]; // perform C(52,7) dictionary key lookups
sw.Stop();
Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);

sw.Reset();

sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intList[32131]; // perform C(52,7) array index lookups
sw.Stop();
Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);

che restituisce:

time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms

È previsto questo tipo di comportamento (diminuzione delle prestazioni di un fattore 8)?IIRC, un dizionario ha, in media, ricerche O (1), mentre un array ha ricerche O (1) nel caso peggiore, quindi mi aspetto che le ricerche dell'array siano più veloci, ma non di così tanto!

Attualmente sto memorizzando la classifica delle mani di poker in un dizionario.Suppongo che se questo è veloce quanto possono essere le ricerche nel dizionario, devo ripensare il mio approccio e utilizzare invece gli array, anche se indicizzare le classifiche diventerà un po' complicato e probabilmente dovrò fare un'altra domanda al riguardo.

Answer 1

Non dimenticate che le notazioni O-grande, dice solo come la complessità cresce rispetto alla dimensione (ecc) - non dà alcuna indicazione dei fattori costanti coinvolti. Ecco perché a volte anche un lineare ricerca per le chiavi è più veloce di una consultazione dei dizionari, quando ci sono sufficientemente pochi tasti. In questo caso non si sta anche facendo una ricerca con la matrice anche se - solo un'operazione di indicizzazione dritto

.

Per la ricerca degli indici diritte, le matrici sono fondamentalmente ideale - è solo un caso di

pointer_into_array = base_pointer + offset * size

(E poi riferimento a un puntatore.)

L'esecuzione di una consultazione dei dizionari è relativamente complicato - molto veloce rispetto a (diciamo) una ricerca lineare chiave quando ci sono un sacco di chiavi, ma molto più complicato di una ricerca di matrice dritto. Si deve calcolare l'hash della chiave, poi capire quale secchio che dovrebbe essere in, eventualmente trattare con gli hash duplicati (o duplicare secchi) e quindi controllare per l'uguaglianza.

Come sempre, scegliere la struttura di dati giusto per il lavoro -. E se davvero si può uscire solo con indicizzazione in un array (o List<T>) allora sì, che sarà veloce come il fulmine

Answer 2

  

E 'questo tipo di comportamento previsto (riduzione delle prestazioni di un fattore 8)?

Perché no? Ogni ricerca array è quasi intantaneous / trascurabile, mentre una consultazione dei dizionari può avere bisogno di almeno una chiamata di subroutine in più.

Il punto della loro essendo entrambi O (1) significa che anche se si dispone di 50 volte di più elementi in ogni collezione, la riduzione delle prestazioni è ancora solo un fattore di qualunque essa sia (8).

Answer 3

Qualcosa potrebbe prendere un millennio, e di essere ancora O (1).

Se single-step attraverso questo codice nella finestra di smontaggio, si arriva rapidamente a capire quale sia la differenza.

Answer 4

Le strutture dei dizionari sono particolarmente utili quando lo spazio delle chiavi è molto grande e non può essere mappato in un ordine stabile e sequenziale.Se riesci a convertire le tue chiavi in ​​un semplice numero intero in un intervallo relativamente piccolo, ti sarà difficile trovare una struttura dati che funzioni meglio di un array.

In una nota di implementazione;in .NET i dizionari sono essenzialmente hashable.Puoi migliorare in qualche modo le prestazioni di ricerca delle chiavi assicurando che le tue chiavi siano inserite in un ampio spazio di valori univoci.Sembra che nel tuo caso tu stia utilizzando un semplice numero intero come chiave (che credo abbia il suo stesso valore), quindi potrebbe essere la cosa migliore che puoi fare.

Answer 5

Una ricerca array è la cosa più veloce che si può fare - in sostanza tutto ciò che è è un singolo bit di aritmetica dei puntatori per passare dall'inizio della matrice per l'elemento che si voleva trovare. D'altra parte, la consultazione dei dizionari è probabile che sia po 'più lento in quanto deve fare hashing e occuparsi di trovare il secchio corretta. Anche se il tempo di esecuzione previsto è anche O (1) - le costanti algoritmici sono maggiori in modo che sarà più lento

.

Answer 6

Benvenuti alla notazione O-grande. Hai sempre considerare che v'è un fattore costante in questione.

Fare un Dict-Lookup è, naturalmente, molto più costoso di una ricerca di matrice.

Big-O dice solo come algoritmi di scala. Raddoppia la quantità di ricerche e vedere come i numeri cambiano:. Entrambi dovrebbero prendere tutto il tempo per due volte

Answer 7

Il costo di recupero di un elemento da un Dictionary è O (1) , ma questo è perché un dizionario è implementato come una tabella hash - in modo da avere per calcolare il valore hash prima di sapere quale elemento per tornare. Hashtables spesso non sono che efficiente - ma sono un bene per grandi serie di dati, o di insiemi di dati che hanno un sacco di valori unici-hash

.

The List (oltre ad essere una parola spazzatura utilizzata per dercribe una matrice piuttosto che una lista collegata!) Sarà più veloce in quanto restituirà il valore calcolando direttamente l'elemento che si desidera venga restituito.