Более простая структура данных для поиска значения ключа?

Question

Для небольшого набора пар ключ / значение (по умолчанию 2, макс. 5) значение Dictionary<TKey, TValue> выглядит излишним. Есть ли намного более простая структура данных, которая могла бы использоваться в моем случае? Я кэширую вычисленные значения для определенных объектов (например, <MyClass, double>), поэтому скорость поиска важна.

Спасибо

Answer 1

A List<KeyValuePair<TKey, TValue>> (созданный с соответствующей емкостью), вероятно, будет работать так же хорошо в этом случае ... но это не будет ужасно идиоматическим. (Просто чтобы прояснить ситуацию, вы просто позвоните Equals для каждого ключевого элемента, полностью игнорируя хеш-код.) Если List<T> кажется вам немного тяжелым, вы можете даже перейти на KeyValuePair<TKey, TValue>[], если хотите. Круто, но эй ... это твой код.

Вы действительно пытались Dictionary<TKey, TValue> и обнаружили, что это слишком медленно? «Похоже на излишество» - не такой хороший аргумент, как «Я попробовал его, профилировал и обнаружил, что недопустимое количество времени моего приложения тратится на создание словарей и поиск записей в них. имеют характеристику производительности X, и на данный момент у меня есть только Y ".

Если ваш тип ключа имеет определенный порядок (и если вы собирались выполнить больше операций поиска в структуре данных, чем собирались создавать экземпляры), вы могли бы отсортировать список, что означает, что у вас будет максимум 3 сравнения для любого конкретный поиск. Всего с 5 записями вы можете даже жестко закодировать все потенциальные пути, если вы хотите оптимизировать до самого конца. (Вы можете даже иметь разные реализации для 2, 3, 4 и 5 элементов. Хотя в этот момент это становится немного глупо.) Это в основном реализация SortedList<TKey, TValue>, но вы можете быть в состоянии оптимизировать это немного для вашего сценария только с несколькими записями. Опять же, стоит сначала попробовать встроенные типы.

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

Answer 2

Если набор ключей известен во время компиляции, тогда вы могли бы просто создать класс (или структуру) со свойствами, допускающими обнуляемость, которые содержат значения.

Answer 3

Если вы используете массив типа KeyValuePair<TKey, TValue>[], вы можете отсортировать его, а затем выполнить поиск с помощью двоичного поиска. Но это быстро, только если вам нужно отсортировать один раз, а затем получить много раз.

Answer 4

Мне часто нравится использовать класс Hashtable (http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx).

Еще одна вещь, которую вы можете сделать, это не беспокоиться об управлении каким-либо кешем самостоятельно, а просто использовать кеширование из ASP.NET. Все, что вам нужно сделать, это включить сборку system.web, а затем использовать ее даже в не-веб-приложениях. Вот статья об использовании кода кэша .Net в приложении Windows Forms. Это действительно просто.

http://www.codeproject.com/KB/cs/cacheinwinformapps.aspx

D.