Когда использовать SortedList <TKey, TValue> над SortedDictionary <TKey, TValue>?

Ответ 1

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

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

Каждый тест работает на SortedList/SortedDictionary, содержащий 10000 int32 ключей. Каждый тест повторяется 1000 раз (Выпуск сборки, Запуск без отладки).

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

***** 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 раз медленнее при добавлении.

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

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

Ответ 2

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

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

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

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

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

Например:

// 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, но работает лучше, если значения для вставки еще не отсортированы.

EDIT: если вы используете .NET Framework 4.5, альтернативой SortedDictionary<TKey, TValue> является SortedSet<T>. Он работает так же, как SortedDictionary, используя двоичное дерево, но ключи и значения здесь одинаковы.

Ответ 3

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

Существует не так много семантической разницы этих двух типов коллекции в .NET make. Они оба предлагают ключевой поиск, а также сохраняют записи в порядке сортировки ключей. В большинстве случаев вам будет в порядке с любым из них. Возможно, единственным отличием будет разрешение с индексированным извлечением 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>, когда:

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

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

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

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

Оба 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. 

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

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

Ответ 4

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

Ответ 5

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

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

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

Ответ 6

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