Быстрая замена словаря <TKey, TValue>

Question

Мне нужна быстрая замена для System.Collections.Generic.Dictionary<TKey, TValue>. Мое приложение должно быть действительно быстро. Таким образом, замена должна поддерживать:

• Generics
• Добавить
• Получить
• Содержит

... и это все. Мне не нужна поддержка в 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, что много времени для меня, потому что мое приложение делает много других вещей, некоторые из них от старого медленные библиотеки, которые я должен использовать и не зависят от меня.

Любые идеи о том, как реализовать более быстрый?

спасибо.

Answer 1

Скорее всего, вы видите компиляцию JIT. На моей машине, я вижу:

00:00:00.0000360 
00:00:00.0000060 

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

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

У вас есть все основания полагать, что это Фактически замедляет ваш код - или вы основываете все это на своем первоначальном сроке?

Я сомневаюсь, что вы найдете что-нибудь значительно быстрее, чем Dictionary<TKey, TValue>, и я был бы очень удивлен, обнаружив, что это узкое место.

EDIT: Я только что сравнил количество миллионов элементов с Dictionary<TKey, TValue>, где все ключи были существующими объектами (строки в массиве), повторное использование того же значения (как это не имеет значения) и указание емкости миллиона на строительство - и это заняло около 0,15 секунды на моем двухлетнем ноутбуке.

Действительно ли это действительно может быть узким местом для вас, учитывая, что вы уже сказали, что используете некоторые «старые медленные библиотеки» в другом месте вашего приложения? Имейте в виду, что чем медленнее эти другие библиотеки, тем меньшее влияние будет иметь улучшенный класс коллекции. Если изменения словаря составляют только 1% от вашего общего времени приложения, то даже если бы мы могли предоставить мгновенный словарь, вы только ускорите свое приложение на 1%.

Как всегда, получите профилировщик - это даст вам гораздо лучшее представление о том, куда ваше время идет.

Answer 2

Я согласен с предположением Jon Skeet, что это, скорее всего, компиляция JIT.

Это, как говорится, я хотел бы добавить некоторую другую информацию здесь:

Большинство вопросов скорости, связанных с использованием Dictionary<T,U> не связаны с реализацией словаря. Dictionary<T,U> ОЧЕНЬ быстро, из коробки. Было бы трудно победить его.

Проблемы со скоростями, связанные с экземплярами Dictionary, почти всегда являются проблемами реализации хеш-кода. Если у вас возникли проблемы с частотой при использовании Dictionary<MyCustomClass,MyValue>, перейдите к реализации GetHashCode(), которую вы определили на MyCustomClass. Это еще более важно, если вы используете собственную структуру как свой ключ.

Для того, чтобы получить хорошую производительность из словаря, GetHashCode() должно быть:

1. Fast
2. состоянии обеспечить хэш-коды, которые генерируют несколько конфликтов. Уникальные экземпляры должны, когда это возможно, генерировать уникальные значения хэша.

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

Answer 3

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

Я хотел бы избежать использования Содержит если вообще возможно, и смотреть на TryGetValue т.д.

Answer 4

Odds вы не собираетесь найти что-либо гораздо быстрее, чем словарь. Я бы просто использовал словарь. Затем, когда вы видите, что не выполняете свои первоочередные цели, а профилировщик указывает, что добавление/удаление из словаря - ваши узкие места, вы можете рассмотреть возможность замены с более целевым классом.

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

Answer 5

Не забывайте, что вы также закрепили конструктор словаря в этом коде. Я сделал тест, переведя вызов на конструктор из измерения и зацикленный 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 

Я не уверен, насколько быстрее вы могли бы получить, чем ...

Update

Похоже на то, что эти зеркала также показывают результаты работы Джона Скита ... JIT.

Answer 6

Не могли бы вы использовать список и определить перечисление, например, fieldName = 0, Title = 1 и использовать уникальный индекс каждого свойства в качестве индекса поиска в списке? Это было бы самым быстрым решением, хотя и наименее гибким, так как вы были бы привязаны к перечислению.

Answer 7

Сколько предметов вы планируете добавить в словарь?Хотя Dictionary/Hashtable, как правило, самый быстрый, в зависимости от того, что вы делаете, может быть что-то более быстрое (что лучше подходит), чем Hashtable (базовая структура в словаре). Основываясь на использовании, возможно, что SortedList может быть быстрее, если он сочетается с каким-то списком пропусков или даже с самобалансирующимся деревом или пытается. Особенно, если вы хотите вернуть диапазон значений, а не одно значение.

Hashtable хорошо подходит, когда:

1. Вы знаете, сколько элементов вы собираетесь хранить до начала населения таблицы. Динамическое изменение размера будет очень болезненным!
2. У вас есть хороший алгоритм хеширования с равномерным распределением, которое делает .NET
3. Существует хороший механизм в месте для разрешения конфликтов, который делает .NET
4. Вы ищете одно значение
5. Вы можете убедитесь, что все значения будут уникальными.

Если вы выполняете сжатие, например, RB-Tree лучше, чем Hashtable.

Источник: http://en.wikipedia.org/wiki/Hashtable#Dynamic_resizing