SortedList<>, SortedDictionary<> и словарь<>

StackOverflow https://stackoverflow.com/questions/1427147

Вопрос

Я нахожу это SortedList<TKey, TValue> SortedDictionary<TKey, TValue> и Dictionary<TKey, TValue> реализовать те же интерфейсы.

  1. Когда нам следует сделать выбор в пользу SortedList и SortedDictionary над Dictionary?
  2. В чем разница между SortedList и SortedDictionary в плане применения?
Это было полезно?

Решение

<Ол>

  • При переборе элементов любого из двух элементов они будут отсортированы. Не так с Словарём < T, V > .

  • MSDN устраняет разницу между SortedList < ; T, V > и SortedDictionary < T, V > :

    •   

    Универсальный класс SortedDictionary (TKey, TValue) является двоичным поиском.   дерево с поиском O (log n), где n - количество элементов в   словарь. В этом отношении он похож на SortedList (TKey,   TValue) родовой класс. Два класса имеют похожие объектные модели, и   оба имеют O (log n) поиска. Где два класса отличаются в   Использование памяти и скорость вставки и удаления:

         

    SortedList (TKey, TValue) использует меньше памяти, чем SortedDictionary (TKey,   TValue).      

    SortedDictionary (TKey, TValue) имеет более быструю вставку и удаление   операции для несортированных данных: O (log n), а не O (n) для   SortedList (TKey, TValue).

         

    Если список заполняется сразу из отсортированных данных,   SortedList (TKey, TValue) работает быстрее, чем SortedDictionary (TKey,   TValue).

    Другие советы

    введите описание изображения здесь

    Я бы упомянул разницу между словарями.

    На приведенном выше рисунке показано, что Dictionary < K, V > в любом случае равен или быстрее, чем аналог Sorted , но если требуется порядок элементов, например, чтобы распечатать их, Sorted выбирается один.

    Src: http: // people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

    Чтобы подвести итоги теста производительности - SortedList против SortedDictionary и против Словарь против Hashtable , результаты от лучших к худшим для разных сценариев:

    Использование памяти: 

    SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

    Вставки: 

    Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

    Операции поиска: 

    Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

    Операции цикла foreach 

    SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
    <Ол>

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

  • SortedList и SortedDictionary делают одно и то же, но реализованы по-разному, поэтому имеют разные сильные и слабые стороны. объяснено здесь .

    • Я вижу, что предлагаемые ответы ориентированы на производительность.Статья, представленная ниже, не содержит ничего нового относительно производительности, но объясняет основные механизмы.Также обратите внимание, что он не фокусируется на трех Collection Типы, упомянутые в вопросе, но касаются всех типов. System.Collections.Generic пространство имен.

    http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

    Выдержки:

    Словарь<>

    Словарь, вероятно, является наиболее часто используемым ассоциативным контейнерным классом.Словарь — самый быстрый класс для ассоциативного поиска/вставки/удаления, потому что он использует хеш-таблицу под обложкой.Поскольку ключи хешированы, тип ключа должен правильно реализовывать GetHashCode() и Equals() соответствующим образом, или вам следует предоставить внешний IEqualityComparer для словаря при его создании.Время вставки/удаления/поиска элементов в словаре амортизируется постоянное время — O(1) — что означает, что независимо от того, насколько велик словарь, время, необходимое для поиска чего-либо, остается относительно постоянным.Это очень желательно для высокоскоростного поиска.Единственный обратная сторона заключается в том, что словарь по своей природе использует хеш-таблицу неупорядочен, поэтому вы не можете легко перемещаться по элементам словаря по порядку.

    Сортированный словарь<>

    SortedDictionary похож на Dictionary по использованию, но сильно отличается по реализации.Тем SortedDictionary использует скрытое двоичное дерево для поддержания порядка элементов по ключу..В результате сортировки тип, используемый для ключа, должен правильно реализовывать IComparable. чтобы ключи можно было правильно отсортировать.Сортированный словарь тратит немного времени на поиск ради возможности поддерживать элементы в порядке, поэтому время вставки/удаления/поиска в отсортированном словаре является логарифмическим - O(log n).Вообще говоря, используя логарифмическое время, вы можете удвоить размер коллекции, и для поиска элемента достаточно выполнить только одно дополнительное сравнение.Используйте SortedDictionary, если вам нужен быстрый поиск, но при этом вы хотите поддерживать порядок в коллекции по ключу.

    Сортированный список<>

    SortedList — это еще один класс сортированного ассоциативного контейнера в универсальных контейнерах.Еще раз SortedList, как и SortedDictionary, использует ключ для сортировки пар ключ-значение.Однако в отличие от SortedDictionary, элементы в SortedList хранятся как отсортированный массив элементов..Это означает, что вставки и удаления являются линейными (O(n)), поскольку удаление или добавление элемента может включать в себя сдвиг всех элементов вверх или вниз в списке.Однако время поиска составляет O(log n), поскольку SortedList может использовать двоичный поиск для поиска любого элемента в списке по его ключу.Так почему же вам вообще захочется это сделать?Что ж, ответ заключается в том, что если вы собираетесь загрузить SortedList заранее, вставки будут медленнее, но поскольку индексирование массива происходит быстрее, чем следование по ссылкам на объекты, поиск будет немного быстрее, чем SortedDictionary.Еще раз я бы использовал это в ситуациях, когда вам нужен быстрый поиск и вы хотите поддерживать коллекцию в порядке по ключу, а также где вставки и удаления происходят редко.

    Предварительное резюме основных процедур

    Обратная связь очень приветствуется, так как я уверен, что не все понял правильно.

    • Все массивы имеют размер n.
    • Несортированный массив = .Add/.Remove равен O(1), а .Item(i) равен O(n).
    • Отсортированный массив = . Добавлять/. Remove равно O(n), но . Элемент(i) равен O(1).

    Словарь

    Память

    KeyArray(n) -> non-sorted array<pointer>
    ItemArray(n) -> non-sorted array<pointer>
    HashArray(n) -> sorted array<hashvalue>

    Добавлять

    1. Добавлять HashArray(n) = Key.GetHash # О(1)
    2. Добавлять KeyArray(n) = PointerToKey # О(1)
    3. Добавлять ItemArray(n) = PointerToItem # О(1)

    Удалять

    1. For i = 0 to n, находить i где HashArray(i) = Key.GetHash # O(log n) (отсортированный массив)
    2. Удалять HashArray(i) # O(n) (отсортированный массив)
    3. Удалять KeyArray(i) # О(1)
    4. Удалять ItemArray(i) # О(1)

    Получить предмет

    1. For i = 0 to n, находить i где HashArray(i) = Key.GetHash # O(log n) (отсортированный массив)
    2. Возвращаться ItemArray(i)

    Переберите

    1. For i = 0 to n, возвращаться ItemArray(i)

    Сортированный словарь

    Память

    KeyArray(n) = non-sorted array<pointer>
    ItemArray(n) = non-sorted array<pointer>
    OrderArray(n) = sorted array<pointer>

    Добавлять

    1. Добавлять KeyArray(n) = PointerToKey # О(1)
    2. Добавлять ItemArray(n) = PointerToItem # О(1)
    3. For i = 0 to n, находить i где KeyArray(i-1) < Key < KeyArray(i) (с использованием ICompare) # На)
    4. Добавлять OrderArray(i) = n # O(n) (отсортированный массив)

    Удалять

    1. For i = 0 to n, находить i где KeyArray(i).GetHash = Key.GetHash # На)
    2. Удалять KeyArray(SortArray(i)) # О(1)
    3. Удалять ItemArray(SortArray(i)) # О(1)
    4. Удалять OrderArray(i) # O(n) (отсортированный массив)

    Получить предмет

    1. For i = 0 to n, находить i где KeyArray(i).GetHash = Key.GetHash # На)
    2. Возвращаться ItemArray(i)

    Переберите

    1. For i = 0 to n, возвращаться ItemArray(OrderArray(i))

    Сортированный список

    Память

    KeyArray(n) = sorted array<pointer>
    ItemArray(n) = sorted array<pointer>

    Добавлять

    1. For i = 0 to n, находить i где KeyArray(i-1) < Key < KeyArray(i) (с использованием ICompare) # O(логарифм n)
    2. Добавлять KeyArray(i) = PointerToKey # На)
    3. Добавлять ItemArray(i) = PointerToItem # На)

    Удалять

    1. For i = 0 to n, находить i где KeyArray(i).GetHash = Key.GetHash # O(логарифм n)
    2. Удалять KeyArray(i) # На)
    3. Удалять ItemArray(i) # На)

    Получить предмет

    1. For i = 0 to n, находить i где KeyArray(i).GetHash = Key.GetHash # O(логарифм n)
    2. Возвращаться ItemArray(i)

    Переберите

    1. For i = 0 to n, возвращаться ItemArray(i)

    Пытаюсь назначить оценка производительности для каждого случая, представленного @Lev, я использовал следующие значения:

    • О(1) = 3
    • О (логарифм п) = 2
    • О (п) = 1
    • О(1) или О(n) = 2
    • O(log n) или O(n) = 1,5

    Результаты (выше = лучше):

    Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

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

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top