Ответ 1
Я прочитал (просто быстрый проход) оригинальную бумагу и кажется интересным. Он также отвечает на большинство ваших вопросов на первой странице.
Вы можете скачать статью из здесь
НТН!
Я наткнулся на страницу Википедии для них:
И я прочитал pdf файлы с примечаниями к классу, связанные внизу, но они касаются самой структуры данных и подробно рассказывают о функции sketch(x)
. Я думаю, что часть моей путаницы заключается в том, что статьи пытаются быть очень общими, и я хотел бы представить конкретный пример.
Подходит ли эта структура данных для хранения данных на основе произвольных 32- или 64-битных целочисленных ключей? Чем он отличается от B-дерева? Есть один раздел, который говорит, что это в основном B-дерево с коэффициентом ветвления B = (lg n)^(1/5)
. Для полностью заполненного дерева с 32-битными ключами B будет 2. Это просто станет бинарным деревом? Предназначена ли эта структура данных для использования гораздо более длинных битовых строк в качестве ключей?
Мой Google не нашел ничего ужасно полезного, но я бы приветствовал любые хорошие ссылки на эту тему. Это на самом деле просто мимолетное любопытство, поэтому я еще не готов платить за PDF файлы на portal.acm.org
.
Я прочитал (просто быстрый проход) оригинальную бумагу и кажется интересным. Он также отвечает на большинство ваших вопросов на первой странице.
Вы можете скачать статью из здесь
НТН!
Я прочитал бумагу слияния. Идеи довольно умны, а в терминах нотации O он может сделать дело для победы.
Мне не ясно, что это победа на практике. Постоянный фактор имеет большое значение, и разработчики чипов очень усердно работают с дешевыми локальными ссылками.
Он должен иметь B в своих искусственных B-деревьях, довольно маленьких для реальных машин (B = 5 для 32 бит, может быть, 10 для 64 бит). То, что многие указатели в значительной степени вписываются в строку кэша. После первого касания линии кеширования (чего он не может избежать) в несколько сотен циклов вы можете в значительной степени выполнять линейный поиск по ключам в течение нескольких циклов на ключ, что означает, что традиционная реализация тщательно кодированного B-дерева кажется им должны опережать сварочные деревья. (Я создал такой код B-tree для поддержки нашей системы преобразования программ).
Он утверждает список приложений, но сравнительных чисел нет.
У кого-нибудь есть доказательства? (Реализации и сравнения?)
Идея дерева слияния на самом деле довольно проста. Предположим, у вас есть w-бит (скажем, 64-битные) ключи, идея состоит в том, чтобы сжимать (то есть эскиз) каждые последовательные 64-х ключи в 64-элементный массив. Функция эскиза обеспечивает постоянное отображение времени между исходными ключами и индексом массива для данной группы. Затем поиск ключа становится поиском группы, содержащей ключ, который является O (log (n/64)). Как вы можете видеть, основной проблемой является функция эскиза.
Вы задали здесь несколько замечательных вопросов:
Я хотел бы ответить на каждый из этих вопросов по очереди.
Ваш первый вопрос был о том, какие деревья слияния предназначены для хранения. Структура данных Fusion Tree специально разработана для хранения целых чисел, которые вписываются в одно машинное слово. В результате на 32-разрядной машине вы будете использовать дерево слияния для хранения целых чисел до 32 бит, а на 64-разрядной машине вы будете использовать дерево слияния для хранения целых чисел до 64 бит.
Деревья слияния не предназначены для обработки произвольно длинных цепочек битов. Конструкция деревьев слияния, к которой мы вскоре перейдем, основана на методике, называемой параллелизмом на уровне слов, в которой отдельные операции над машинными словами (умножения, сдвиги, вычитания и т.д.) Выполняются для неявного действия. на большой коллекции чисел параллельно. Чтобы эти методы работали правильно, сохраняемые числа должны соответствовать отдельным машинным словам. (Технически возможно адаптировать здесь методы для работы с числами, которые вписываются в постоянное количество машинных слов.)
Но прежде чем мы пойдем дальше, я должен добавить одну оговорку: деревья слияния представляют только теоретический интерес. Хотя деревья слияния по номинальной стоимости, по-видимому, имеют отличные гарантии времени выполнения (O (log w n) времени на операцию, где w - размер машинного слова), фактические детали реализации таковы, что скрытые постоянные факторы огромны и являются основными барьер для практического принятия. Оригинальная статья о деревьях слияния была в основном направлена на доказательство того, что можно было преодолеть нижнюю границу Ω (log n) для операций BST, используя параллелизм на уровне слов и без учета затрат времени выполнения настенных часов. Таким образом, в этом смысле, если ваша цель в понимании деревьев слияния заключается в том, чтобы использовать их на практике, я бы рекомендовал остановиться здесь и искать другую структуру данных. С другой стороны, если вам интересно узнать, сколько скрытой мощности доступно в скромных машинных словах, тогда, пожалуйста, продолжайте читать!
На высоком уровне вы можете думать о дереве слияния как о обычном 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. Есть два "естественных" способа, которыми мы могли бы выполнить этот поиск:
Поскольку каждый узел в B-дереве имеет коэффициент ветвления b или больше, высота B-дерева порядка b равна O (log b n). Поэтому, если мы используем первую стратегию (линейный поиск), чтобы найти, в какое дерево спускаться, наихудшая работа, необходимая для поиска, - это O (b log b n), поскольку мы выполняем O (b) работу на уровень по O (журнал б н) уровней. Интересный факт: количество b log b n минимизируется, когда b = e, и становится все хуже, когда мы увеличиваем b за этот предел.
С другой стороны, если мы используем бинарный поиск, чтобы найти дерево, в которое нужно спуститься, время выполнения заканчивается O (log b · log b n). Используя изменение базовой формулы для логарифмов, обратите внимание, что
log b · log b n = log b · (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 слоев) в дереве!
Вопрос сейчас в том, как это сделать.
По техническим причинам, которые станут понятнее позже, дерево слияния работает, выбирая в качестве параметра ветвления для 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 ≈ 2,29,
который мы, вероятно, округлили бы до 2. Значит ли это, что дерево слияния - это просто двоичное дерево?
Ответ "не совсем". В B-дереве каждый узел хранит от b - 1 до 2b - 1 всего ключей. С b = 2 это означает, что каждый узел хранит всего от 1 до 3 ключей. (Другими словами, наше B-дерево было бы 2-3-4, если вы знакомы с этой прекрасной структурой данных). Это означает, что мы будем разветвляться немного больше, чем обычное дерево двоичного поиска, но не намного больше.
Возвращаясь к нашей более ранней точке, деревья слияния представляют в первую очередь теоретический интерес. Тот факт, что мы выбрали b = 2 на реальной машине и едва ли справились лучше обычного бинарного дерева поиска, является одной из многих причин, почему это так.
С другой стороны, если бы мы работали, скажем, на машине, размер слова которой составлял 32 768 бит (я не затаил дыхание, увидев одну из них в моей жизни), то мы получили бы коэффициент ветвления b = 8, и мы могли бы фактически начать видеть что-то, что бьет обычный BST.
Как упомянуто выше, "секретный соус" дерева слияния - это способность дополнять каждый узел в B-дереве некоторой вспомогательной информацией, которая позволяет эффективно (за время O (1)) определить, какое поддерево B-дерева дерево, чтобы спуститься в. Если у вас есть возможность заставить этот шаг работать, оставшаяся часть структуры данных в основном представляет собой обычное B-дерево. Следовательно, имеет смысл сосредоточиться (исключительно?) На том, как работает этот шаг.
Это также, безусловно, самый сложный шаг в этом процессе. Чтобы этот шаг работал, необходимо разработать несколько весьма нетривиальных подпрограмм, которые в совокупности дают общее поведение.
Первый метод, который нам понадобится, - это операция с параллельным рангом. Давайте вернемся к ключевому вопросу о нашем поиске B-дерева: как определить, в какое поддерево спуститься? Давайте вернемся к нашему узлу B-дерева, как показано здесь:
+-----+-----+-----+-----+
| 103 | 161 | 166 | 261 |
+-----+-----+-----+-----+
/ | | | \
/ | | | \
T0 T1 T2 T3 T4
Это тот же рисунок, что и раньше, но вместо обозначения поддеревьев A, B, C, D и E я пометил их 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 бит, который мы ставим перед верхним числом, так что этот бит останется равным 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.
Другими словами, чтобы сравнить эти числа друг с другом, нам нужно только сохранить эти отмеченные биты. Если мы обработаем эти биты по порядку, нам никогда не нужно будет смотреть на другие:
A: 00110101000101000101000100000101
B: 11001000010000001000000000000000
C: 11011100101110111100010011010101
D: 11110100100001000000001000000000
^ ^^
Это шаг зарисовки, о котором вы говорили в своем вопросе, и он занимал небольшое количество больших чисел и превращал их в небольшое количество маленьких чисел. Как только у нас будет небольшое количество небольших чисел, мы можем использовать наш шаг параллельного ранжирования с более ранних этапов для выполнения операций ранжирования за время O (1), что нам и нужно было сделать.
Конечно, здесь я пропущу много шагов. Как вы определяете, какие биты являются "интересными" битами, на которые нам нужно обратить внимание? Как вы извлекаете эти биты из чисел? Если вам дается число, которого нет в группе, как вы выясните, как оно сравнивается с числами в группе, учитывая, что оно может отличаться в других позициях бит? Это не тривиальные вопросы, на которые нужно отвечать, и именно они порождают большую часть сложности дерева слияния.
И да и нет. Я скажу "да", потому что есть ресурсы, которые показывают, как работают различные шаги. Тем не менее, я скажу "нет", потому что я не верю, что какая-то одна картинка, на которую вы можете посмотреть, заставит всю структуру данных внезапно сфокусироваться.
Я преподаю курс по сложным структурам данных и провел две 80-минутные лекции по построению дерева слияния с использованием методов параллелизма на уровне слов. Обсуждение здесь основано на тех лекциях, которые углубляются в каждый шаг и включают в себя визуализации различных подэтапов (как вычислить ранг в постоянное время, как работает этап создания эскиза и т.д.), И каждый из этих шагов в отдельности может дать вам лучшее представление о том, как работает вся структура. Эти материалы связаны здесь:
В первой части обсуждается параллелизм на уровне слов, вычисление рангов во времени O (1), построение варианта дерева слияния, которое работает для очень маленьких целых чисел, и вычисление старших значащих бит во времени O (1).
Вторая часть исследует полную версию дерева слияния, представляя основы, лежащие в основе этапа создания эскиза (который я называю "коды Патрисии", основанные на связи с тривием Патриции).
В итоге:
Fusion tree - это модификация B-дерева. Базовая структура соответствует структуре обычного B-дерева, за исключением того, что каждый узел имеет некоторую вспомогательную информацию для ускорения поиска.
Деревья слияния на данный момент представляют чисто теоретический интерес. Скрытые постоянные коэффициенты слишком высоки, а коэффициент ветвления слишком низок, чтобы осмысленно конкурировать с бинарными деревьями поиска.
Деревья слияний используют параллелизм на уровне слов для ускорения поиска, обычно путем объединения нескольких чисел в одно машинное слово и использования отдельных операций для симуляции параллельной обработки.
Шаг создания эскиза используется для уменьшения количества бит во входных числах до точки, где возможна параллельная обработка с машинным словом.
Есть слайды с лекциями, подробно описывающие это.
Надеюсь это поможет!