Comments 30
Да, хабр точно торт :) Спасибо, отличная статья)
Не совсем понятно, чем это лучше, например Nested set? Порядок О — аналогичный, алгоритмы поиска — примерно такие-же, но алгоритмы создания, слияния, удаления и переноса — проще.
Можете сделать сравнительный анализ?
Можете сделать сравнительный анализ?
Было бы интересно видеть сравнение перформанса с реализацией RBT без рекурсии.
Я видел одно полноценное сравнение (стр. 69-77). В нем дерамида выиграла по производительности (на рандомных тестах величины 10000/50000/100000) у RBT, Radix tree, списка с пропусками и AA-дерева.
К сожалению, там не приводятся исходники, или я просто не заметил ссылки. И реализация дерамиды в том тестировании отлична от приведенной здесь, они использовали более быстрые операции, с поворотами. Впрочем, учитывая, что там испытывались одни из быстрейших реализаций всех сравниваемых структур, результат вполне показателен.
К сожалению, там не приводятся исходники, или я просто не заметил ссылки. И реализация дерамиды в том тестировании отлична от приведенной здесь, они использовали более быстрые операции, с поворотами. Впрочем, учитывая, что там испытывались одни из быстрейших реализаций всех сравниваемых структур, результат вполне показателен.
По моему опыту, на больших объёмах данных у декартова дерева скорость процентов на 20% ниже, чем у RBT, а ещё быстрее процентов на 5 будет работать 2-3 дерево, за счёт того, что в этих случаях производительность зависит от объёма используемой памяти на узел, а в 2-3 дереве можно в листьях не хранить указатели на детей (правда, кода получается жутко много). Естественно, рассматриваются нерекурсивные реализации. Отметим, правда, что при хранении дополнительных данных вроде количества/суммы по поддеревьям нерекурсивная реализация требует моделирования стека или хранения предка (ну второе вообще по памяти жесть, а вот первое реально используется).
Но мне пока так никто и не объяснил, как нормально без лишних данных в RBT делать merge, а без этого невозможно их адаптировать для использования по неявному ключу (а именно для этого и придумывалось декартово дерево в российском ACM-программировании).
А ещё нерекурсивная реализация декартова дерева выглядит красиво :) К сожалению, при попытке запостить код все отступы куда-то исчезают, несмотря на мои попытки использовать теги code и pre… (может, я чего-то не понимаю???)
Но мне пока так никто и не объяснил, как нормально без лишних данных в RBT делать merge, а без этого невозможно их адаптировать для использования по неявному ключу (а именно для этого и придумывалось декартово дерево в российском ACM-программировании).
А ещё нерекурсивная реализация декартова дерева выглядит красиво :) К сожалению, при попытке запостить код все отступы куда-то исчезают, несмотря на мои попытки использовать теги code и pre… (может, я чего-то не понимаю???)
В крайнем случае всегда можно выложить код на какой-нибудь pastie.org, и оставить здесь ссылку. Интересно увидеть ведь.
Да, точно… что-то мне не пришло это в голову, хотел прямо сюда :)
Вот пример процедуры merge, написанной нерекурсивно.
Вот пример процедуры merge, написанной нерекурсивно.
Оставлю здесь код из ссылки kotehok, на случай если его удалят с acm.spbgu.ru:
static ltree_t *ltree_merge (ltree_t *L, ltree_t *R) {
ltree_t *Root, **U = &Root;
while (L && R) {
if (L->y > R->y) {
*U = L;
U = &L->right;
L = *U;
} else {
*U = R;
U = &R->left;
R = *U;
}
}
*U = L ? L : R;
return Root;
}О, есть шанс ещё раз попробовать понять эту структуру данных!
Статья на главной — иллюстраций нет :(
С ними было бы попонятнее…
С ними было бы попонятнее…
Про терминологию: встречал название «курево» (куча+дерево), удачно созвучное с «treap».
Круто. Кажется, где-то еще нужно написать, что эта структура данных meldable, но не mergeable.
UFO just landed and posted this here
Введение в курево отличное.
Ждем второго поста. Дерамида по неявному ключу + множественные операции + инверсия на отрезке — это сила данной структуры.
Ждем второго поста. Дерамида по неявному ключу + множественные операции + инверсия на отрезке — это сила данной структуры.
UFO just landed and posted this here
По-моему, было бы лучше в примерах на C# писать сразу
Treap<T> без специализации на int.UFO just landed and posted this here
Здесь есть видео по Декартову дереву.
в статье битые ссылки, после реорганизации сатйа. Если можно — поправьте.
Sign up to leave a comment.
Декартово дерево: Часть 1. Описание, операции, применения