Комментарии 16
Жаль нет объяснения, почему ручной по ключу настолько медленней.
Для ручного поиска используется цикл foreeach которая инициализирует Enumerator и мы бежим по все коллекции и сравиваем с Key - а это занимает время.
Есть ссылка на репозиторий - посмотрите метод GetValueByKeyManual(string key)
Видно, что обычный Dictionary 100 записей вставляет за 12 наносекунд, а 1000 примерно за 120.от мы и получили почти O(1) сложность вставки одной записи!
O(1) – самый желанный, простой в понимании и сложный в достижении. Означает, что при неограниченно растущей нагрузке мы будем делать то, что нам требуется за условную единицу времени, эта единица времени может быть и секунда и день, но глобально это одно и то же время для любой нагрузки, которое будет испытывать алгоритм
Время тут выросло в 10 раз, во столько же и нагрузка, что больше подходит под определение O(n)
Тут идея в том что не важно какого размера словарь, время вставки +- одинаковое. Время выросло в 10 раз, т.к. вставляется в 10 раз больше чисел, то время и ростет в 10 раз.
Линейный рост в данном случае будет если при вставке в 10 записей была 1 секунда, а при вставке в 100 записей - 10 секунд.
Так это как раз и есть O(n) - в 10 раз увеличилось кол-во данных, в 10 раз и время выросло. Линейная зависимость
Нет. Это о1. Неважно ваш словарь 10 или 100 элементов вы все равно добавляете новый элемент за Х времени. Оно не растет (понятно, коллизии и прочие худшие не в счёт).
Иначе по вашей логике доступ к элементу массива по индексу это о(н). Ведь если мне надо достать 1 элемент то это Х времени, а 10 элементов я достану за 10Х.
тема не раскрыта.
в итоге ведь Dictionary это наследник HashTable
+картина не полная без прочих таблиц аки List, Queue, e.t.c.
Dictionary<TKey,TValue> внутри себя использует массивы. ConcurrentDictionary<TKey, TValue> существенно медленней чем Dictionary<TKey,TValue> так как там есть еще дополнительный объект для хранения текущего состояния и в нем еще дополнительно массив для синхронизаций. И бакеты у него это не структуры как в Dictionary<TKey,TValue> а ссылочный тип. Поэтому, теоретически, он должен работать медленнее и создавать значительно больше трафика памяти, что будет напрягать GC.
Dictionary<TKey,TValue> - быстрый, но есть реализации, которые работают быстрее в плане Get, например здесь - там нет перебора по массиву и виртуальных вызовов для разрешения коллизий (в таблице он FastDictionary). Вот я померил на 1 миллионе элементов <string, int>:
BenchmarkDotNet=v0.12.1, OS=Windows 10.0.22000
Intel Core i7-10875H CPU 2.30GHz, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=6.0.101
| Method | Mean | Error | StdDev | Median |
|--------------------- |---------:|---------:|---------:|---------:|
| FastDictionary | 12.70 ns | 0.281 ns | 0.234 ns | 12.63 ns |
| Dictionary | 13.32 ns | 0.291 ns | 0.398 ns | 13.09 ns |
| ConcurrentDictionary | 16.39 ns | 0.289 ns | 0.365 ns | 16.25 ns |
А в вашем репо
for (int i = 0; i < Target; i++)
{
var key = Guid.NewGuid();
if (_concurrentDictionary.ContainsKey(key))
{
result = _concurrentDictionary[key];
}
}
цикл, создаени ключа, вызов ContainsKey - очень дорогие операции, вы их и мерили скорее всего
Как-то странно сравнивать с ConcurrentDictionary и с ImmutableDictionary, и не использовать потоков. Смысл в таком сравнении? "Если вам нужно нарезать хлеб, нет смысла брать швейцарский нож" - спасибо, кэп.
А сравните в конкурентном доступе. 2/8/32/128 потока. 95/5 чтения/записи, 50/50 ч/з, 99.9/0.1, 1/99 - это всё разные паттерны, реально встречающиеся в жизни (ну, может кроме 1/99: обычно, даже если "только пишем", то всё равно читаем перед этим).
Простите за недогование.
.Net Dictionary и как они обитают