Меня зовут Женя, я работаю в Itransition как backend .Net developer – и это моя первая статья на техническую тему. Сегодня я хочу рассказать о типах словарей, которые бывают в .Net, а также о Hash table, о сложности поиска и вставки, о применимости в различных условиях, и даже слегка о Tree.
Big O
Для самого начала нам нужно хотя-бы вскользь пробежаться по алгоритмической сложности. Звучит заумно, но на практике обычно не вызывает сложностей. Мы не будем строить графики и выдвигать математическое доказательство почему O(1) лучше O(n), но нам нужно в самом начале понять, что O(1) означает. Сложность алгоритмов оценивается по двум критериям – временная и по затрачиваемой памяти, потому что и время, и память не безграничны, и мы хотим понять как много мы будем их тратить в сравнении одного и другого пути развития. Нам на данном этапе понадобиться только 3 из них:
O(1) – самый желанный, простой в понимании и сложный в достижении. Означает, что при неограниченно растущей нагрузке мы будем делать то, что нам требуется за условную единицу времени, эта единица времени может быть и секунда и день, но глобально это одно и то же время для любой нагрузки, которое будет испытывать алгоритм.
O(n) – гораздо хуже O(1), но часто приемлемый, а иногда максимально возможный. Означает, что единица времени растет линейно с ростом нагрузки, примером может служить АЗС – в единицу времени колонка качает 1 л. топлива: чтобы перекачать 100 литров, нам нужно в 100 раз больше колонок с той же производительностью.
O(logN) – опять же, хуже O(1), но лучше O(n). Чтобы понять, лучше почитать больше литературы, связанной со сложностью. Но если очень приближенно, то смысл в том, что алгоритм на каждом этапе дает выигрыш в 2 раза, центральная идея бинарных деревьев основана именно на этом (к деревьям мы еще вернемся чуть ниже), данная сложность дает большой профит на большой объеме данных.
Hashtable
Начнем рассказ о HashTable – данная структура доступна для использования и сейчас (.net6) и как любой объект его можно создать:
var hashTable = new Hashtable();
и мы можем даже что-то там хранить в виде пары ключ-значение:
hashTable.Add("company", "Itransition");
hashTable.Add(56, "numberKey");
Но тут мы получаем проблему использования, а именно: и ключ и значение не типизированы, и могут быть чем угодно, что обеспечивается тем, что и ключ, и значение хранится в виде object, что приводит к проблеме boxing/unboxing. А это дополнительные расходы ресурсов – как памяти, так и времени. В общем, в явном виде им уже давно никто не пользуется.
Dictionary<TKey,TValue>
Любой разработчик .Net, который слышит слово Dictionary, представляет себе конструкцию вида:
var dictionary = new Dictionary<TKey, TValue>();
где TKey – это ключ, а TValue – значение, которое соответствует этому ключу. Использование такой структуры данных очень эффективно с точки зрения скорости поиска, вставки и объема используемой памяти. В среднем сложность поиска и вставки составляет O(1), в худшем же O(n) – почему это так, останется за рамками данной статьи.
Чтобы добиться такого шикарного результата, dictionary внутри себя использует HashTable, но в свою очередь dictionary типизирован, т.е. если пользователь создал dictionary для хранения ключей тип число, а для значений объекты котиков, использовать строки он уже не сможет – компилятор будет против) – и это убирает проблему boxing/unboxing, что существенно может сэкономить дополнительные накладные расходы.
Если не используется многопоточность, то dictionary является шикарным выбором для хранения и получения сохраненного результата.
ConcurrentDictionary<TKey,TValue>
Вот это штука очень крутая – в мире, когда все хотят многопоточный код, этот вид dictionary как эликсир жизни и скорости в одном флаконе. Реализуется потокобезопасность с помощью механизма Monitor, который вешает lock на запись значения по ключу, что в свою очередь и закрывает проблему одновременной записи в словарь двух одинаковых значений одновременно. Как раз из-за того, что нет гарантии, что значение было записано в названия методов, добавлено Try – TryAdd(), TryUpdate(), TryDelete()
Но вдруг вы хотите усложнить себе жизнь, тогда для вас есть
Hashtable.Synchronized(hashTable);
Данный HashTable также потокобезопаснен, но хранит и ключ, и значение в виде object – и опять же мы встречаемся с проблемой boxing/unboxing.
ImmutableDictionary<TKey,TValue>
Как и ConcurrentDictionary, данный вид dictionary является потокобезопасным, т.к. не существует проблемы одновременной записи, мы можем только получать сохраненные значения. Если посмотреть, то у данного dictionary есть методы добавления новых ключ-значение, но на самом деле этого не происходит, потому что при добавлении новой записи в ImmutableDictionary, мы получим новый словарь с копией всех данных из первого словаря, плюс еще одна запись, а исходный не изменится.
А самое интересное, что внутри это не HashTable, а AVL Tree, для которого скорость поиска и вставки составляет уже O(logN). Что такое AVL Tree и деревья в общем, останется за пределами данной статьи.
Производительность
Мы никогда не должны основываться на «мне так кажется»: цифры лучше показывают реальность, нежели ощущения. Поэтому нужно измерять: все что измерено, то оторвано от стереотипов. Для себя я использую BenchmarkDotNet – пакет для .net приложений, позволяющий очень быстро и просто оценить: лучше/хуже стало и на сколько. За примерами использования лучше обратиться к документации или посмотреть в код. Для моей задачки показать, чем отличаются словари, этот инструмент подходит идеально. Для всех тестов будет использоваться .NET SDK=6.0.101
Для начала давайте посмотрим, как словари справляются с вставкой 100, 1000 и 10000 значений
Method | Target | Mean | Error | StdDev | Rank | Allocated |
Dictionary_Add | 100 | 11.50 us | 0.036 us | 0.032 us | 1 | 11 KB |
Hashtable_Add | 100 | 16.33 us | 0.282 us | 0.325 us | 2 | 14 KB |
ConcurrentDictionary_Add | 100 | 20.34 us | 0.072 us | 0.060 us | 3 | 25 KB |
ImmutableDictionary_Add | 100 | 62.62 us | 0.900 us | 0.842 us | 4 | 49 KB |
Dictionary_Add | 1000 | 118.59 us | 0.398 us | 0.372 us | 5 | 114 KB |
Hashtable_Add | 1000 | 162.68 us | 0.968 us | 0.905 us | 6 | 140 KB |
ConcurrentDictionary_Add | 1000 | 209.76 us | 2.043 us | 1.811 us | 7 | 220 KB |
ImmutableDictionary_Add | 1000 | 903.69 us | 9.405 us | 7.854 us | 8 | 723 KB |
Dictionary_Add | 10000 | 1,254.97 us | 11.560 us | 10.248 us | 9 | 1,051 KB |
Hashtable_Add | 10000 | 1,903.21 us | 27.632 us | 25.847 us | 10 | 1,335 KB |
ConcurrentDictionary_Add | 10000 | 2,583.28 us | 43.599 us | 40.782 us | 11 | 1,782 KB |
ImmutableDictionary_Add | 10000 | 12,779.01 us | 206.515 us | 183.070 us | 12 | 9,601 KB |
Видно, что обычный Dictionary 100 записей вставляет за 12 наносекунд, а 1000 примерно за 120.от мы и получили почти O(1) сложность вставки одной записи! HashTable чуть медленнее, но он хранит и возвращает все в object и нет проверки на уровне компиляции. ConcurrentDictionary еще немного медленнее – это связано с накладными расходами, обеспечивающими потокобезопасность, но очень даже неплохо для такой мощной системы! Самый же медленный – это ImmutableDictionary. еще прошу обратить внимание на потребляемую им память: при каждой итерации она значительно больше, чем у всех собратьев. Это связано с тем, что при каждой вставке в новый словарь копируются все значения из старого словаря и еще одно, которое мы хотим добавить. Еще прошу заметить, насколько он медленнее при вставке новой записи – все потому что данные в нем хранятся без использования HashTable, а с использованием AVL Tree, у которого сложность вставки O(logN).
Теперь предлагаю посмотреть, как словари справляются с поиском из 1000 значений при 100, 1000 и 10000 попытках.
Method | Target | Mean | Error | StdDev | Rank | Gen 0 |
ConcurrentDictionary_Get | 100 | 9.276 us | 0.0784 us | 0.0695 us | 1 | - |
Dictionary_Get | 100 | 9.374 us | 0.0549 us | 0.0487 us | 1 | - |
Hashtable_Get | 100 | 10.651 us | 0.0537 us | 0.0476 us | 2 | 0.7629 |
ImmutableDictionary_Get | 100 | 14.019 us | 0.0436 us | 0.0340 us | 3 | - |
ConcurrentDictionary_Get | 1000 | 84.548 us | 0.2929 us | 0.2596 us | 4 | - |
Dictionary_Get | 1000 | 90.155 us | 0.3177 us | 0.2817 us | 5 | - |
Hashtable_Get | 1000 | 108.548 us | 0.4798 us | 0.4253 us | 6 | 7.5684 |
ImmutableDictionary_Get | 1000 | 140.010 us | 0.2568 us | 0.2276 us | 7 | - |
ConcurrentDictionary_Get | 10000 | 891.774 us | 3.0775 us | 2.7281 us | 8 | - |
Dictionary_Get | 10000 | 936.266 us | 2.9327 us | 2.7433 us | 9 | - |
Hashtable_Get | 10000 | 1,082.217 us | 7.7229 us | 6.8461 us | 10 | 76.1719 |
ImmutableDictionary_Get | 10000 | 1,391.331 us | 4.9817 us | 4.4161 us | 11 | - |
Тут видно, что время поиска у Dictionary и ConcurrentDictionary практически одинаковое. Оно на самом деле является одинаковым в пределах погрешности и незначительно изменяется при разных прогонах. Поэтому можно считать, что скорость поиска, в отличие от вставки, у обеих коллекций одинаковая и она очень хорошая, даже отличная! Для HashTable можно заметить, что выделяется память, а в других словарях такого нет – это как раз связано с тем, что HashTable хранит и ключ, и значение в виде object, и есть накладные расходы на boxing/unboxing последующую чистку возникшего мусора с помощью Garbage Collection. Часто это не тривиально и просто так не увидеть, читая код, поэтому еще раз призываю Вас измерять свой код на производительность. И самый медленный из всех опять же ImmutableDictionary, что наводит на следующую мысль: нужно очень внимательно выбирать структуры данных для использования, так есть области применения, где ImmutableDictionary раскрывается с наилучшей стороны – там, где нужно чтобы коллекция была неизменяема – вот так поворот!
Как можно все испортить
Для завершения расскажу, как можно взять отличный Dictionary (я надеюсь, что к этому моменту вы уже с уважением относитесь к этой структуре данных) и испортить его функционал поиска в 257 раз! Будем сравнивать поиск по ключу через метод TryGetValue, ContainsKey, ручной поиск по ключу, Linq.FirstOrDefault. Взглянем на результаты:
Method | Mean | Error | StdDev | Ratio | RatioSD | Gen 0 |
GetValueByKeyWithTryGet | 7.550 ns | 0.0767 ns | 0.0718 ns | 0.96 | 0.02 | - |
GetValueByKey | 7.864 ns | 0.1307 ns | 0.1158 ns | 1 | 0 | - |
GetValueByKeyManual | 571.320 ns | 7.4372 ns | 6.5929 ns | 72.66 | 1.37 | - |
GetValueByKeyWithLinq | 1,839.986 ns | 30.7720 ns | 32.9257 ns | 234.3 | 5.68 | 0.0343 |
Вот это да!!! Между TryGetValue и FirstOrDefault разница в 257 раз – и это на словаре в 100 записей, и дополнительно нужно выделять память и еще создавать работу для GC, подчищая за нами. С умом подходите к использованию методов.
Репозитоторий для тех, кому интересно запустить у себя.