Вы задали здесь несколько замечательных вопросов:
- Является ли дерево слияния хорошей структурой данных для хранения 32-битных или 64-битных чисел? Или он предназначен для хранения более длинных цепочек?
- Чем дерево слияния отличается от дерева B?
- Дерево слияний выбирает b = w 1/5 , где w - размер машинного слова. Означает ли это, что b = 2 на 32-битной машине, и делает ли это просто двоичным деревом?
- Почему так много дискуссий о дереве слияния сосредоточено на эскизах?
- Существует ли визуализация дерева слияния, чтобы помочь понять, как работает структура?
Я бы хотел ответить на каждый из этих вопросов по очереди.
В1: Что вы храните в дереве слияния? Они хороши для 32-битных целых чисел?
Ваш первый вопрос был о том, какие деревья сплавов предназначены для хранения. Структура данных Fusion Tree специально разработана для хранения целых чисел, которые вписываются в одно машинное слово. В результате на 32-разрядной машине вы будете использовать дерево слияния для хранения целых чисел до 32 бит, а на 64-разрядной машине вы будете использовать дерево слияния для хранения целых чисел до 64 бит.
Деревья слияния не предназначены для обработки произвольно длинных цепочек битов. Конструкция деревьев слияния, к которой мы вскоре перейдем, основана на методике, называемой параллелизм на уровне слов , в которой отдельные операции над машинными словами (умножения, сдвиги, вычитания и т. д.) выполняются, чтобы неявно работать с большим набором чисел параллельно. Чтобы эти методы работали правильно, сохраняемые числа должны соответствовать отдельным машинным словам. (Технически возможно адаптировать здесь методы для работы с числами, которые вписываются в постоянное количество машинных слов.)
Но прежде чем мы пойдем дальше, мне нужно включить одну важную оговорку: деревья слияния представляют только теоретический интерес . Хотя деревья слияния по номиналу имеют отличные гарантии времени выполнения (O (log w n) времени на операцию, где w - размер машинного слова), фактические детали реализации таковы, что скрытая константа факторы огромны и являются серьезным препятствием для практического принятия. Оригинальная статья о деревьях слияния была в основном направлена на доказательство того, что можно было преодолеть нижнюю границу & Omega; (log n) для операций BST с помощью параллелизма на уровне слов и без учета затрат времени выполнения настенных часов. Таким образом, в этом смысле, если ваша цель в понимании деревьев слияния заключается в том, чтобы использовать их на практике, я бы рекомендовал остановиться здесь и искать другую структуру данных. С другой стороны, если вам интересно узнать, сколько скрытой мощности доступно в скромных машинных словах, тогда, пожалуйста, продолжайте читать!
Q2: Чем дерево слияния отличается от обычного B-дерева?
На высоком уровне вы можете думать о дереве слияния как о обычном B-дереве с добавлением некоторой дополнительной магии для ускорения поиска.
В качестве напоминания, B-дерево порядка b - это дерево поиска в нескольких направлениях, где каждый узел интуитивно хранит (примерно) b ключей. B-дерево - это дерево поиска в нескольких направлениях, означающее, что ключи в каждом узле хранятся в отсортированном порядке, а дочерние деревья хранят элементы, упорядоченные относительно этих ключей. Например, рассмотрим этот узел B-дерева:
+-----+-----+-----+-----+
| 103 | 161 | 166 | 261 |
+-----+-----+-----+-----+
/ | | | \
/ | | | \
A B C D E
Здесь A, B, C, D и E являются поддеревьями корневого узла. Поддерево A состоит из ключей, строго меньших 103, поскольку оно слева от 103. Поддерево B состоит из ключей между 103 и 161, поскольку поддерево B находится между 103 и 161. Аналогично, поддерево C состоит из ключей между 161 и 166 , поддерево D состоит из ключей между 166 и 261, а поддерево E состоит из ключей больше, чем 261.
Чтобы выполнить поиск в B-дереве, вы начинаете с корневого узла и неоднократно спрашиваете, в какое поддерево вам нужно спуститься, чтобы продолжить поиск. Например, если бы я хотел найти 137 в вышеупомянутом дереве, мне нужно было бы каким-то образом определить, что 137 находится в поддереве B. Есть два «естественных» способа, которыми мы могли бы сделать этот поиск:
- Запустите линейный поиск по ключам, чтобы найти место, куда нам нужно идти. Время: O (b), где b - количество ключей в узле.
- Запустите бинарный поиск по ключам, чтобы найти место, куда нам нужно идти. Время: O (log b), где b - количество ключей в узле.
Поскольку каждый узел в B-дереве имеет коэффициент ветвления b или больше, высота B-дерева порядка b равна O (log b n). Поэтому, если мы используем первую стратегию (линейный поиск), чтобы найти, в какое дерево спускаться, для поиска потребуется наихудшая работа O (b log b n), поскольку мы делаем O (b ) работа за уровень по уровням O (log b n). Забавный факт: количество b log b n сводится к минимуму, когда b = e, и становится все хуже, когда мы увеличиваем b за этот предел.
С другой стороны, если мы используем двоичный поиск, чтобы найти дерево, в которое нужно спуститься, время выполнения заканчивается O (log b & middot; log b n). Используя изменение базовой формулы для логарифмов, обратите внимание, что
log b & middot; log b n = log b & middot; (log n / log b) = log n,
так что время выполнения поиска таким образом равно O (log n), независимо от b. Это соответствует временным рамкам поиска обычного сбалансированного BST.
Магия дерева слияния заключается в том, чтобы найти способ определить, в какое поддерево спуститься во времени O (1). Позвольте этому погрузиться в течение минуты - мы можем иметь несколько дочерних элементов для каждого узла в нашем B-дереве, сохраненные в отсортированном порядке, и все же мы можем найти, между какими двумя ключами находится наш элемент во времени O (1)! Это явно нетривиально и является основной магией дерева слияния. Но пока, предполагая, что мы можем это сделать, обратите внимание, что время выполнения поиска в дереве слияний будет равно O (log b n), поскольку мы выполняем O (1) времени работы O (log ) b слоев) в дереве!
Вопрос теперь в том, как это сделать.
Q3: Дерево слияний выбирает b = w 1/5 , где w - размер машинного слова. Означает ли это, что b = 2 на 32-битной машине, и делает ли это просто двоичным деревом?
По техническим причинам, которые станут понятнее позже, дерево слияния работает, выбрав в качестве параметра ветвления для B-дерева значение b = w 1/5 , где w - машина размер слова. На 32-битной машине это означает, что мы выберем
b = w 1/5 = (2 5 ) 1/5 = 2,
и на 64-битной машине мы выбираем
b = w 1/5 = (2 6 ) 1/5 = 2 6/5 & asymp; 2,29
который мы, вероятно, округлим до 2. Значит ли это, что дерево слияния - это просто двоичное дерево?
Ответ "не совсем". В B-дереве каждый узел хранит от b - 1 до 2b - 1 всего ключей. С b = 2 это означает, что каждый узел хранит всего от 1 до 3 ключей. (Другими словами, наше B-дерево было бы 2-3-4, если вы знакомы с этой прекрасной структурой данных). Это означает, что мы будем разветвляться немного больше, чем обычное дерево двоичного поиска, но не намного больше.
Возвращаясь к нашей более ранней точке, деревья слияния представляют в основном теоретический интерес . Тот факт, что мы выбрали b = 2 на реальной машине и едва ли справились лучше обычного дерева двоичного поиска, является одной из многих причин, почему это так.
С другой стороны, если бы мы работали, скажем, на машине, размер слова которой составлял 32 768 бит (я не затаил дыхание, увидев одну из них в моей жизни), то мы получили бы фактор ветвления с b = 8, и мы могли бы фактически начать видеть что-то, что бьет обычный BST.
Q4: Почему так много обсуждений дерева слияния сосредоточено на эскизах?
Как уже упоминалось выше, «секретный соус» дерева слияния - это способность увеличивать каждый узел в B-дерево с некоторой вспомогательной информацией, которая позволяет эффективно (за время O (1)) определить, в какое поддерево B-дерева сходиться.Если у вас есть возможность заставить этот шаг работать, оставшаяся часть структуры данных в основном представляет собой обычное B-дерево.Следовательно, имеет смысл сосредоточиться (исключительно?) На том, как работает этот шаг.
Это также, безусловно, самый сложный шаг в процессе.Для того, чтобы этот шаг работал, требуется разработка нескольких весьма нетривиальных подпрограмм, которые в совокупности дают общее поведение.
Первый метод, который нам понадобится, - это параллельный ранг операция.Давайте вернемся к ключевому вопросу о нашем поиске B-дерева: как определить, в какое поддерево спуститься?Давайте вернемся к нашему узлу B-дерева, как показано здесь:
+-----+-----+-----+-----+
| 103 | 161 | 166 | 261 |
+-----+-----+-----+-----+
/ | | | \
/ | | | \
T0 T1 T2 T3 T4
Это тот же чертеж, что и раньше, но вместо обозначения поддеревьев A, B, C, D и E, I 'мы пометили их T0, T1, T2, T3 и T4.
Давайте представим, что я хочу найти 162. Это должно поместить меня в поддерево T2.Один из способов увидеть это состоит в том, что 162 больше 161 и меньше 166. Но есть и другая перспектива, которую мы можем здесь использовать: мы хотим искать T2, потому что 162 больше, чем 103 и 161, два ключа, которые предшествуют ему.Интересно - нам нужен индекс дерева 2, и мы больше двух ключей в узле.Хммм.
Теперь, ищите 196. Это помещает нас в дерево T3, и получается, что 196 больше 103, 161 и 166, всего три ключа.Интересно.А как насчет 17?Это будет в дереве T0, а 17 больше нуля ключей.
Это намекает на ключевую стратегию, которую мы будем использовать, чтобы заставить работать дерево слияния:
Чтобы определить, в какое поддерево спуститься, нам нужно посчитать, на сколько ключей больше наш ключ поиска.(Это число называется рангом ключа поиска.)
Ключевое понимание дерева слияний заключается в том, как это сделать за время O (1).
Прежде чем приступить к созданию эскизов, давайте создадим ключевой примитив, который понадобится нам позже.Идея заключается в следующем: предположим, что у вас есть набор маленьких целых чисел, где здесь «маленький» означает «такой маленький, что многие из них могут быть упакованы в одно машинное слово».Используя некоторые очень умные методы, если вы можете упаковать несколько маленьких целых чисел в машинное слово, вы можете решить следующую проблему за время O (1):
Параллельный ранг : учитывая ключ k, который является маленьким целым числом, и фиксированный набор маленьких целых чисел x 1 , ..., x b , определите, сколько изx i меньше или равно k.
Например, у нас может быть набор из 6-битных чисел, например, 31, 41, 59,26 и 53, и мы могли бы затем выполнить запросы типа «сколько из этих чисел меньше или равно 37?»
Чтобы дать краткое представление о том, как работает этот метод, идея состоит в том, чтобы собрать всеиз маленьких целых чисел в одно машинное слово, разделенных нулевыми битами.Это число может выглядеть так:
00111110101001011101100110100110101
0 31 0 41 0 59 0 26 0 53
Теперь предположим, что мы хотим увидеть, сколько из этих чисел меньше или равно 37. Для этого мы начнем с формирования целого числа, состоящего из несколькихреплицированные копии с номером 37, каждой из которых предшествует 1 бит.Это будет выглядеть так:
11001011100101110010111001011100101
1 37 1 37 1 37 1 37 1 37
Что-то очень крутое случится, если мы вычтем первое число из этого второго числа.Посмотрите это:
11001011100101110010111001011100101 1 37 1 37 1 37 1 37 1 37
- 00111110101001011101100110100110101 - 0 31 0 41 0 59 0 26 0 53
----------------------------------- ---------------------------------
10001100111100010101010010110110000 1 6 0 -4 0 -12 1 9 0 -16
^ ^ ^ ^ ^ ^ ^ ^ ^ ^
Биты, которые я выделил здесь, - это дополнительные биты, которые мы добавили в начале каждого номера. Обратите внимание, что
- , если верхний номер равенбольше или равно нижнему числу, тогда бит перед результатом вычитания будет 1, а
- если верхнее число меньше нижнего, то бит перед результатом вычитания будет равен 0.
Чтобы понять, почему это так, если верхнее число больше или равно нижнему, то при выполнении вычитания нам никогда не нужно будет «брать» этот дополнительный 1 бит, который мы ставим перед старшее число, так что бит останется равным 1. В противном случае верхнее число будет меньше, поэтому, чтобы вычитание сработало, мы должны позаимствовать этот бит, помечая его как ноль. Другими словами, эту единственную операцию вычитания можно рассматривать как параллельное сравнение между исходным ключом и каждым из небольших чисел. Мы делаем одно вычитание, но, по логике, это пять сравнений!
Если мы сможем подсчитать, сколько из отмеченных битов равны 1, у нас есть ответ, который мы хотим. Оказывается, это требует некоторой дополнительной креативности для работы во времени O (1), но это действительно возможно.
Эта параллельная ранговая операция показывает, что если у нас много действительно маленьких ключей - таких маленьких, что мы можем упаковать их в машинное слово - мы действительно можем пойти и вычислить ранг нашего ключа поиска за время O (1), который сказал бы нам, в какое поддерево нам нужно спуститься. Однако есть одна загвоздка - эта стратегия предполагает, что наши ключи действительно малы, но в целом у нас нет оснований предполагать это. Если мы храним полные 32-битные или 64-битные машинные слова в качестве ключей, мы не можем упаковать их много в одно машинное слово. Мы можем вписать ровно один ключ в машинное слово!
Чтобы решить эту проблему, деревья слияния используют другое понимание. Давайте представим, что мы выбираем фактор ветвления нашего B-дерева очень маленьким по сравнению с количеством битов в машинном слове (скажем, b = w 1/5 ). Если у вас есть небольшое количество машинных слов, вам нужно понять, что только несколько битов в этих машинных словах действительно имеют значение для определения порядка . Например, предположим, что у меня есть следующие 32-разрядные числа:
A: 00110101000101000101000100000101
B: 11001000010000001000000000000000
C: 11011100101110111100010011010101
D: 11110100100001000000001000000000
Теперь представьте, что я хотел отсортировать эти числа. Для этого мне действительно нужно взглянуть на некоторые из них. Например, некоторые из чисел отличаются по своему первому биту (верхнее число A там имеет 0, а остальные имеют 1). Поэтому я запишу, что мне нужно посмотреть на первый бит числа. Второй бит этих чисел на самом деле не помогает сортировать вещи - все, что отличается во втором бите, уже отличается в первом бите (понимаете почему?). Третий бит числа также помогает нам ранжировать их, потому что числа B, C и D, имеющие один и тот же первый бит, расходятся на третьем бите в группы (B, C) и D. Мне также необходимо посмотрите на четвертый бит, который разделяет (B, C) на B и C.
Другими словами, чтобы сравнить эти числа друг с другом, нам нужно было только сохранить эти отмеченные биты. Если мы обработаем эти биты по порядку, нам никогда не придется смотреть на другие:
1212 * *
Это шаг набросков , который вы имели в виду в своем вопросе, и он используется для того, чтобы взять маленькое число больших чисел и превратить их в маленький номер маленький номер. Как только у нас будет небольшое количество небольших чисел, мы можем использовать наш шаг параллельного ранга с более ранних этапов для выполнения операций ранга во времени O (1), что нам и нужно было сделать.
Конечно, есть 1226 * много шагов, которые я здесь пропускаю. Как вы определяете, какие биты являются «интересными» битами, на которые мы должны смотреть? Как вы извлекаете эти биты из чисел? Если вам дается число, которого нет в группе, как вы выясните, как оно сравнивается с числами в группе, учитывая, что оно может отличаться в других позициях бит? На эти нетривиальные вопросы нужно ответить, и именно они и создают большую часть сложности дерева слияния.
Q5: Существует ли визуализация дерева слияния, чтобы помочь понять, как работает структура?
Да и нет. Я скажу «да», потому что есть ресурсы, которые показывают, как работают различные шаги. Однако я скажу «нет», потому что я не верю, что есть какая-то одна картинка, на которую вы можете взглянуть, которая заставит всю структуру данных внезапно сфокусироваться.
Я преподаю курс по сложным структурам данных и провел две 80-минутные лекции по построению дерева слияния с использованием методов параллелизма на уровне слов. Обсуждение здесь основано на тех лекциях, которые углубляются в каждый шаг и включают в себя визуализации различных подэтапов (как вычислить ранг в постоянное время, как работает этап создания эскиза и т. Д.), И каждый из этих шагов в отдельности может дать вам лучшее представление о том, как работает вся структура. Эти материалы связаны здесь:
Часть первая обсуждается параллелизм на уровне слов, вычисляются ранги во времени O (1), строится вариант работающего дерева слияния для очень маленьких целых чисел и вычисления старших значащих бит во времени O (1).
Часть вторая исследует полную версию дерева слияния, представляя основы, лежащие в основе этапа создания эскиза (который я называю «Патрициевые коды») на основании подключения к Патрисии).
Подвести итог
В итоге:
Fusion tree - это модификация B-дерева. Базовая структура соответствует структуре обычного B-дерева, за исключением того, что каждый узел имеет некоторую вспомогательную информацию для ускорения поиска.
Деревья слияния на данный момент представляют чисто теоретический интерес. Коэффициенты скрытой константы слишком высоки, а коэффициент ветвления слишком низок, чтобы осмысленно конкурировать с бинарными деревьями поиска.
Деревья слияния используют параллелизм на уровне слов для ускорения поиска, обычно путем объединения нескольких чисел в одно машинное слово и использования отдельных операций для имитации параллельной обработки.
Шаг создания эскиза используется для уменьшения количества бит во входных числах до точки, где возможна параллельная обработка с машинным словом.
Существуют слайды с лекциями, подробно описывающие это.
Надеюсь, это поможет!