Понимание деревьев Fusion?

я наткнулся на Wikipedia page для них:Понимание деревьев Fusion?

И я прочитал класс отмечает PDFs, связанные в нижней части, но он получает ручной волнистый о самой структуре данных и переходит в много деталей о функция sketch(x). Я думаю, что часть моей путаницы заключается в том, что документы стараются быть очень общими, и я хотел бы, чтобы конкретный пример визуализировался.

Является ли эта структура данных подходящей для хранения данных на основе произвольных 32 или 64-битных целых ключей? Чем он отличается от B-дерева? Существует одна секция, в которой говорится, что это в основном B-дерево с коэффициентом ветвления B = (lg n)^(1/5). Для полностью заполненного дерева с 32-битными ключами B будет 2. Будет ли это просто стать двоичным деревом? Является ли эта структура данных более длинными битовыми строками в качестве ключей?

My Googling не принес ничего ужасно полезного, но я бы приветствовал любые хорошие ссылки на эту тему. Это действительно просто мимолетное любопытство, поэтому я еще не желал платить за PDF-файлы в portal.acm.org.

источник

2010-10-07 xscott

Я думаю, что он получает 5 ключей в узле дерева B на 32 бита. –

@ xscott- В качестве альтернативы вы можете посмотреть деревья Ван Эмде Боаса (vEB-деревья). Деревья Fusion выполняются в O (lg n/lg lg n), где, когда деревья vEB работают в O (lg lg n) раз за операцию, с асимптотически быстрее. Более того, vEB-деревья значительно легче понять, чем деревья слияния, по крайней мере, IMHO. – templatetypedef

Я прочитал (просто быстрый проход) оригинальную бумагу и кажется интересным. Он также отвечает на большинство ваших вопросов на первой странице.

Вы можете загрузить бумагу из here

HTH!

источник

2010-11-04 02:11:08

Клянусь соблюдать условия. Спасибо за ссылку! – xscott

Friggin Rapidshare не позволит мне скачать ссылку. Очень расстраивает на самом деле. – xscott

@xscott Просто предложите другой способ совместного использования pdf-файла в частично закрытом envoronment (то есть, не индексированный google), чтобы сохранить «неповторяемое» ограничение авторских прав –

Я прочитал бумагу фьюжн-дерева. Идеи довольно умны, и в терминах нотации O он может сделать дело для победы.

Непонятно, что это на практике. Постоянный фактор имеет большое значение, и разработчикам чипов очень сложно справляться с дешевыми локальными ссылками.

Он должен иметь B в своих искусственных B-деревьях, довольно маленьких для реальных машин (B = 5 для 32 бит, может быть, 10 для 64 бит). То, что многие указатели в значительной степени вписываются в строку кэша. После первого касания линии кеширования (чего он не может избежать) в несколько сотен циклов вы можете в значительной степени выполнять линейный поиск по ключам в течение нескольких циклов на ключ, что означает, что традиционная реализация тщательно кодированного B-дерева кажется им должны опережать сварочные деревья. (Я создал такой код B-tree для поддержки нашей системы преобразования программ).

Он утверждает список приложений, но сравнительных чисел нет.

У кого-нибудь есть веские доказательства? (Реализации и сравнения?)

источник

2010-11-09 18:51:52

Добро пожаловать в мир теории. Рассмотрим: если n равно <= 2^32, то loglog n равно 5. Поэтому, если постоянная O-нотации увеличивается в 5 раз (относительно решения log n), вы ничего не получаете или даже не теряете. Важность этого результата теоретическая: в принципе возможно асимптотически преодолеть барьер log n. Кстати, с тех пор были успехи. Наилучший целочисленный алгоритм сортировки на сегодняшний день O (n loglog n). – Ari

@Ari: Да, знаете о теории и практике: -} Ref to O (n loglog n) бумага? Имеет ли такая же проблема с константами на практике? –

Y. Han, Детерминированная сортировка в O (n loglog n) времени и линейном пространстве. STOC 2002 pp. 602-608. Версия журнала - J. Алгоритмы 50 (1): 96-105 (2004). Я на самом деле не прочитал все это, но учитывая, что он построен на деревьях Fusion и экспоненциальных деревьях, я должен сказать, что константа не позволит ему обыграть обычную сортировку O (n log n) для любого практического n. – Ari

Идея, лежащая в основе дерева слияния, на самом деле довольно проста. Предположим, у вас есть w-бит (скажем, 64-битные) ключи, идея состоит в том, чтобы сжимать (то есть эскиз) каждые последовательные 64-х ключи в 64-элементный массив. Функция эскиза обеспечивает постоянное отображение времени между исходными ключами и индексом массива для данной группы. Затем поиск ключа становится поиском группы, содержащей ключ, который является O (log (n/64)). Как вы можете видеть, главной задачей является функция эскиза.

источник

2016-02-28 16:19:43 jzl106

Понимание деревьев Fusion?

ответ

Смежные вопросы