Существует ли предел записям в Словаре <>?
У меня есть приблизительно 3 000 различных файлов, которые я должен организовать и получить в разное время во время игры.
Я создал свою собственную структуру переменных. Я думал о создании "Словаря" в начале моего приложения и просто загрузки всех моих файлов, прежде чем игра запустится.
Я задаюсь вопросом о производительности: будет словарь с этим, много записей заставляют мое приложение быть медленным? Большой словарь сделал бы "TryGetValue" и "ContainsKey" выполненными медленнее?
спасибо за совет!
8 ответов
TryGetValue и ContainsKey должны работать довольно быстро при таком размере, если ключ имеет хорошо распределенные хэши.
Словарь имеет индексируемое количество «ведер». Когда он добавляет или ищет значение по ключу, он принимает значение, возвращаемое GetHashCode (), снова хеширует его, чтобы оно было меньше количества корзин (обычно что-то простое, например, по модулю, но реализация не определена), и загляните в соответствующее ведро.
В настоящее время в корзине будет ноль или более элементов. Словарь будет сравнивать каждый элемент с ключом с помощью .Equals ().
Первый бит поиска нужного сегмента будет происходить за постоянное время O (1). Второй бит сравнения ключа с ключами в корзине будет происходить за линейное время O (n), где n относится только к количеству элементов в этой корзине, а не во всей коллекции.
Как правило, в каждом сегменте должно быть очень мало элементов (количество сегментов будет расти, чтобы попытаться сохранить этот случай), поэтому операция по существу является постоянной по времени.
Однако, если ваши хэш-коды плохо реализованы, в одном сегменте будет много ключей.Временная сложность будет приближаться к O (n), что можно увидеть, поэкспериментируя с объектом с заведомо неправильным GetHashCode, который каждый раз просто возвращает 0. В худшем случае он хуже, чем список, поскольку список тоже O (n), но у словаря больше накладных расходов.
Означает ли это, что вам следует волноваться? Нет, даже относительно простые методы хеширования должны давать относительно хорошие результаты. Если вы используете строковый ключ, то, вероятно, этого уже будет более чем достаточно. Если вы используете простой встроенный шрифт, то тем более.
Если вы все же обнаружите, что доступ к словарю происходит медленно, вы должны обратить на это внимание и либо исправить метод GetHashCode (), либо создать IEqualityComparer (который позволяет вам определять внешние правила для GetHashCode () и Equals () для использования со словарями, хэшсетами и т. д.).
Скорее всего, 3000 - ничто, ничего страшного.
Обеспечение алгоритма хэш-кода для типа словарного ключа распределяет хэш-коды относительно равномерно по пространству Int32, поиск хэш-кода не зависит от размера словаря.
См. http://en.wikipedia.org/wiki/Hashtable#Performance_analysis для получения дополнительной информации.
Нет, не будет. Он будет потреблять память, но TryGetValue и ContainKey должны быть довольно быстрыми, поскольку словарь является хеш-таблицей, а доступ к элементам по ключу является постоянным и не зависит от количества элементы.
Узким местом будет не производительность словаря, а чтение 3000 файлов.
Как и в большинстве случаев с компьютерами (и в частности с производительностью), "It Depends (tm)"
Все зависит от реализации Dictionary.
Это может быть выполнено как двоичное дерево, и в этом случае поиск должен быть O (log2 N), что означает, что время поиска медленно растет по мере увеличения размера словаря.
Это можно сделать в виде хеш-таблицы, которая теоретически равна O (1), что означает, что поиск всегда будет занимать одинаковое количество времени независимо от размера словаря, но это теория и зависит от от количества ведер и качества хэш-кода. Если многие элементы попадают в одну и ту же корзину, что требует линейного поиска, работа значительно замедляется по мере роста словаря.
Однако словарь должен вырасти за пределы 3000 на несколько порядков, прежде чем вы увидите заметную разницу.
Существует предел, но 3000 - это еще не предел. Dictionary<> использует Object.GetHashCode() для орагнизации своих ключей, который возвращает int. Поэтому вы можете хранить максимум 2^32 (4,294,967,296) ключей, прежде чем произойдет столкновение. Однако из-за того, как обычно вычисляются хэш-коды в .Net, скорее всего, будет много коллизий, когда вы приблизитесь к этому магическому числу.
Добавление дополнительных ключей не замедлит TryGetValue и ContainsKey - они являются O(1) операциями.
3000 записей пустяки для Словаря <> . Это не будет источником замедления.
С другой стороны, чтение 3000 различных файлов в память при запуске будет медленным. Вам будет гораздо лучше читать файлы в память только в то время, когда они нужны, но потом сохранять их в памяти для последующих обращений.
Словари в .NET используют схему поиска по хеш-таблице, поэтому добавление записей практически не влияет на производительность поиска. Единственная проблема, с которой вы столкнетесь, может заключаться в использовании памяти. Словарь из 3000 элементов будет занимать примерно в 3000 раз больше памяти, используемой ключом плюс типы значений. Если это простая структура без огромных двоичных объектов, 3000 будет совершенно крошечной.