Должен ли я быть обеспокоен скоростью словаря .NET?

Question

Я буду создавать проект, который будет использовать поиск по словарю и вставлять немало. Это то, что беспокоит?

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

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

Answer 1

1. Вы микрооптимизируемые.У вас еще есть рабочий код?Помните: «Если это не сработает, не имеет значения, как быстро не сработает».(Mich Ravera) http://www.codingninja.co.uk/best-programmers-quotes/.

   Вы не представляете, где будут узкие места, и уже сосредоточены на словаре.Что, если проблема в другом месте?

2. Как вы узнаете, как реализован класс Dictionary?Возможно, он уже использует массив с хешированными ключами!

PS Это действительно «.NET Dictionaries», а не «C # Dictionaries», потому что C # - всего лишь один из нескольких языков программирования, использующих framework.

Answer 2

Здравствуйте, я буду создавать проект который будет использовать поиск по словарю и вставляет совсем немного. Это что то беспокоиться о?

Да. Всегда целесообразно учитывать факторы производительности заранее.

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

Кроме того, если я сделаю бенчмаркинг и тому подобное и это действительно плохо, то что это лучший способ заменить словарь что-то еще?

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

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

Будет ли использовать массив с "hashed" ключи еще быстрее? Это не хотя поможет время вставки? 1018 *

Ни вы, ни кто-либо, кто читает это, не могут знать, какой из них быстрее, пока вы не напишите его обоими способами, а затем не сравните его в обоих направлениях в реальных условиях . Выполнение этого в «лабораторных» условиях искажает ваши результаты; вам нужно понять, как все работает, когда ГХ находится под реальным давлением памяти и так далее. Вы могли бы также спросить нас, какая лошадь будет бегать быстрее в Дерби Кентукки в следующем году. Если бы мы знали ответ, просто взглянув на гоночную форму, мы все уже были бы богаты. Вы не можете ожидать, что кто-нибудь узнает, какой из двух полностью гипотетических, неписанных фрагментов кода будет быстрее при неуказанных условиях!

Answer 3

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

Короче говоря - нет , как правило, вам не следует беспокоиться о производительности деталей реализации до тех пор, пока у вас не возникнет проблема.

Answer 4

Класс Dictionary<TKey, TValue> фактически реализован как хеш-таблица, которая делает поиск очень быстрым (близким к O (1)). См. документацию API для получения дополнительной информации. Я сомневаюсь, что вы могли бы сделать лучшую реализацию самостоятельно.

Answer 5

Я бы сделал тест словаря, HashTable (HashSet в .NET) и, возможно, домашнего класса, и посмотрел, какой из них лучше всего подходит для ваших типичных условий использования.

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

Answer 6

Я не уверен, что кто-то еще действительно ответил на эту часть:

Кроме того, если я сделаю бенчмаркинг и тому подобное и это действительно плохо, то что это лучший способ заменить словарь что-то еще?

Для этого везде, где это возможно, объявите переменные как IDictionary<TKey, TValue>. Это основной интерфейс, из которого происходит словарь. (Я предполагаю, что если вы так сильно заботитесь о производительности, то вы не рассматриваете неуниверсальные коллекции.) Затем, в будущем, вы можете изменить базовый класс реализации без необходимости изменения какого-либо кода, который его использует. толковый словарь. Например:

IDictionary<string, int> myDict = new Dictionary<string, int>();

Answer 7

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

Что касается использования массива, это то, что уже делает класс Dictionary. На самом деле он использует два массива, один для ключей и один для значений.

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

Answer 8

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

Если это однопоточный, то почти наверняка узкое место будет в другом месте. Например, чтение этих объектов оттуда, где вы их читаете.

Answer 9

Я использую словарь для сервера ретрансляции UDP. Каждый раз, когда приходит пакет, он выполняет Dictionary.ContainsKey и Dictionary [Key], и он отлично работает (огромное количество клиентов). У меня были проблемы, когда я делал это, но оказалось, что это последнее, о чем я должен беспокоиться.

Answer 10

Посмотрите на C # HybridDictionary Использование

Класс HybridDictionary

Этот класс рекомендуется для случаев где количество элементов в словарь неизвестен. Занимает Преимущество улучшенной производительности ListDictionary с небольшим коллекции, и предлагает гибкость переключения на Hashtable, который обрабатывает больше коллекции лучше, чем ListDictionary