Pull to refresh

Comments 30

Да, хабр точно торт :) Спасибо, отличная статья)
Обидно только, что такие крутые статьи читает 1/100 хабра. Зато вот напиши очередную статью «как правильно ложиться спать», и все, +300 голосов, 600 комментов.
Не совсем понятно, чем это лучше, например Nested set? Порядок О — аналогичный, алгоритмы поиска — примерно такие-же, но алгоритмы создания, слияния, удаления и переноса — проще.
Можете сделать сравнительный анализ?
Поясните, плиз. Так понял, задача — ускорить операции поиска, вставки и удаления. Есть какие-то еще?
Еще огромнейшее количество применений, просто в первую часть они не влезли :)
Хотя бы тем что nested set не ускорит поиск по ключу как это. Nested set больше нужен для построения иерархических каталогов в базе данных чтобы можно было быстро выбрать нужную ветку а не для поиска например цены.
Было бы интересно видеть сравнение перформанса с реализацией RBT без рекурсии.
Я видел одно полноценное сравнение (стр. 69-77). В нем дерамида выиграла по производительности (на рандомных тестах величины 10000/50000/100000) у RBT, Radix tree, списка с пропусками и AA-дерева.

К сожалению, там не приводятся исходники, или я просто не заметил ссылки. И реализация дерамиды в том тестировании отлична от приведенной здесь, они использовали более быстрые операции, с поворотами. Впрочем, учитывая, что там испытывались одни из быстрейших реализаций всех сравниваемых структур, результат вполне показателен.
По моему опыту, на больших объёмах данных у декартова дерева скорость процентов на 20% ниже, чем у RBT, а ещё быстрее процентов на 5 будет работать 2-3 дерево, за счёт того, что в этих случаях производительность зависит от объёма используемой памяти на узел, а в 2-3 дереве можно в листьях не хранить указатели на детей (правда, кода получается жутко много). Естественно, рассматриваются нерекурсивные реализации. Отметим, правда, что при хранении дополнительных данных вроде количества/суммы по поддеревьям нерекурсивная реализация требует моделирования стека или хранения предка (ну второе вообще по памяти жесть, а вот первое реально используется).

Но мне пока так никто и не объяснил, как нормально без лишних данных в RBT делать merge, а без этого невозможно их адаптировать для использования по неявному ключу (а именно для этого и придумывалось декартово дерево в российском ACM-программировании).

А ещё нерекурсивная реализация декартова дерева выглядит красиво :) К сожалению, при попытке запостить код все отступы куда-то исчезают, несмотря на мои попытки использовать теги code и pre… (может, я чего-то не понимаю???)
В крайнем случае всегда можно выложить код на какой-нибудь pastie.org, и оставить здесь ссылку. Интересно увидеть ведь.
Оставлю здесь код из ссылки 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;
}
О, есть шанс ещё раз попробовать понять эту структуру данных!
Статья на главной — иллюстраций нет :(
С ними было бы попонятнее…
Недопонял. В статье с десяток иллюстраций, все на habreffect`e.
Видимо я неудачно зашел — ни одной не было, перезагрузка не помогала.
Сейчас вижу, буду дочитывать материал…
Кстати, спасибо за топик — тема интересная.
Про терминологию: встречал название «курево» (куча+дерево), удачно созвучное с «treap».
жарево, парево, серево, варево, курево :)
извините, неудержался:)
Кстати, еще из забавных названий.
Пирамида + Дерево => ПиВо.
Круто. Кажется, где-то еще нужно написать, что эта структура данных meldable, но не mergeable.
Введение в курево отличное.
Ждем второго поста. Дерамида по неявному ключу + множественные операции + инверсия на отрезке — это сила данной структуры.
UFO landed and left these words here
По-моему, было бы лучше в примерах на C# писать сразу Treap<T> без специализации на int.
Теоретически да, я говорил об этом в тексте. Но тогда, во-первых, T where T: IComparable<T>. Во-вторых, потеряется возможность сравнивать ключи операторами — теряется наглядность кода. Эта статья более учебная, чем обобщенная, поэтому я предпочитаю наглядность.
в статье битые ссылки, после реорганизации сатйа. Если можно — поправьте.
Only those users with full accounts are able to leave comments. Log in, please.