Когда использовать SortedList ‹TKey, TValue› вместо SortedDictionary ‹TKey, TValue›?

Я не уверен, насколько точна документация MSDN по SortedList и SortedDictionary. Кажется, что оба реализованы с использованием двоичного дерева поиска. Но если SortedList использует двоичное дерево поиска, почему он будет намного медленнее при добавлении, чем SortedDictionary?

Во всяком случае, вот результаты некоторых тестов производительности.

Каждый тест работает с SortedList / SortedDictionary, содержащим 10 000 ключей int32. Каждый тест повторяется 1000 раз (Release build, Start without Debugging).

Первая группа тестов добавляет ключи в последовательности от 0 до 9 999. Вторая группа тестов добавляет случайные перемешанные ключи от 0 до 9 999 (каждое число добавляется ровно один раз).

***** Tests.PerformanceTests.SortedTest

SortedDictionary Add sorted: 4411 ms
SortedDictionary Get sorted: 2374 ms


SortedList Add sorted: 1422 ms
SortedList Get sorted: 1843 ms

***** Tests.PerformanceTests.UnsortedTest

SortedDictionary Add unsorted: 4640 ms
SortedDictionary Get unsorted: 2903 ms


SortedList Add unsorted: 36559 ms
SortedList Get unsorted: 2243 ms

Как и при любом профилировании, важна относительная производительность, а не реальные цифры.

Как видите, для отсортированных данных отсортированный список быстрее, чем SortedDictionary. Для несортированных данных SortedList извлекается немного быстрее, но примерно в 9 раз медленнее при добавлении.

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

Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary. Но это противоречит тому, что говорится в документации MSDN.

Я не знаю, почему MSDN говорит, что SortedList<TKey, TValue> использует двоичное дерево для своей реализации, потому что, если вы посмотрите на код с помощью декомпилятора, такого как Reflector, вы поймете, что это не так.

SortedList<TKey, TValue> - это просто массив, который со временем растет.

Каждый раз, когда вы вставляете элемент, он сначала проверяет, имеет ли массив достаточную емкость, если нет, воссоздается массив большего размера и в него копируются старые элементы (например, List<T>).

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

Чтобы массив оставался отсортированным, он перемещает (или подталкивает) все элементы, расположенные после позиции элемента, который должен быть вставлен, на одну позицию (с использованием Array.Copy()).

Eg :

// we want to insert "3" 

2  
4  <= 3
5
8
9
.      
.      
.  

// we have to move some elements first

2
.  <= 3
4 
5  |
8  v
9
.
.

Это объясняет, почему SortedList так плохо работает при вставке несортированных элементов. Он должен повторно копировать некоторые элементы почти при каждой вставке. Единственный случай, когда этого не нужно делать, - это когда элемент нужно вставить в конец массива.

SortedDictionary<TKey, TValue> отличается и использует двоичное дерево для вставки и извлечения элементов. Это также связано с некоторыми затратами при вставке, потому что иногда дерево необходимо повторно сбалансировать (но не при каждой вставке).

При поиске элемента с SortedList или SortedDictionary производительность очень похожа, потому что оба они используют двоичный поиск.

На мой взгляд, вам не следует никогда использовать SortedList только для сортировки массива. Если у вас очень мало элементов, всегда будет быстрее вставить значения в список (или массив), а затем вызвать метод Sort().

SortedList в основном полезен, когда у вас есть список уже отсортированных значений (например: из базы данных), вы хотите сохранить его отсортированным и выполнить некоторые операции, которые позволят использовать его сортировку (например: Contains() метод SortedList выполняет двоичный поиск вместо линейный поиск)

SortedDictionary предлагает те же преимущества, что и SortedList, но работает лучше, если значения для вставки еще не отсортированы.

РЕДАКТИРОВАТЬ: если вы используете .NET Framework 4.5, альтернативой SortedDictionary<TKey, TValue> является SortedSet<T>. Он работает так же, как SortedDictionary, с использованием двоичного дерева, но ключи и значения здесь те же.

Они предназначены для двух разных целей?

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

Но производительность?

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

+------------------+---------+----------+--------+----------+----------+---------+
| Collection       | Indexed | Keyed    | Value  | Addition |  Removal | Memory  |
|                  | lookup  | lookup   | lookup |          |          |         |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList       | O(1)    | O(log n) | O(n)   | O(n)*    | O(n)     | Lesser  |
| SortedDictionary | n/a     | O(log n) | O(n)   | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+

* Insertion is O(1) for data that are already in sort order, so that each 
  element is added to the end of the list (assuming no resize is required).

Резюме

Подводя итог, вам нужно SortedList<K, V>, когда:

1. вам нужен индексированный поиск.
2. желательно иметь меньшие накладные расходы на память.
3. ваши входные данные уже отсортированы (скажем, вы уже заказали их из db).

Вместо этого вы бы предпочли SortedDictionary<K, V>, когда:

1. относительная общая производительность имеет значение (в отношении масштабирования).
2. ваши входные данные неупорядочены.

Написание кода

И SortedList<K, V>, и SortedDictionary<K, V> реализуют IDictionary<K, V>, поэтому в вашем коде вы можете вернуть IDictionary<K, V> из метода или объявить переменную как IDictionary<K, V>. В основном скрывают детали реализации и код против интерфейса.

IDictionary<K, V> x = new SortedDictionary<K, V>(); //for eg. 

В будущем будет проще переключиться с любого из них, если вас не устраивают характеристики производительности одной коллекции.

Для получения дополнительной информации о двух типах коллекций см. Ссылку на исходный вопрос.

Визуальное представление различий в производительности.

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

Я стараюсь использовать SortedList как можно чаще, потому что он позволяет мне перебирать ключи и коллекции значений. Насколько мне известно, это невозможно с SortedDictionary.

Я не уверен в этом, но насколько мне известно, словари хранят данные в древовидных структурах, тогда как списки хранят данные в линейных массивах. Это объясняет, почему вставка и удаление словарей выполняется намного быстрее, поскольку приходится перемещать меньше памяти. Это также объясняет, почему вы можете перебирать SortedLists, но не SortedDictionary.

Важным для нас соображением является тот факт, что у нас часто есть небольшие словари (‹100 элементов), а текущие процессоры намного быстрее получают доступ к последовательной памяти, выполняя при этом несколько трудно предсказуемых ветвей. (т.е. повторение по линейному массиву, а не по дереву) Поэтому, когда в вашем словаре менее 60 элементов, SortedList ‹> часто является самым быстрым и наиболее эффективным с точки зрения памяти словарем во многих случаях использования.