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

Ответ 1

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

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

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

P.S. Это действительно ".NET Dictionaries", а не "С# Dictionaries", потому что С# - это всего лишь один из нескольких языков программирования, которые используют фреймворк.

Ответ 2

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

Да. Всегда разумно учитывать факторы эффективности.

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

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

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

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

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

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

Ответ 3

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

Вкратце - нет, в общем, вы не должны беспокоиться о производительности деталей реализации до тех пор, пока у вас не возникнет проблема.

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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

Ответ 8

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

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

Ответ 9

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

Ответ 10

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

Класс HybridDictionary

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

Ответ 11

Вы можете использовать библиотеку C5. Я нашел его очень быстрым и продуманным. Другие на stackoverflow нашли то же самое. С C5 у вас есть возможность использовать интерфейсы общего типа (с I) или непосредственно структуры данных. Естественно, интерфейсы позволяют вам менять различные реализации, но я нашел в тестировании производительности, что интерфейсы будут стоить вам.

Ответ 12

Вы можете посмотреть класс KeyedCollection в System.ObjectModel. Из описания MSDN "предоставляет абстрактный базовый класс для коллекции, ключи которой встроены в значения".