Я пишу 7-карточный покерный оценщик как один из моих любимых проектов. Пытаясь оптимизировать свою скорость (мне нравится вызов), я был потрясен, обнаружив, что производительность поиска словаря была довольно медленной по сравнению с поиском индекса массива.
Например, я запустил этот примерный код, который перечисляет все 52 выбирает 7 = 133 784 560 возможных 7 карт:
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);
который выводит:
time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms
Ожидается ли такое поведение (снижение производительности в 8 раз)? IIRC, словарь имеет, в среднем, O (1) поиск, в то время как массив имеет наихудший поиск O (1), поэтому я ожидаю, что поиск массива будет быстрее, но не этим!
В настоящее время я храню рейтинг в покере в Словаре. Я полагаю, что если это так быстро, как словарный поиск может быть, я должен пересмотреть мой подход и использовать массивы вместо этого, хотя индексация ранжирования будет немного сложнее, и мне, вероятно, придется задать еще один вопрос об этом.
