Какова пространственная сложность радикального дерева?
Я всегда был обеспокоен использованием пространства радикс-дерева, но я не нашел никаких полезных обсуждений по этому вопросу.
Теперь давайте предположим, что у нас есть реализация основанного на ядре дерева, аналогичная linux radix-tree.c, которая принимает целое число и использует каждые 6 бит для индексации следующей позиции в дереве. Я легко могу вспомнить случаи, когда использование пространства радикального дерева намного больше, чем двоичные деревья поиска. Пожалуйста, поправьте меня, если я ошибаюсь:
Варианты использования: (0,1,1,1,1), (1,1,1,1,1), (2,1,1,1,1), ... (63,1,1,1), 1).
Здесь просто для удобства я использую (a, b, c, d, e) для представления 30-битного целочисленного ключа, где каждый элемент соответствует 6-битному значению. а является MSB и е является LSB.
Корень дерева:
Для этого варианта использования высотное дерево будет иметь высоту 5, а каждый ключ будет занимать 4 отдельных узла, поскольку они находятся на разных поддеревьях корня. Таким образом, будет ((5-1) * 64 + 1) = 257 узлов.
Каждый узел содержит 2^6 = 64 указателя, поэтому он будет использовать 257 * 64 * 4Byte = 65KB
Двоичное дерево поиска
Нам важно только, сколько там ключей. В этом случае он имеет 64 ключа.
Предположим, что каждый узел BST использует 3 указателя на узел, он будет использовать 64 * 3 * 4Byte = 768 байт.
сравнение
Похоже, основание дерева очень неэффективно. Он использует ~100 раз больше места, чем двоичное дерево поиска при одинаковом количестве узлов! Я не понимаю, почему он используется даже в ядре Linux.
Я что-то пропустил? Благодарю.
3 ответа
Вы просили о сложности пространства, так что давайте разберемся.
Если мы рассматриваем ненулевой указатель на лист как значение, представляющее интерес, то нетрудно доказать противоречие, что наихудшим случаем является полностью заполненное дерево с одним значением на узел листа.
Если ветвление N-way (в вашем случае использования 64), а высота - H (в вашем случае использования 5), в этом дереве есть N^(H-1) листовых узлов, хранящих равное количество значений. Общее количество узлов
1 + N + N^2 + ... N^(H-1) = (N^H - 1) / (N-1)
Таким образом, требование к хранению, измеренное в указателях, в N раз больше.
(N^H - 1) [N / (N-1)]
Это дает эффективность хранения
(N^H - 1) [N / (N-1)]
--------------------
N^(H-1)
Это общее количество указателей, деленное на количество действительных указателей данных.
Когда N становится больше, это приближается к N. В вашем примере использования это на самом деле 65.01 (для N=64). Таким образом, мы можем сказать, что сложность хранения равна O(NV), где V - количество значений данных, которые должны быть сохранены.
Хотя мы пришли сюда с анализом первых принципов, это имеет смысл. Хранилище на уровне листа всего дерева доминирует над остальными почти в Н. Размер этого хранилища равен NV.
Конечно, преимущество деревьев с такими огромными факторами ветвления (как, например, B-деревья в базах данных) заключается в том, что для перехода к нужному листу требуется меньше обходов узлов.
Более того, когда каждый обход представляет собой поиск в одном массиве, как в основном дереве, вы не можете получить намного быстрее.
В вашем случае идеально сбалансированное двоичное дерево поиска потребовало бы до 30 сравнений с сопутствующими ветвями, очищающими конвейер. Это по сравнению с 5 операциями индексации массива может быть намного медленнее. Индексирование массива имеет тенденцию быть быстрее, чем сравнение, потому что это не ветвящийся код. Но даже если они одинаковы, двоичному дереву потребуется только 2^5=32 элемента, чтобы вызвать ту же работу индексирования, что и радикальному дереву, содержащему 2^30 элементов.
Чтобы обобщить это, двоичное дерево из 2^H элементов потребует таких же усилий по поиску, как и дерево индексов, способное содержать N^(H-1) элементов, если сравнение ключей и операции с индексами массива имеют одинаковую стоимость.
Как уже говорили другие, если биты индекса для верхних уровней дерева стремятся к нескольким общим префиксам (то есть они являются старшими битами адресов одного и того же пространства VM), поведение хранилища радикального дерева в худшем случае не возникает,
Основное дерево в Linux изначально представляло собой структуру данных для поддержки кеша страниц, где такое распределение ключей (смещение файлов) встречается редко.
(FWIW, первоначальный вариант использовал Splay Tree, но Линус сказал нет:)
Основное дерево широкое и неглубокое, поэтому поиск в нем позволяет получить доступ к сравнительно небольшому количеству различных строк кэша, что, очевидно, весьма выгодно для производительности.
Он также обладает тем свойством, что локальность в доступах к кэшу страниц означает локальность в доступах к узлам оснований дерева, в отличие от альтернативных конструкций, таких как, например, хеш-таблица.
В корнях дерева очень часто используются длинные строки с общими / общими префиксами. в этом случае основание дерева будет гораздо более экономичным.
Для данных, которые вы указываете, это другая история.
редактировать
Хорошим примером длинных строк с префиксами является сохранение всех имен файлов с полным путем на вашем компьютере. С такими данными это будет более экономично, чем альтернативы, и будет очень быстро определять, существует имя файла или нет. Может даже быть быстрее в некоторых случаях, чем хеш-таблица.
Посмотрите на эти 2 файла:
- "c: \ Program Files (x86) \ Microsoft Visual Studio 12.0 \ VC \ include \ streambuf"
- "c: \ Program Files (x86) \ Microsoft Visual Studio 12.0 \ VC \ include \ string"
Их общий префикс: "c:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\str", который сохраняется только один раз.