Comments 15
Так тут, скорее, вопрос не в «плохо решалась» а в «не подходит». То есть, он нужен в случаях, когда необходимо поддерживать упорядоченность ключей в словаре. Например, у меня это были даты DateTime и их нужно было хранить в упорядоченном виде, потому что алгоритм предполагал их перебор по порядку.
В качестве обмена опытом: в сценариях, где важна [даже относительно] высокая производительность SortedDictionary не подходит: производительность добавления ожидаемая, но на каждое добавление происходить выделение памяти, скорость поиска ожидаемо невысокая, перечисление медленное, при перечислении выделяет память.
SortedList, к слову, тоже так себе. Не помню уже кто был быстрее, кто медленнее, помоему SortedList побыстрее, но точно размещает меньше индивидуальных инстанцев в куче.
При необходимости рекомендую проанализировать сценарий и написать свой специализированный компонент.
С другой стороны, в клиентском приложении на ЮИ не на горячем пути вполне применим.
Если же нам важно поддерживать порядок ключей в словаре ВСЕ ВРЕМЯ работы с ним, то нам следует использовать SortedDictionary
Было бы полезно описать, когда именно это может быть нужно, в каких кейсах? Потому что сейчас это выглядит как капитанский совет, для новичка абсолютно бесполезный, имхо
Зачем вы выделили, кстати, 'все время' можно иначе как то порядок поддерживать?
Во-вторых, словарь - одна из самых часто используемых структур данных и при разработке бывает полезно понимать, какие у нее есть подводные
Про подводные ни слова не написали в итоге
Было бы полезно описать, когда именно это может быть нужно, в каких кейсах?
Например, когда нужно перебирать элементы в порядке значения их ключа (для обычного Dictionary порядок элементов не определен). Но, судя по вашей критике, вы и так это знаете :)
Например, когда нужно перебирать элементы в порядке значения их ключа
Для этого есть SortedList. В сравнении с SortedDictionary у сортированного списка есть недостаток в виде O(n) на добавление/удаление (против O(log n) у сортированного словаря), но он шустрее в перечислениях и памяти меньше ест так как внутренне он не на базе bst, а на базе двух массивов реализован.
"Все время" я выделил, так как порой мы можем выполнить все необходимые операции над обычным словарем, а потом уже вернуть отсортированную через OrderBy версию. Из-за разницы между 
и 
нам не стоит поддерживать сортировку все время, если это важно только для вывода. Хотя возможно тут очевидный пример, который не вписывается в случаи применения SortedDictionary.
Под подводными я отметил, что эффективность Dictionary зависит от качества хеш функции, и что при частом росте числа элементов, мы будем все время спотыкаться об изменение размера бакетов, что замедлит наши операции вставки. С SortedDictionary основным подводным является сложность выполнения операций, про которую я писал.
Если под ожидаемыми подводными имелась ввиду потокобезопасность, пожалуй да, моя недоработка, сегодня допишу. Спасибо.
Постараюсь так же более явно выделить подводные описанные выше.
Интересно, кстати, почему в SortedDictionary внутренние объекты реализаций коллекций ключей и значений Keys и Values (SortedDictionary.KeyCollection и SortedDictionary.ValueCollection) не являются реализациями IList? В некоторых случаях бывало бы удобно обращаться напрямую по индексу внутрь этих коллекций, но не дают!
меня пару раз об этом спросили на собеседованиях и в первый раз я вообще потерялся с ответом
Программист не обязан знать вообще всё.
SortedDictionary я на своей практике пытался использовать ровно один раз. И то в итоге выбросил код, т.к. реализовать решение другим образом оказалось эффективнее.
Было бы крайне интересно познакомиться с каким-нибудь настоящим практическим примером, где выбор SortedDictionary позволил эффективно решить задачу, которая плохо решалась стандартным словарём.
Теоретически оно понятно, но кто ж будет бенчмаркать всё подряд, на всякий случай подставляя другую реализацию словаря, а вдруг повезёт? :)
В качестве обмена опытом: в сценариях, где важна [даже относительно] высокая производительность SortedDictionary не подходит: производительность добавления ожидаемая, но на каждое добавление происходить выделение памяти, скорость поиска ожидаемо невысокая, перечисление медленное, при перечислении выделяет память.
SortedList, к слову, тоже так себе. Не помню уже кто был быстрее, кто медленнее, помоему SortedList побыстрее, но точно размещает меньше индивидуальных инстанцев в куче.
При необходимости рекомендую проанализировать сценарий и написать свой специализированный компонент.
С другой стороны, в клиентском приложении на ЮИ не на горячем пути вполне применим.
Внутри SortedDictionary находится BST, а внутри SortedList обычный отсортированный список. SortedList может выиграть (за счет более компактного представления в памяти) в сценарии, когда коллекция изначально наполняется (особенно если поступающие данные уже более-менее отсортированы), а после только читаются.
SortedListможет выиграть (за счет более компактного представления в памяти) в сценарии, когда
SortedList выигрывает в любом сценарии, когда нам нужна именно отсортированная коллекция - он гораздо лучше при перечислении (плюс предоставляет доступ по индексу). SortedDictionary при каждом вызове GetEnumerator создаёт Stack и в дальнейшем его использует, что может приводить к выделению одного или более массивов в куче - в зависимости от глубины дерева.
Если же нам не нужен доступ перечислением - то нам не нужны и SortedList/SortedDictionary, логично?
Но и при добавлении и поиске в NET6/NET7 SortedList БЫЛ лучше - я поднял некоторые свои бенчмарки и обнаружил, что в NET8 SortedDictionary наконец-то стал быстрее при добавлении и поиске - приятный сюрприз, нужно будет посмотреть, что они изменили.
О чём я ещё забыл и сейчас обнаружил - SortedList тоже выделяет память в куче при каждом вызове GetEnumerator - но выделяет константный объём, 48 байтов. Не помню и не смотрел, что именно он выделяет, но это в любом случае лучше, чем Stack в SortedDictionary.
Результат бенчмарка для NET8 и NET7:
BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3007/23H2/2023Update/SunValley3)
12th Gen Intel Core i9-12900HK, 1 CPU, 20 logical and 14 physical cores
.NET SDK 8.0.100
[Host] : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2
| Method | Mean | Error | StdDev | Gen0 | Gen1 | Allocated |
|-------------------------------------------------- |--------------:|-------------:|-------------:|-------:|-------:|----------:|
| SortedDictionary_Reused_16_Enumerate | 95.47 ns | 1.599 ns | 1.496 ns | 0.0095 | - | 120 B |
| SortedList_Reused_16_Enumerate | 26.42 ns | 0.217 ns | 0.203 ns | 0.0038 | - | 48 B |
| SortedDictionary_Reused_1024_Enumerate | 5,530.26 ns | 31.941 ns | 28.315 ns | 0.0153 | - | 216 B |
| SortedList_Reused_1024_Enumerate | 1,307.96 ns | 14.057 ns | 13.149 ns | 0.0038 | - | 48 B |
| SortedDictionary_Reused_Random_Add_16 | 246.21 ns | 1.989 ns | 1.861 ns | 0.0610 | - | 768 B |
| SortedList_Reused_Random_Add_16 | 290.66 ns | 4.571 ns | 4.275 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_16_Get_16 | 380.68 ns | 2.345 ns | 2.193 ns | 0.0610 | - | 768 B |
| SortedList_Reused_Random_Add_16_Get_16 | 494.61 ns | 6.040 ns | 5.650 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_16_Get_160 | 1,208.38 ns | 10.448 ns | 9.773 ns | 0.0610 | - | 768 B |
| SortedList_Reused_Random_Add_16_Get_160 | 1,867.62 ns | 14.080 ns | 13.171 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_1024 | 56,606.91 ns | 276.384 ns | 258.530 ns | 3.9063 | 0.4883 | 49152 B |
| SortedList_Reused_Random_Add_1024 | 74,034.43 ns | 414.384 ns | 387.615 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_1024_Get_1024 | 102,770.04 ns | 334.855 ns | 296.840 ns | 3.9063 | 0.4883 | 49152 B |
| SortedList_Reused_Random_Add_1024_Get_1024 | 132,839.35 ns | 514.959 ns | 481.693 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_1024_Get_10240 | 507,017.59 ns | 922.908 ns | 818.134 ns | 3.9063 | - | 49154 B |
| SortedList_Reused_Random_Add_1024_Get_10240 | 570,572.80 ns | 2,884.269 ns | 2,408.496 ns | - | - | 2 B |
[Host] : .NET 7.0.14 (7.0.1423.51910), X64 RyuJIT AVX2
| Method | Mean | Error | StdDev | Gen0 | Gen1 | Allocated |
|-------------------------------------------------- |---------------:|------------:|------------:|-------:|-------:|----------:|
| SortedDictionary_Reused_16_Enumerate | 162.2 ns | 2.18 ns | 2.04 ns | 0.0095 | - | 120 B |
| SortedList_Reused_16_Enumerate | 102.1 ns | 0.36 ns | 0.30 ns | 0.0038 | - | 48 B |
| SortedDictionary_Reused_1024_Enumerate | 10,244.9 ns | 181.27 ns | 169.56 ns | 0.0153 | - | 216 B |
| SortedList_Reused_1024_Enumerate | 4,827.5 ns | 11.26 ns | 9.98 ns | - | - | 48 B |
| SortedDictionary_Reused_Random_Add_16 | 426.9 ns | 4.32 ns | 3.83 ns | 0.0610 | - | 768 B |
| SortedList_Reused_Random_Add_16 | 335.6 ns | 5.09 ns | 4.76 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_16_Get_16 | 813.4 ns | 9.89 ns | 8.77 ns | 0.0610 | - | 768 B |
| SortedList_Reused_Random_Add_16_Get_16 | 479.7 ns | 9.32 ns | 9.57 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_16_Get_160 | 3,838.5 ns | 12.82 ns | 12.00 ns | 0.0610 | - | 768 B |
| SortedList_Reused_Random_Add_16_Get_160 | 2,117.7 ns | 37.54 ns | 35.11 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_1024 | 101,679.9 ns | 323.19 ns | 269.88 ns | 3.9063 | 0.4883 | 49152 B |
| SortedList_Reused_Random_Add_1024 | 78,013.1 ns | 345.91 ns | 288.85 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_1024_Get_1024 | 202,480.1 ns | 745.23 ns | 660.63 ns | 3.9063 | 0.4883 | 49152 B |
| SortedList_Reused_Random_Add_1024_Get_1024 | 135,209.1 ns | 662.28 ns | 619.49 ns | - | - | - |
| SortedDictionary_Reused_Random_Add_1024_Get_10240 | 1,069,533.8 ns | 8,001.54 ns | 7,093.16 ns | 3.9063 | - | 49155 B |
| SortedList_Reused_Random_Add_1024_Get_10240 | 609,317.3 ns | 2,603.99 ns | 2,174.45 ns | - | - | 2 B |А, ну и да - SortedDictionary выделяет память в куче при каждом добавлении - это означает, что его не имеет особого смысла пулить/переиспользовать, а вот SortedList - стоит.
Плюс у SortedList можно установить Capacity, и он не будет выделять новые массивы при добалении элементов в рамках установленной capacity.
Ну и ещё одна мелочь - внутри у SortedList не список, а два массива - ключи и значения.
...что-то заигрался я в бенчмарки, но тут интересное:
При добавлении заранее отсортированных элементов у SortedList скорость ожидаемо растёт, а у SortedDictionary - неожиданно падает. Хотя если подумать - слишком часто приходится перебалансировать дерево.
В общем, нюансов у этих Sorted* масса, как я уже писал: если нужна производительность - скорее всего придётся писать своё специализированное.
Однако, если мы будем случайно подбирать размеры массива, мы можем плохо распределять загрузку значений, например, много чисел имеет одинаковый остаток от деления на 2 или другую степень этого замечательного числа. В противовес этому, у простых чисел по определению только два делителя единица и само число, поэтому вероятность, что остаток от деления двух разных чисел на третье простое число окажется одинаковым очень мала. За счет этого мы гарантируем, что при нормально работающей хеш функции, бакеты будут заполнены равномерно.
Не очень понятна вот эта мысль. Как простата числа размера массива бакетов может влиять на распределение значений по этим самым бакетам? Если хэш функция хорошая, то распределение по бакетам будет равномерным при любом размере. Да, в случае с 2(а это кстати тоже простое число) все значения будут в двух бакетах, но распределены они будут равномерно. Аналагично и для остатка от деления на 2^10 - значения будут распределены равномерно по 1024 бакетам.
Dictionary и SortedDictionary