Comments 14
ха, а я прочитал (я про тег, а не про статью :) ).
Прикольная штука. Кто их придумал?
В сегодняшнем полном варианте — Зайдель и Арагон, в 1996 году (link). Идеи о том, как «квази-балансировать» дерево поиска приоритетами существовали и раньше, применения отложенных вычислений на отрезках — еще раньше, с успехом работали в одноименном «дереве отрезков».
После 1996 года главная модификация, которая произошла — переделка под неявный ключ. Что характерно, вроде бы сделана в России ACM-олимпийцами, потому что в западной литературе упоминаний об этой махинации — ноль =)
После 1996 года главная модификация, которая произошла — переделка под неявный ключ. Что характерно, вроде бы сделана в России ACM-олимпийцами, потому что в западной литературе упоминаний об этой махинации — ноль =)
благодарю автора, чудесная статья. обожаю изучать новые алгоритмы и структуры данных, буду ждать продолжения.
Понятно.
Напомнило как я однажды «изобрел» Б-деревья. Как-то я размышлял над таблицами и списками и решил, что их нужно творчески объединить, чтобы избавиться от недостатков (долгая вставка в таблицу и долгий поиск в списке). Полученный «список таблиц», разумеется, постепенно превратился в дерево, состоящее из «списков таблиц». Долго я сражался с реализацией и получил-таки работающий вариант. Радости моей не было предела и после оптимизаций я решился помериться производительностью с деревьями из stl библиотеки, на которых основан map.
Увы, в среднем моя структура отставала на 50-70%. Хотя временами, для отдельных случаев — опережала. Тогда-то я и решил, наконец, поизучать вопрос поподробнее и узнал про красно-черные и про Б-деревья… :-)
Напомнило как я однажды «изобрел» Б-деревья. Как-то я размышлял над таблицами и списками и решил, что их нужно творчески объединить, чтобы избавиться от недостатков (долгая вставка в таблицу и долгий поиск в списке). Полученный «список таблиц», разумеется, постепенно превратился в дерево, состоящее из «списков таблиц». Долго я сражался с реализацией и получил-таки работающий вариант. Радости моей не было предела и после оптимизаций я решился помериться производительностью с деревьями из stl библиотеки, на которых основан map.
Увы, в среднем моя структура отставала на 50-70%. Хотя временами, для отдельных случаев — опережала. Тогда-то я и решил, наконец, поизучать вопрос поподробнее и узнал про красно-черные и про Б-деревья… :-)
UFO just landed and posted this here
Вообще-то, для классических сбалансированных деревьев, например, AVL, тоже не представляет никакой трудности держать в узле вычисленные параметры поддерева — тот же размер левого потомка или max(cost). И преобразование этих величин при элементарных преобразованиях (для AVL это вставка/удаление листьев и поворот) ничуть не сложнее.
Небольшим недостатком декартового дерева есть то, что игреки нигде не используются практически, кроме балансировки дерева.
На самом деле, можно вместо Y брать реальную информацию, тоесть не случайно сгенерированные числа. Если после этого умножить все Y на некоторое простое число P и взять по модулю 2^64 (что очень удобно и быстро), то можно доказать, что Y будут распределены случайным образом. Для того, что бы при необходимости узнать Y, нужно будет просто домножить на обратный элемент к P по модулю 2^64.
Таким образом, память у декартового дерева не будет тратиться попусту и в ней можно хранить некоторую информацию, помимо ключей.
На самом деле, можно вместо Y брать реальную информацию, тоесть не случайно сгенерированные числа. Если после этого умножить все Y на некоторое простое число P и взять по модулю 2^64 (что очень удобно и быстро), то можно доказать, что Y будут распределены случайным образом. Для того, что бы при необходимости узнать Y, нужно будет просто домножить на обратный элемент к P по модулю 2^64.
Таким образом, память у декартового дерева не будет тратиться попусту и в ней можно хранить некоторую информацию, помимо ключей.
Да, этот метод действительно может быть практически полезен.
Однако у него есть одна серьезная уязвимость, а именно, если кто-то сможет каким-то образом выяснить, какое число вы используете в качестве простого, то он сможет ваше дерево сделать очень некрасивым (с серьезными последствиями для работы вашей программы).
Мне рассказывали, что недавно к нам приезжал Тарьян, и рассказывал грустную историю про людей, которые использовали подобные методы в красно-черном дереве, бездоказательно, и у них залажался какой-то серьезный проект, и их за это засудили и отсудили кучу денег…
Поэтому реально гораздо более сильны следующие методы:
1) использование счётчиков для балансировки
— если у вас в дереве всё равно хранятся счётчики, то можно, используя их, предсказать вероятность, с которой новый «y» будет больше текущего. Этим методом любила пользоваться ACM-команда SPb SU Drink Less, пока на очередном чемпионате СПбГУ им не попалась задачка, на которой они не смогли пробить TL с помощью такой балансировки. Действительно, если аккуратно написать формулу, то видно, что там нужно так или иначе взятие по модулю, которое не самая быстрая операция. Конечно, есть способы с этим бороться, но домножение на обратное было быстрее.
2) апгрейд исходного метода, придуманный мной совсем недавно, выглядит так:
пусть у нас в дереве нет никакой дополнительной информации, кроме x
тогда, казалось бы, на простое (по модулю) придётся домножать x
но легко доказать, что какая бы функция f(x) ни была, найдётся такая последовательность x длины не менее sqrt (M), где M — модуль, по которому происходит домножение на простое, что пары (x, f(x)) будут совместно монотонны — таким образом, используя x в качестве прототипа для y, мы никак не сможем добиться хорошей формы дерева
однако есть ещё одно непредусмотренное место, в которое легко засунуть рандом — это, собственно, указатель на структурку, в которой и хранится узел дерева
тут открывается простор для фантазии, как выделять структурки, чтобы указатель на них был случаен :) так или иначе с этой задачей можно справиться, и никакой y не нужен
ну или можно по первому методу использовать p в качестве дополнительных данных, если не боитесь злобных хакеров ;) или линейную комбинацию из x и p со случайными коэффициентами, так вернее :)
Однако у него есть одна серьезная уязвимость, а именно, если кто-то сможет каким-то образом выяснить, какое число вы используете в качестве простого, то он сможет ваше дерево сделать очень некрасивым (с серьезными последствиями для работы вашей программы).
Мне рассказывали, что недавно к нам приезжал Тарьян, и рассказывал грустную историю про людей, которые использовали подобные методы в красно-черном дереве, бездоказательно, и у них залажался какой-то серьезный проект, и их за это засудили и отсудили кучу денег…
Поэтому реально гораздо более сильны следующие методы:
1) использование счётчиков для балансировки
— если у вас в дереве всё равно хранятся счётчики, то можно, используя их, предсказать вероятность, с которой новый «y» будет больше текущего. Этим методом любила пользоваться ACM-команда SPb SU Drink Less, пока на очередном чемпионате СПбГУ им не попалась задачка, на которой они не смогли пробить TL с помощью такой балансировки. Действительно, если аккуратно написать формулу, то видно, что там нужно так или иначе взятие по модулю, которое не самая быстрая операция. Конечно, есть способы с этим бороться, но домножение на обратное было быстрее.
2) апгрейд исходного метода, придуманный мной совсем недавно, выглядит так:
пусть у нас в дереве нет никакой дополнительной информации, кроме x
тогда, казалось бы, на простое (по модулю) придётся домножать x
но легко доказать, что какая бы функция f(x) ни была, найдётся такая последовательность x длины не менее sqrt (M), где M — модуль, по которому происходит домножение на простое, что пары (x, f(x)) будут совместно монотонны — таким образом, используя x в качестве прототипа для y, мы никак не сможем добиться хорошей формы дерева
однако есть ещё одно непредусмотренное место, в которое легко засунуть рандом — это, собственно, указатель на структурку, в которой и хранится узел дерева
тут открывается простор для фантазии, как выделять структурки, чтобы указатель на них был случаен :) так или иначе с этой задачей можно справиться, и никакой y не нужен
ну или можно по первому методу использовать p в качестве дополнительных данных, если не боитесь злобных хакеров ;) или линейную комбинацию из x и p со случайными коэффициентами, так вернее :)
Вы не пробовали писать книгу? У вас хороший стиль, как для технических текстов — не сухо, и в то же время не художественный рассказ. Картинки очень понравились. Даже если что не понятно в тексте, то после них вопросов не остается :).
Sign up to leave a comment.
Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней