Когда я должен использовать sorteddictionary вместо словаря

Как я писал в некоторых своих последних сообщениях, я до сих пор совершенно не знаком с миром С#, поэтому я написал небольшой ориентир для сравнения словаря, Hashtable, SortedList и SortedDictionary друг с другом. Тест проходит с 8000 итерациями и от 50 до 100000 элементов. Я тестировал добавление новых элементов, поиск элементов и цикл через некоторые элементы, все случайные. Результаты были такими, какие я ожидал от них, кроме результата SortedDictionary, который был очень запутан для меня... Это было просто медленно во всех результатах. Так что я пропустил некоторые слова о концепции сортированного словаря. Я уже спросил google, но все, что я узнал, было то, что другие пришли к одному и тому же результату теста. Немного отличаются в зависимости от их реализации. Опять мой вопрос: почему SortedDicrionary настолько медленнее, чем все остальные?

Ответ 1

A SortedDictionary реализуется как двоичное дерево поиска. Следовательно, доступ к элементу равен O (lg (n)). Словарь представляет собой хеш-таблицу и имеет сложность O (1) для доступа.

A SortedDictionary весьма полезен, когда вам нужны данные для сортировки (словарь не имеет определенного порядка). Словарь подходит для большинства случаев.

Ответ 2

Ответ заключается в простом использовании SortedDictionary, если вам нужен отсортированный словарь.

Помните, что, хотя в тестах он оказался самым медленным, он все равно не замедляется. Если вам нужно именно то, что делает SortedDictionary, это лучшее решение. То же самое делать с помощью Dictionary или SortedList будет намного медленнее.

Ответ 3

Снова мой вопрос: почему SortedDicrionary настолько медленнее, чем все остальные?

Этьен уже дал технический ответ раньше, но добавить более "простое" замечание: я бы предположил, что бит "Сортировка" в SortedDictionary ставит некоторые накладные расходы на вставки и даже извлекает элементы, как кажется из ответа Этьена.

Однако в реальном приложении SortedDictionary, вероятно, может обеспечить значительную производительность или "воспринимаемую производительность", если вам понадобится "уже отсортированный словарь" в свое время в вашем приложении.

Надеюсь, что это поможет.