Я видел несколько цитат об этом в Интернете, но официальной документации нет? Может ли кто-нибудь сказать мне, где я могу получить информацию об этом?
Является ли SortedDictionary красно-черным деревом?
Ответы (5)
Это не должно документироваться, поскольку это деталь реализации.
Например, существует более одной реализации SortedDictionary: есть реализация Microsoft и есть реализация Mono.
И реализация Mono действительно использует красно-черное дерево в своей текущей версии (2.10.9). Как и текущая версия .NET (это можно узнать, декомпилировав код, например, с помощью Reflector, ildasm.exe или встроенного средства просмотра IL в MonoDevelop).
Однако это вероятно изменится в будущем, поскольку на самом деле существуют более эффективные реализации (например, B-деревья).
Итак, еще раз: эта информация бесполезна, это деталь реализации, и она изменится с высокой вероятностью.
person
Konrad Rudolph
schedule
16.02.2013
Это не отвечает на вопрос.
- person Greg Graham; 08.05.2019
@GregGraham Как это не так? Я четко объясняю, что делают текущие (на момент ответа) реализации и почему на эту информацию не следует полагаться в будущем. Что еще вам не хватает в ответе?
- person Konrad Rudolph; 08.05.2019
Это официальная документация от MSDN< /a> страница;
Универсальный класс SortedDictionary представляет собой двоичное дерево поиска с извлечением O (log n), где n — количество элементов в словаре.
Является ли SortedDictionery красно-черным деревом?
Ну, я не слишком хорошо знаком с red-black tree< /a> но я только что декомпилировал класс SortedDictionary с помощью dotPeek (бесплатно), но с удалением красно-черного дерева алгоритм и код метода Remove() SortedDictionary не кажутся похожими. Итак, мои деньги за Нет.
SortedDictionary хранит свои ключи всегда отсортированными. Это позволяет избежать самостоятельной сортировки ключей. Его производительность поиска ниже, чем у Dictionary. Это имеет преимущества, если вам требуется отсортированная таблица поиска в памяти.
Dictionary lookup time: Close to O(1)
SortedDictionary lookup time: O(log n)
Дополнительные сведения см. на странице here.
person
Soner Gönül
schedule
16.02.2013
Не уверен, что вы декомпилировали, но
SortedDictionary внутри просто использует TreeSet, который является внутренним классом и, да, реализован в терминах красно-черного дерева.
- person Konrad Rudolph; 16.02.2013
@KonradRudolph Хм, я декомпилировал метод
Remove(), который использовал метод internal virtual bool DoRemove(T item), но это не похоже на что-то похожее с red-black tree (который представляет собой поиск по двоичному дереву) алгоритм удаления. Я пропустил здесь что?
- person Soner Gönül; 16.02.2013
На данный момент у меня нет доступа к реализации .NET (я работаю на Mac), но я проверил соответствующие ресурсы и эталонную реализацию Rotor (которая, конечно, не является официальной) и Я почти уверен, что
SortedDictionary действительно использует TreeSet, которое является красно-черным деревом.
- person Konrad Rudolph; 16.02.2013
Более того, статья MSDN на самом деле гарантирует, что (текущая реализация)
SortedDictionary является бинарным деревом поиска, поэтому ваша оценка метода DoRemove должна быть ошибочной. Сказав это, странно, что MSDN на самом деле конкретен в этом вопросе, потому что, как я написал в своем ответе, тот факт, что используется бинарное дерево поиска (а не обобщенное дерево поиска), является деталь реализации, и она обязательно изменится, поэтому этой информации нет места в MSDN.
- person Konrad Rudolph; 16.02.2013
Reference Source подтверждает, что это красно-черное дерево (по крайней мере, в 4.5.2); referencesource.microsoft.com/#System/compmod/system/
- person alexn; 20.02.2015
Документация, по-видимому, гарантирует O(log n) для извлечения из BST. Если они сообщают «в среднем» относительно возможных деревьев, то даже небалансирующие реализации могут утверждать это. Даже если бы это была гарантия наихудшего случая, этого вместе с BST недостаточно, чтобы сказать, реализовано ли оно как красно-черное дерево, не прибегая к декомпиляции. Это также может быть AVL, splay или какой-либо другой вариант балансировки.
Я вытащил точечный взгляд. О сборке системы 4.0.0.0. OrderedDictionary использует Treeset, который является подклассом SortedSet. Скорее всего, это красно-черное дерево. Однако это не типичный пример, похожий на многие примеры в Интернете, которые реализуют балансировку после вставки или удаления. Реализация в основном итеративна, и кажется, что вставка фиксирует цвета по пути вниз, а не после вставки (сверху вниз - есть пара статей о таком подходе). Что-то похожее было с удалением, но нет времени проверить. Конечно, не что-то прямо сопоставимое.
По крайней мере, я предполагаю, что у него должна быть аналогичная характеристика времени выполнения. К тому времени, когда он доходит до точки вставки/удаления, он мало что делает, так как все это было сделано по пути вниз.
person
ptthiem
schedule
23.08.2013
Со своей страницы MSDN:
Универсальный класс SortedDictionary представляет собой двоичное дерево поиска с извлечением O (log n), где n — количество элементов в словаре.
person
CodeCaster
schedule
16.02.2013
Вы можете декомпилировать его (например, с помощью Reflector) ... НО, поскольку это «деталь реализации», я бы не стал на это полагаться, его можно изменить в любое время с любым обновлением.
Не уверен, насколько актуальна такая деталь реализации, но если вам действительно нужно дерево RedBlack, ТОГДА реализуйте его явно ... все остальное будет "техническим долгом" / "ожиданием катастрофы" ИМХО.
person
Yahia
schedule
16.02.2013
Зачем декомпилировать, когда Microsoft выпустила .Net с открытым исходным кодом? referencesource.microsoft.com/#System/compmod/system/
- person nivs1978; 11.05.2016
