Каково различие между SortedList и SortedDictionary?

Question

Каково различие между SortedList и SortedDictionary?

Я бы предложил просто перетасовать массивы вместо того, чтобы пытаться распространить это на коллекции в целом:

extension Array {
    mutating func shuffle () {
        for i in (0..<self.count).reversed() {
            let ix1 = i
            let ix2 = Int(arc4random_uniform(UInt32(i+1)))
            (self[ix1], self[ix2]) = (self[ix2], self[ix1])
        }
    }
}

251

c# .net generics sortedlist sorteddictionary

задан Shaul says I Support Monica 27 July 2015 в 03:42

2 ответа

Посетите страницу MSDN для SortedList :

Из раздела примечаний:

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

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

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

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

13

ответ дан 23 November 2019 в 02:54

Другие вопросы по тегам:

c# .net generics sortedlist sorteddictionary

Похожие вопросы:

score 287 · Accepted Answer

Да - их рабочие характеристики существенно различаются. Вероятно, было бы лучше называть их SortedList и SortedTree , поскольку это более точно отражает реализацию.

Просмотрите документы MSDN для каждого из них ( SortedList ], SortedDictionary ) для получения подробной информации о производительности для различных операций в разных ситуациях. Вот хорошее резюме (из документации SortedDictionary ):

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

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

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

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

( SortedList фактически поддерживает отсортированный массив, а не использует дерево. Он по-прежнему использует двоичный поиск для поиска элементов.)