В поисках быстрого составного ключа для словаря я столкнулся с аномалией, которую я не могу понять и не оправдать.
В ограниченном тестировании
Dictionary<KeyValuePair<UInt32, UInt32>, string>
значительно медленнее (200: 1), чем
Dictionary<KeyValuePair<UInt16, UInt16>, string>
Тест на две петли от 0 до 1000 Заполните и затем ContainsKey
Poplulate ContainsKey
UInt32 92085 86578
UInt16 2201 431
Проблема заключается в том, что
new KeyValuePair<UInt32, UInt32>(i, j).GetHashCode();
дает МНОГИЕ дубликаты.
В циклах я и j 1024 создается только 1024 уникальных значения хэша.
На основе лавинного комментария от CasperOne пробовали я * 31 и j * 97 (два простых числа), и это привело к тому, что 105280 уникально на 1024X1024. Еще много дубликатов. CasperOne Я знаю, что это не то же самое, что и случайное. Но это не моя работа по рандомизации ввода. GetHashCode() предполагается рандомизировать вывод.
Почему большое количество дубликатов?
Тот же цикл на
new KeyValuePair<UInt16, UInt16>(i, j).GetHashCode();
дает 1024 X 1024 уникальных хэш-кодов (отлично).
Int32 имеет ту же проблему.
Эти повторяющиеся значения хеша убивают
Dictionary<KeyValuePair<UInt32, UInt32>, string>
Tuple также генерирует много дубликатов, которые он не деградирует в Int32 по сравнению с Int16.
Время генерации исходного KVP и исходного кода KPV.GetHashCode аналогично.
Такая же аномалия с HashSet.
Dictionary<KeyValuePair<UInt32, UInt32>, string> dKVPu32 = new Dictionary<KeyValuePair<UInt32, UInt32>, string>();
Dictionary<KeyValuePair<UInt16, UInt16>, string> dKVPu16 = new Dictionary<KeyValuePair<UInt16, UInt16>, string>();
KeyValuePair<UInt32, UInt32> kvpUint32;
KeyValuePair<UInt16, UInt16> kvpUint16;
int range = 1000;
Int32 hashCode;
HashSet<Int32> kvpUint32Hash = new HashSet<Int32>();
HashSet<Int32> kvpUint16Hash = new HashSet<Int32>();
Stopwatch sw = new Stopwatch();
sw.Start();
for (UInt32 i = 0; i < range; i++)
{
for (UInt32 j = 0; j < range; j++)
{
kvpUint32 = new KeyValuePair<UInt32, UInt32>(i, j);
}
}
Console.WriteLine("UInt32 raw " + sw.ElapsedMilliseconds.ToString());
// 7
sw.Restart();
for (UInt16 i = 0; i < range; i++)
{
for (UInt16 j = 0; j < range; j++)
{
kvpUint16 = new KeyValuePair<UInt16, UInt16>(i, j);
}
}
Console.WriteLine("UInt16 raw " + sw.ElapsedMilliseconds.ToString());
// 6
sw.Restart();
for (UInt32 i = 0; i < range; i++)
{
for (UInt32 j = 0; j < range; j++)
{
hashCode = new KeyValuePair<UInt32, UInt32>(i, j).GetHashCode();
kvpUint32Hash.Add(hashCode);
}
}
Console.WriteLine("UInt32 GetHashCode " + sw.ElapsedMilliseconds.ToString() + " unique count " + kvpUint32Hash.Count.ToString());
// 285 1024
sw.Restart();
for (UInt16 i = 0; i < range; i++)
{
for (UInt16 j = 0; j < range; j++)
{
hashCode = new KeyValuePair<UInt16, UInt16>(i, j).GetHashCode();
kvpUint16Hash.Add(hashCode);
}
}
Console.WriteLine("UInt16 GetHashCode " + sw.ElapsedMilliseconds.ToString() + " unique count " + kvpUint16Hash.Count.ToString());
// 398 1000000
sw.Restart();
Console.ReadLine();
for (UInt32 i = 0; i < range; i++)
{
for (UInt32 j = 0; j < range; j++)
{
dKVPu32.Add(new KeyValuePair<UInt32, UInt32>(i, j), String.Format("{0} {1}", i.ToString(), j.ToString()));
}
}
Console.WriteLine("hsKVPu32 pop " + sw.ElapsedMilliseconds.ToString());
// 92085
sw.Restart();
for (UInt32 i = 0; i < range; i++)
{
for (UInt32 j = 0; j < range; j++)
{
if (!dKVPu32.ContainsKey(new KeyValuePair<UInt32, UInt32>(i, j))) Debug.WriteLine("Opps"); ;
}
}
Console.WriteLine("hsKVPu32 find " + sw.ElapsedMilliseconds.ToString());
// 86578
dKVPu32.Clear();
dKVPu32 = null;
GC.Collect();
sw.Restart();
for (UInt16 i = 0; i < range; i++)
{
for (UInt16 j = 0; j < range; j++)
{
dKVPu16.Add(new KeyValuePair<UInt16, UInt16>(i, j), String.Format("{0} {1}", i.ToString(), j.ToString()));
}
}
Console.WriteLine("hsKVPu16 pop " + sw.ElapsedMilliseconds.ToString());
// 2201
sw.Restart();
for (UInt16 i = 0; i < range; i++)
{
for (UInt16 j = 0; j < range; j++)
{
if (!dKVPu16.ContainsKey(new KeyValuePair<UInt16, UInt16>(i, j))) Debug.WriteLine("Opps"); ;
}
}
sw.Stop();
Console.WriteLine("hsKVPu16 find " + sw.ElapsedMilliseconds.ToString());
// 431
P.S. Самый быстрый - упаковать .E.G. ((UInt32) int1 < 16) | int2;
Хэш первого столбца UInt32 равен хэшу KVP следующих двух.
2281371105 8 992
2281371104 8 993
2281371107 8 994
2281371145 0 0
2281371147 0 2
2281371149 0 4
2281371151 0 6
2281371137 0 8
2281371144 0 1
2281371146 0 3
2281371148 0 5
2281371150 0 7
2281371136 0 9
2281371144 1 0
2281371145 1 1
2281371146 1 2
2281371147 1 3
2281371148 1 4
2281371149 1 5
2281371150 1 6
2281371151 1 7
2281371136 1 8
2281371137 1 9
2281371147 2 0
2281371146 2 1
2281371144 2 3
2281371151 2 4
2281371150 2 5
2281371149 2 6
2281371148 2 7
2281371139 2 8
Единственный шаблон, который я нашел, заключается в том, что либо сумма, либо разница или соответствие KVP.
Но не удалось найти шаблон для того, когда суммировать и когда вычесть.
Это плохой хеш, поэтому зная, что это такое, мало имеет значения.