1

Есть словарь вида 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];

4 ответа 4

5

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

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

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

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


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

3
  • Не хотел я возиться с тестированием, но видимо придется... Кроме того, есть возможность сделать первый словарь по принципу perfect hash. Так что он действительно может оказаться быстрее большого, даже если придется искать в нем 20 чисел, а не одно... 24 фев 2015 в 17:22
  • Расскажите потом о результатах. И каков характер данных.
    – andreycha
    24 фев 2015 в 22:33
  • 1
    Там фишка не в данных, а в алгоритме оказалась. Я только вчера догадался накалякать пять строк на Пайтоне, которые проверили, а как часто вообще будет вызываться "большой" словарь в моей задаче. Оказалось - с вероятностью 20%. Даже если условно считать его скорость бесконечной, все равно получается ускорение на 25% (100 / 80 = 1.25). Причем для этого ускорения придется очень сильно раздуть и усложнить код. Классическое соотношение 80/20 получилось! 80% кода обслуживают 20% запросов. :( Вместо этого я оптимизировал "маленький" словарь, в результате чего он стал более чем в два раза быстрее! : 26 фев 2015 в 17:14
2

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

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

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

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

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

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

1
  • Суммирование чисел - это просто для примера, на самом деле там другие преобразования. Но все это неважно - выяснилось, что в моей конкретной задаче проще отказаться от большого словаря, зато максимально оптимизировать маленький (с помощью perfect hash). 26 фев 2015 в 17:05
1

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

2
  • Кстати, вполне может быть оптимальный вариант, если значения не сильно разбросаны.
    – VladD
    24 фев 2015 в 17:18
  • Если бы это было возможно, я бы так и сделал. Однако разброс у ключей слишком велик - сотни миллионов в одном словаре и еще больше в другом. Предлагаете сделать массив, занимающий полгигабайта памяти, на 99.995% заполненный нулями? Или я не понял, что Вы имели в виду? 24 фев 2015 в 17:18
1

Хеш-таблицы имеют константную асимптотику времени доступа. То есть на больших числах что один большой словарь, что много словарей по-меньше - нет разницы. Делайте так, как вам удобнее.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.