Наиболее эффективная структура данных в памяти для доступа к словарю только для чтения

Question

В C # у меня есть некоторые статические данные, которые можно поместить в Dictionary<int, T>, где T - некоторый ссылочный тип.Веб-приложение должно только инициализировать его один раз, статически (оно не изменяется).

Поскольку мне не нужно беспокоиться о производительности вставки или удаления, какую структуру данных лучше всего использовать (или следуетЯ сам себе катаюсь)?Я, наверное, смотрю что-то вроде ~ 100 000 записей, довольно равномерно распределенных.

Я ищу оптимальный алгоритм для получения этих данных.Dictionary<> неплохо, но я думаю, что там должно быть что-то оптимизированное для данных только для чтения.

Я подозреваю, но не подтвердил, что диапазон этих ключей может быть 0 - 400 000,Если бы это было так, как бы изменились рекомендации?(У меня есть мысль, что я опубликую в качестве возможного ответа).

---

Может быть, я мог бы:

1. Один раз отсканировать данные и взять самый высокий ключ
2. Выделите массив с размером старшего ключа + 1.
3. Сделайте второй проход и сохраните данные в массиве.

Было бы это лучше или хуже, чемHashTable / словарь с разумным коэффициентом загрузки?

Answer 1

Словарь - верный путь. Вот цитата из MSDN :

Универсальный класс Dictionary (Of TKey, TValue) обеспечивает отображение из набор ключей для набора значений. Каждое дополнение к словарю состоит из значения и связанного с ним ключа. Получение значения по использовать его ключ очень быстро, близко к O (1) , потому что словарь (из Класс TKey, TValue) реализован в виде хеш-таблицы.

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

Редактировать

Если у вас будет более 50% ключей в диапазоне от 0 до 400 Кб, имеет смысл использовать простой массив, где ключ - это индекс элемента. Это даст вам сложность O (1) в лучшем случае. По вашему вопросу, только 25% ключей будет присутствовать. Так что в этом случае я бы пошел с Dictionary <,>, я не думаю, что он имеет 75% дополнительной памяти для хранения каждой пары ключ-значение по сравнению с простым массивом.

Answer 2

Если это действительно словарь, trie работает достаточно хорошо. Dictionary (хеш-таблица) - это еще одна возможность, если вы настроите ее. Что было бы быстрее ... Я не знаю, вам нужно профилировать это, я думаю. В космосе Три выигрывает руки вниз. Я не думаю, что .NET имеет три в своей стандартной библиотеке, но должны быть некоторые реализации, плавающие вокруг.