C# Dictionary - лучше один большой или несколько маленьких?

Рейтинг: 1Ответов: 3Опубликовано: 24.02.2015

Есть словарь вида Dictionary<uint, uint>(5000)

Есть возможность оптимизировать поиск в нем, но за счет создания гораздо большего словаря. Имеет ли смысл это делать? Будет ли поиск в словаре вместимостью 50000 элементов ощутимо быстрее, чем чтение 10 чисел из словаря вместимостью 5000 элементов? В обоих случаях это словари констант. То есть код выглядит примерно так (для случая трех чисел):

var d1 = new Dictionary<uint, uint>(5000);
uint x = d1[a] + d1[b] + d1[c];

var d2 = new Dictionary<uint, uint>(50000);
uint x = d2[a + b + c];
c# .net словари оптимизация
Источник: Stack Overflow на русском

Ответы

▲ 5Принят

Во-первых, я думаю, что никто не сможет вам сказать точно: алгоритмы, используемые словарём, не являются частью стандарта (частью стандарта является лишь их алгоритмическая сложность), а значит, могут изменяться (обычно в сторону улучшения) в зависимости от версии .NET, сервис-паков, начального значения хэшкода объекта, адреса переменных в heap-памяти, направления ветра и фазы Луны.

Тем не менее, по идее скорость поиска должна падать больше от неравномерности появления хэш-коллизий. Поэтому большая таблица и один поиск в ней должно быть лучше, чем десять.

В любом случае, вы должны спрофилировать доступ именно на данных, типичных для вашего приложения, и на этой основе приходить к заключению. Всё остальное — гадание на кофейной гуще.

Кроме того, 50000 — это маленький размер таблицы. Большим размером было бы за миллион.

Короче: А вот измерьте скорость сами и сравните. Я бы поставил на то, что один поиск в большей таблице будет быстрее, чем много поисков в маленьких.

▲ 2

Скорость поиска в хэш-таблице зависит в большей степени от качества хэш-функции: чем более уникальное распределение дает данная функция для данного типа значений, тем меньше происходит коллизий и тем быстрее происходит поиск.

Соответственно в вашем случае чем более уникальные ключи вы будете хранить, тем быстрее будет поиск (поскольку значение хэш-кода для uint равно собственно его значению).

Так что все зависит от ваших данных. Взять хотя бы случай с вычислением ключа для одной таблицы:

uint x = d2[a + b + c];

полученная сумма может часто давать одинаковые значения для разных a, b, c, однако может давать и достаточно уникальные значения. Это сильно зависит от значений a, b, c.

Поэтому, как посоветовал @VladD, нужно тестировать на конкретно ваших данных. Лично мне кажется, что если ключи достаточно уникальны, то ощутимой разницы не будет, и проще будет держать одну таблицу.

▲ 1

VadimTukaev, мне кажется, для вашей задачи лучше использовать просто линейный массив. В одном массиве вы храните индексы ключей. В другом значения. Время доступа - будет двумя операциями чтения из System.Array. И поиск не нужен =)