Otimizando Lookups: pesquisas de chave Dictionary vs. pesquisas de índice da matriz

Question

Eu estou escrevendo um atiçador avaliador mão 7 card como um dos meus projetos de estimação. Ao tentar otimizar sua velocidade (I como o desafio), fiquei chocado ao descobrir que o desempenho das principais pesquisas de dicionário foi bastante lento em comparação com pesquisas de índice de matriz.

Por exemplo, eu corri este código de exemplo que enumera todos os 52 escolher 7 = 133,784,560 mãos possíveis 7 cartão:

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);

que saídas:

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

É este tipo de comportamento esperado (redução de desempenho por um fator de 8)? IIRC, um dicionário tem, em média, O (1) pesquisas, enquanto uma matriz tem de pior caso O (1) pesquisas, por isso eu esperava as pesquisas de matriz para ser mais rápido, mas não por este muito!

Atualmente, estou armazenando rankings da mão do poker em um dicionário. Suponho que se isso é tão rápido quanto as pesquisas de dicionário pode ser, eu tenho que repensar a minha abordagem e usar arrays em vez, embora indexar os rankings vai ficar um pouco complicado e eu provavelmente vai ter que fazer outra pergunta sobre isso.

Answer 1

Não se esqueça que as notações Big-O diz apenas como a complexidade cresce com relação ao tamanho (etc) - não dá qualquer indicação dos fatores constantes envolvidos. É por isso que às vezes até um linear procurar para chaves é mais rápido do que uma consulta do dicionário, quando não são suficientemente algumas teclas. Neste caso, você não está mesmo fazendo uma busca com a matriz embora -. Apenas uma operação de indexação reta

Para pesquisas de índice em linha reta, as matrizes são basicamente ideal - é apenas um caso de

pointer_into_array = base_pointer + offset * size

(E então um dereference ponteiro.)

Realizando uma pesquisa de dicionário é relativamente complicado - muito rápido em comparação com (digamos) uma pesquisa linear por chave quando há muitas chaves, mas muito mais complicado do que uma pesquisa de série em linha reta. Tem que calcular o hash da chave, em seguida, descobrir qual balde que deve ser, possivelmente lidar com hashes duplicadas (ou baldes duplicadas) e, em seguida, verificar se há igualdade.

Como sempre, escolha a estrutura de dados certo para o trabalho -. E se você realmente pode começar afastado com apenas indexação em uma matriz (ou List<T>), então sim, isso será extremamente rápido

Answer 2

É este tipo de comportamento esperado (redução de desempenho por um fator de 8)?

Por que não? Cada pesquisa matriz é quase intantaneous / negligenciável, enquanto uma pesquisa de dicionário pode precisar de pelo menos uma chamada de sub-rotina extra.

O ponto de serem ambos O (1) significa que mesmo se você tem 50 vezes mais itens em cada coleção, a diminuição do desempenho ainda é apenas um fator de tudo o que é (8).

Answer 3

Algo poderia ter um milênio, e ainda ser O (1).

Se você único-passo através deste código na janela desmontagem, você virá rapidamente para entender o que é a diferença.

Answer 4

estruturas

dicionário são mais úteis quando o espaço da chave é muito grande e não pode ser mapeado em um estábulo, a ordem sequencial. Se você pode converter suas chaves em um inteiro simples em um intervalo relativamente pequeno, você vai ser duramente pressionado para encontrar uma estrutura de dados que terá um desempenho melhor do que uma matriz.

Em uma nota implementação; em NET, dicionários são essencialmente hashables. Você pode tanto melhorar o seu desempenho-chave de pesquisa, garantindo que o seu chaves de hash em um grande espaço de valores exclusivos. Parece que no seu caso, você está usando um inteiro simples como uma chave (que eu acredito hashes para o seu próprio valor.) - de modo que pode ser o melhor que pode fazer

Answer 5

Uma pesquisa matriz é sobre a coisa mais rápido que você pode fazer - essencialmente tudo isso é um único bit de aritmética de ponteiro para ir desde o início da matriz para o elemento que você queria encontrar. Por outro lado, a pesquisa de dicionário é provável que seja um pouco mais lento, uma vez que precisa de fazer hashing e se interesse em encontrar o balde correta. Embora o tempo de execução esperado é também O (1) -. As constantes algorítmicos são maiores por isso vai ser mais lento

Answer 6

Bem-vindo a notação Big-O. Você sempre tem que considerar que há um fator constante envolvidos.

Fazer um Dict-Lookup é, naturalmente, muito mais caro do que uma pesquisa de matriz.

Big-O só lhe diz como os algoritmos de escala. Dobrar a quantidade de pesquisas e ver como os números mudam:. Ambos devem levar em torno do tempo duas vezes

Answer 7

O custo de recuperação de um elemento de uma dicionário é O (1) , mas isso é porque um dicionário é implementado como um hashtable - então você tem que primeiro calcular o valor de hash para saber qual elemento para retorno. Hashtables muitas vezes não são tão eficientes - mas eles são bons para grandes conjuntos de dados ou conjuntos de dados que tem um monte de valores exclusivos-de hash

.

The List (além de ser uma palavra lixo usado para dercribe um array ao invés de uma lista ligada!) Será mais rápido, uma vez que irá retornar o valor por meio do cálculo diretamente o elemento que você deseja retornado.