Более быстрая замена словаря <TKey, TValue>
Мне нужна быстрая замена для System.Collections.Generic.Dictionary<TKey, TValue>
. Мое приложение должно быть действительно быстро. Таким образом, замена должна поддерживать:
- Дженерики
- Добавить
- Получить
- Содержит
... и что это. Мне не нужна поддержка в LINQ или что-то еще. И это должно быть быстро.
Простой код:
Stopwatch stopWatch = Stopwatch.StartNew();
Dictionary<string, string> dictionary = new Dictionary<string, string>();
dictionary.Add("fieldName", "fieldValue");
dictionary.Add("Title", "fieldVaaaaaaaaaaaaaaaaalue");
Console.WriteLine(stopWatch.Elapsed);
... печатает 00: 00: 00.0001274, для меня это много времени, потому что мое приложение делает много других вещей, некоторые из них из старых медленных библиотек, которые я должен использовать, и не зависят от меня.
Любые идеи о том, как реализовать более быстрый?
Спасибо.
Ответы
Ответ 1
Скорее всего, вы видите компиляцию JIT. На моей коробке я вижу:
00:00:00.0000360
00:00:00.0000060
когда я запускаю его дважды в быстрой последовательности в рамках одного процесса, а не в отладчике. (Убедитесь, что вы не запускаете его в отладчике, или это бессмысленный тест.)
Теперь, измеряя любое время, когда крошечный, как правило, плохая идея. Вам нужно будет повторять миллионы раз, чтобы лучше понять, как долго это займет.
У вас есть все основания полагать, что это фактически замедляет ваш код, или вы основываете все это на своем первоначальном времени?
Я сомневаюсь, что вы найдете что-нибудь значительно быстрее, чем Dictionary<TKey, TValue>
, и я был бы очень удивлен, обнаружив, что это узкое место.
EDIT: Я только что проверил, добавив миллион элементов в Dictionary<TKey, TValue>
, где все ключи были существующими объектами (строки в массиве), повторное использование того же значения (что не имеет значения) и указание емкости миллиона на строительство - и это заняло около 0,15 с на моем двухлетнем ноутбуке.
Действительно ли это может быть узким местом для вас, учитывая, что вы уже сказали, что используете какие-то "старые медленные библиотеки" в другом месте вашего приложения? Имейте в виду, что чем медленнее эти другие библиотеки, тем меньшее влияние будет иметь улучшенный класс коллекции. Если изменения словаря составляют только 1% от вашего общего времени приложения, то даже если бы мы могли предоставить мгновенный словарь, вы бы только ускорили свое приложение на 1%.
Как всегда, получите профилировщик - это даст вам гораздо лучшее представление о том, куда ваше время идет.
Ответ 2
Я согласен с Jon Skeet утверждать, что это, скорее всего, компиляция JIT.
Сказав это, я хотел добавить другую информацию здесь:
Большинство вопросов скорости, связанных с использованием Dictionary<T,U>
, не связаны с реализацией словаря. Dictionary<T,U>
ОЧЕНЬ быстро, из коробки. Было бы трудно победить его.
Вопросы скорости, связанные с экземплярами Dictionary, почти всегда являются проблемами реализации хеш-кода. Если при использовании Dictionary<MyCustomClass,MyValue>
возникают проблемы с производительностью, перейдите к реализации GetHashCode()
, которую вы определили в MyCustomClass. Это еще более важно, если вы используете пользовательскую структуру как свой ключ.
Чтобы получить хорошую производительность из словаря, GetHashCode()
должен быть:
- Fast
- Возможность предоставления хеш-кодов, генерирующих несколько конфликтов. Уникальные экземпляры должны, когда это возможно, генерировать уникальные значения хеширования.
Если вы поймете это правильно, я думаю, вы будете очень довольны реализацией словаря по умолчанию.
Ответ 3
Не забывайте, что вы также определяете конструктор словаря в этом коде. Я сделал тест, переведя вызов на конструктор из измерения и зацикленный 10 раз. Здесь мой тестовый код:
for (int i = 0; i < 10; i++)
{
Dictionary<string, string> test = new Dictionary<string, string>();
System.Diagnostics.Stopwatch watch = System.Diagnostics.Stopwatch.StartNew();
test.Add("fieldName", "fieldValue");
test.Add("Title", "fieldavlkajlkdjflkjalkjslkdjfiajwelkrjelrkjavoijl");
Console.WriteLine(watch.Elapsed);
}
Console.ReadKey();
Ниже приведены результаты:
00:00:00.0000607
00:00:00.0000025
00:00:00.0000015
00:00:00.0000015
00:00:00.0000016
00:00:00.0000017
00:00:00.0000016
00:00:00.0000016
00:00:00.0000016
00:00:00.0000015
Я не уверен, насколько быстрее вы сможете получить, чем это...
Обновление
Похоже, что это отражают результаты Jon Skeets... JIT.
Ответ 4
Если вам действительно нужна более высокая производительность, вам придется отказаться от чего-то важного - например, от дженериков, динамического распределения памяти и т.д. Все эти функции приносят в жертву некоторую производительность.
Я бы избегал использования Contains, если это вообще возможно, и смотрю на TryGetValue и т.д.
Ответ 5
ИСПОЛЬЗУЙТЕ INTS КАК КЛЮЧИ ДЛЯ МАКСИМАЛЬНОЙ РАБОТЫ:
Для тех, кто пришел сюда из Google, если вы хотите выжать из словаря все до последней части производительности, тогда используйте Ints в качестве ключей. Вот тест, сравнивающий Int и String Keys: https://jacksondunstan.com/articles/2527
Автор статьи даже упоминает, что преобразование строк в целые стоит того, если у вас есть такая необходимость.
Также обратите внимание, что такое же поведение встречается и в некоторых других языках, таких как PHP. Php ассоциативные массивы -are в словарях fact-, и если вы используете Ints в возрастающем порядке в PHP7, они значительно превосходят строковые ключи.
Ответ 6
Скорее всего, вы не найдете ничего гораздо быстрее, чем словарь. Я бы просто использовал словарь. Затем, когда вы видите, что не выполняете свои первоочередные цели, а профилировщик указывает, что добавление/удаление из словаря - ваши узкие места, вы можете рассмотреть возможность замены с более целевым классом.
Обратите внимание, что такие функции, как LINQ, не должны вызывать потери производительности, если вы их не используете.
Ответ 7
Не могли бы вы использовать список и определить перечисление, например, fieldName = 0, title= 1 и использовать каждый уникальный уникальный индекс в качестве индекса поиска в списке? Это было бы самым быстрым решением, хотя оно было бы наименее гибким, поскольку вы были привязаны к перечислению.
Ответ 8
Сколько элементов вы планируете добавить в словарь? Хотя Dictionary/Hashtable, как правило, самый быстрый, в зависимости от того, что вы делаете, может быть что-то более быстрое (что лучше подходит), чем Hashtable (базовая структура в словаре). Основываясь на использовании, возможно, что SortedList может быть быстрее, если он сочетается с каким-то списком пропусков или даже с самобалансирующимся деревом или пытается. Особенно, если вы хотите вернуть диапазон значений, а не одно значение.
A Hashtable подходит, когда:
- Вы знаете, сколько предметов вы намерены хранить до начала таблицы. Динамическое изменение размера будет очень болезненным!
- У вас есть хороший алгоритм хеширования с равномерным распределением, который .NET делает
- Существует хороший механизм для разрешения конфликтов, который .NET делает
- Вы ищете одно значение
- Вы можете гарантировать, что все значения будут уникальными.
Если вы делаете некоторое сжатие, например, RB-Tree лучше, чем Hashtable.
Источник: http://en.wikipedia.org/wiki/Hashtable#Dynamic_resizing
Ответ 9
Словари позволяют заданный компаратор IEqualityComparer. для строк или других типов общего сравнения может быть не самым эффективным. Небольшой ILSpy покажет вам, что если вы возьмете по умолчанию сравнение ==, если ваша реализация страдает от производительности, вы можете внедрить свой собственный компаратор IEqualityComparer. В конце словарь будет сравнивать хеш-код того, что вы предоставляете в качестве ключа, с существующими хеш-кодами в своем списке записей.
Так что, если у вас есть словарь особых потребностей, возможно, специализируйте его на классе FastDictionary, чтобы получить более эффективный способ получить код доступа,
В вашей реализации это будет:
var dictionary = new Dictionary<string, string>(StringComparer.Ordinal);