Комментарии 26
С практической точки зрения, ворочать структуру при каждом запросе — сомнительная идея.
НЛО прилетело и опубликовало эту надпись здесь
У каждого инструмента есть своя область применения. Splay-деревья ведут себя хорошо при последовательной обработке большого набора запросов с произвольным распределением. Они экономичны в плане количества информации, которую требуется хранить в узлах. Кроме того, splay-дерево — это сливаемая структура данных.
С другой стороны я согласен, что постоянное изменение структуры не делает их привлекательными для параллельного или чисто-функционального программирования. Чтобы что-то получить, нужно чем-то расплатиться.
С другой стороны я согласен, что постоянное изменение структуры не делает их привлекательными для параллельного или чисто-функционального программирования. Чтобы что-то получить, нужно чем-то расплатиться.
Имеет смысл добавить это в статью. Приведите примеры таких запросов. Мне кажется, это было бы полезнее, чем доказательства теор. результатов — я готов поверить на слово, что вы их не перевираете :)
Добавил ссылку на обзор. Splay-деревья сравнивали с красно-черными и AVL-деревьями на реальных данных. Можете посмотреть таблицы.
Вам анализ не нужен, кому-то интересен, а у кого-то это splay-деревья с анализом — билет в экзамене.
Вам анализ не нужен, кому-то интересен, а у кого-то это splay-деревья с анализом — билет в экзамене.
Простите, а у кого такое билетом в экзамене? Просто интересна презентативная выборка заведений.
Провокационный вопрос: прибегут, забанят за рекламу =)
Для школьников: ЛКШ
Для студентов: МГУ, КТ ИТМО, Академический ун-т, ШАД, CS Center. Знающие могут дополнить список.
Для школьников: ЛКШ
Для студентов: МГУ, КТ ИТМО, Академический ун-т, ШАД, CS Center. Знающие могут дополнить список.
Все в столичных кругах по сути: СПб, Москва. А за ее пределами медведи с косами ходют и на балалайке играют.
Я сомневаюсь, что и в перечисленных заведениях конкретно такой вопрос есть на экзамене, больно специфично. Ну, может, где-то в одном месте есть преподаватель-любитель этой структуры данных.
А формально курс «Алгоритмы и структуры данных» с проработкой темы на различной глубине есть почти везде, где его можно ожидать.
А формально курс «Алгоритмы и структуры данных» с проработкой темы на различной глубине есть почти везде, где его можно ожидать.
Программы у многих заведений открыты. Некоторые даже видеозаписи выкладывают. Если Вы сомневаетесь, что лекционный материал идет на экзамен… ну, сомневайтесь.
В Яндексе, похоже, есть, и в вашем вузе, надо понимать. У нас Бауманке такие вещи идут на экзамен без формального доказательства, только результаты, на отлично — пара вопросов «на понимание».
Да, вы правы — алгоритмы и структуры есть практически в каждом техновузе, с разных сторон IT. И хорошо, что вы подметили про глубину — с ней то и возникает основная проблема. В зависимости от вида сбоку грабель — для каждых грабель — разная она. У меня допустим splay именно не было, всего лишь основы основ и фундаментальные кирпичики.
Однако в компиляторах, например, GCC, это одна из основных структур данных. Splay-tree там используется при трансформации из AST в трех-адресный код. Пример использования: github.com/mirrors/gcc/blob/master/gcc/omp-low.c
статья в лучших и всего 4 комментария. Верный признак того что написанно умно но никто ничего не понял )
Меня всегда беспокоят алгоритмы, в которых о константах думают свысока. Например, запись в ответ на запрос чтения — это же ужасно. Особенно, если это несколько записей.
На практике пренебрежение константами превращается в ужасающего едва ворочающегося монстра, у которого o(logn), но такие константы, что до времён, когда логарифм становится важным, просто не доходят.
На практике пренебрежение константами превращается в ужасающего едва ворочающегося монстра, у которого o(logn), но такие константы, что до времён, когда логарифм становится важным, просто не доходят.
В теории есть алгоритм Левина, который решает любую задачу за асимптотически оптимальное время. Он перебирает все возможные программы и запускает их параллельно. Но константа там большая, да…
По поводу практической части. Да, действительно, каждый раз делать splay — это печально. Начиная с 2000 люди предложили несколько эвристик, которые позволяют оптимизировать работу splay-дерева. Кое-каких результатов на практике добились. Я видимо напишу заметку-дополнение как ответ этому комментарию и одному выше, что хорошего здесь происходило.
По поводу практической части. Да, действительно, каждый раз делать splay — это печально. Начиная с 2000 люди предложили несколько эвристик, которые позволяют оптимизировать работу splay-дерева. Кое-каких результатов на практике добились. Я видимо напишу заметку-дополнение как ответ этому комментарию и одному выше, что хорошего здесь происходило.
Можно пояснить следующие моменты?
1. Если у нас есть априорные частоты запросов; в принципе, мы сразу можем построить ДДП с оптимальной глубиной.
2. Апостериорные частоты, т.е. мы набираем статистику по ходу обращений к дереву, заодно и вращаем его, оптимизируя под текущее распределение.
3. Скользящая статистика. Предполагается, что история запросов постепенно теряет актуальность.
В первом случае мы можем отсортировать ключи по возрастанию/убыванию веса (в зависимости от того, как будем строить дерево: добавлять листья или наращивать корень), построим обычное несбалансированное ДДП — его вид будет соответствовать коду Фано.
А если постараться, то и код Хаффмана так же делается.
Splay tree здесь, как видно, не при чём.
В третьем случае, — если придерживаться политики MRU (most recently used), вытаскивать свежезапрошенный ключ на самый верх и затем пусть он тонет, — размер окна истории не поддаётся контролю, а если правильно подобрать запросы, то дерево выродится в линейный список, и в нужный момент мы выстрелим, запросив самый хвостик.
Или splay tree защищено от таких выстрелов, и какую-то минимальную сбалансированность гарантирует?
Во втором случае нам или нужна таблица частот (счётчики обращений) для каждого ключа, или у нас не честное MFU (most frequently used), а всё то же MRU.
Или мы закладываемся на то, что при «хороших» последовательностях запросов политики MFU и MRU должны давать близкие результаты?
1. Если у нас есть априорные частоты запросов; в принципе, мы сразу можем построить ДДП с оптимальной глубиной.
2. Апостериорные частоты, т.е. мы набираем статистику по ходу обращений к дереву, заодно и вращаем его, оптимизируя под текущее распределение.
3. Скользящая статистика. Предполагается, что история запросов постепенно теряет актуальность.
В первом случае мы можем отсортировать ключи по возрастанию/убыванию веса (в зависимости от того, как будем строить дерево: добавлять листья или наращивать корень), построим обычное несбалансированное ДДП — его вид будет соответствовать коду Фано.
А если постараться, то и код Хаффмана так же делается.
Splay tree здесь, как видно, не при чём.
В третьем случае, — если придерживаться политики MRU (most recently used), вытаскивать свежезапрошенный ключ на самый верх и затем пусть он тонет, — размер окна истории не поддаётся контролю, а если правильно подобрать запросы, то дерево выродится в линейный список, и в нужный момент мы выстрелим, запросив самый хвостик.
Или splay tree защищено от таких выстрелов, и какую-то минимальную сбалансированность гарантирует?
Во втором случае нам или нужна таблица частот (счётчики обращений) для каждого ключа, или у нас не честное MFU (most frequently used), а всё то же MRU.
Или мы закладываемся на то, что при «хороших» последовательностях запросов политики MFU и MRU должны давать близкие результаты?
Можно. =)
1. Если все известно заранее, то splay дерево не нужно. Мне кажется, что решение должно быть каким-то таким. Берем ключ такой, что сумма частот слева и справа от него меньше половины. Делаем его корнем. Строим поддеревья рекурсивно. С точностью до константы, это дерево точно будет оптимальным.
Хаффман, если что, меняет порядок ключей. Так что его технику использовать напрямую не получится.
2 (и 3). Мне пока не очень понятно, как именно у вас происходит балансировка. Кроме того, статистика — это доп. информация, которую надо хранить. В AVL, красно-черных деревьях достаточно одного-двух битов доп. информации, в splay — нуля.
3. Нет, от тяжелых запросов деревья не защищены. В некоторых случаях делают splay через раз, или подбрасывают монетку, делать ли splay. Но вообще, такое может случиться. Если нужны быстрые ответы на единичные запросы, лучше использовать другие деревья: AVL, B, красно-черные.
1. Если все известно заранее, то splay дерево не нужно. Мне кажется, что решение должно быть каким-то таким. Берем ключ такой, что сумма частот слева и справа от него меньше половины. Делаем его корнем. Строим поддеревья рекурсивно. С точностью до константы, это дерево точно будет оптимальным.
Хаффман, если что, меняет порядок ключей. Так что его технику использовать напрямую не получится.
2 (и 3). Мне пока не очень понятно, как именно у вас происходит балансировка. Кроме того, статистика — это доп. информация, которую надо хранить. В AVL, красно-черных деревьях достаточно одного-двух битов доп. информации, в splay — нуля.
3. Нет, от тяжелых запросов деревья не защищены. В некоторых случаях делают splay через раз, или подбрасывают монетку, делать ли splay. Но вообще, такое может случиться. Если нужны быстрые ответы на единичные запросы, лучше использовать другие деревья: AVL, B, красно-черные.
Если правильно распорядиться Хаффманом, то порядок ключей не изменится.
Единственная сложность в том, что при равномерном распределении все ключи должны были бы находиться на одинаковой глубине, а в ДДП в любом случае корневой ключ имеет преимущество.
Как это представить в коде Хаффмана, я ещё не придумал, но истина где-то рядом.
Итак, схема примерно такая.
1) строим код Хаффмана в соответствии с частотами
2) забываем про нолики и единички, нас интересует только длина кодов
3) располагаем ключи по порядку
4) рисуем над ними дерево, так, что каждый ключ оказывается на той глубине, которая соответствует длине его кода
Единственная сложность в том, что при равномерном распределении все ключи должны были бы находиться на одинаковой глубине, а в ДДП в любом случае корневой ключ имеет преимущество.
Как это представить в коде Хаффмана, я ещё не придумал, но истина где-то рядом.
Итак, схема примерно такая.
1) строим код Хаффмана в соответствии с частотами
2) забываем про нолики и единички, нас интересует только длина кодов
3) располагаем ключи по порядку
4) рисуем над ними дерево, так, что каждый ключ оказывается на той глубине, которая соответствует длине его кода
Про балансировку. Вот мне как раз и непонятно.
Процедура splay вытягивает найденный узел наверх, то есть, фактически, мы ведём MRU-список.
(А бомба выглядит очень просто, кстати. Опросим все ключи в порядке возрастания, а потом опросим самый первый ключ).
Если бы каждый узел хранил счётчик обращений, то мы могли бы поступать более интеллектуально: поднимать обновлённые узлы над своими (пока ещё) менее вероятными соседями, а не до самого корня.
Тем самым получим адаптивный код Фано. До кода Хаффмана не дотянемся, да и бог с ним.
Чтобы деградировать историю, — проще всего прибегнуть к экспоненциальному скользящему среднему.
Тут вес узла — это не сумма обращений за всю историю, а взвешенная сумма с коэффициентами. убывающими по экспоненциальному закону. Т.е. если касались в моменты T=1, 5, 7, а сейчас момент T=10, то вес будет a^(10-7) + a^(10-5) + a^(10-1) где 0<a<1.
Считать ЭСС очень удобно, потому что в каждый момент времени достаточно обновлять вес по закону W(t) = W(t-1)*a + dW.
Решение в лоб потребовало бы пересчитывать вес всех узлов дерева, но, чтобы избежать это, проще приписать каждому узлу его вес и момент последнего обновления.
Тогда пересчёт веса будет выглядеть так: W(t) = W(t-t0)*a^(t-t0) + dW
где dW = 1, если узел «был найден» и = 0, если это соседний узел, с которым мы решаем — проворачивать дерево или нет.
То есть, в узле, помимо ключа, хранится целое число (номер отсчёта) и вещественное (вес на тот момент).
Но это всё «чистые математические» подходы.
Если принять меры против вырождения splay-деревьев (случайное перетряхивание или отслеживание дисбаланса, как в AVL), то выгода от простоты структуры принесёт ощутимые плоды.
Чем меньше возни и чем меньше памяти, тем быстрее, — даже если количество итераций будет больше (в пределах логарифма).
Процедура splay вытягивает найденный узел наверх, то есть, фактически, мы ведём MRU-список.
(А бомба выглядит очень просто, кстати. Опросим все ключи в порядке возрастания, а потом опросим самый первый ключ).
Если бы каждый узел хранил счётчик обращений, то мы могли бы поступать более интеллектуально: поднимать обновлённые узлы над своими (пока ещё) менее вероятными соседями, а не до самого корня.
Тем самым получим адаптивный код Фано. До кода Хаффмана не дотянемся, да и бог с ним.
Чтобы деградировать историю, — проще всего прибегнуть к экспоненциальному скользящему среднему.
Тут вес узла — это не сумма обращений за всю историю, а взвешенная сумма с коэффициентами. убывающими по экспоненциальному закону. Т.е. если касались в моменты T=1, 5, 7, а сейчас момент T=10, то вес будет a^(10-7) + a^(10-5) + a^(10-1) где 0<a<1.
Считать ЭСС очень удобно, потому что в каждый момент времени достаточно обновлять вес по закону W(t) = W(t-1)*a + dW.
Решение в лоб потребовало бы пересчитывать вес всех узлов дерева, но, чтобы избежать это, проще приписать каждому узлу его вес и момент последнего обновления.
Тогда пересчёт веса будет выглядеть так: W(t) = W(t-t0)*a^(t-t0) + dW
где dW = 1, если узел «был найден» и = 0, если это соседний узел, с которым мы решаем — проворачивать дерево или нет.
То есть, в узле, помимо ключа, хранится целое число (номер отсчёта) и вещественное (вес на тот момент).
Но это всё «чистые математические» подходы.
Если принять меры против вырождения splay-деревьев (случайное перетряхивание или отслеживание дисбаланса, как в AVL), то выгода от простоты структуры принесёт ощутимые плоды.
Чем меньше возни и чем меньше памяти, тем быстрее, — даже если количество итераций будет больше (в пределах логарифма).
Ну и последнее, что хотел сказать: обычное дерево — не cache friendly.
Априорный частотный анализ позволил бы разместить наиболее популярные ключи (первые ярусы дерева) в одной странице.
Апостериорный — MRU или MFU, — ясное дело, потребует перемещения ключей, а это дорогое удовольствие.
Если дерево по-настоящему большое, и мы хотим выжать все оптимизационные соки из него, то лучше, всё-таки, взять априорную статистику и выстроить структуру по-хаффмановски, а в памяти расположить по-ярусно. Да и вообще подумать в сторону Б-деревьев.
Априорный частотный анализ позволил бы разместить наиболее популярные ключи (первые ярусы дерева) в одной странице.
Апостериорный — MRU или MFU, — ясное дело, потребует перемещения ключей, а это дорогое удовольствие.
Если дерево по-настоящему большое, и мы хотим выжать все оптимизационные соки из него, то лучше, всё-таки, взять априорную статистику и выстроить структуру по-хаффмановски, а в памяти расположить по-ярусно. Да и вообще подумать в сторону Б-деревьев.
def find(v, key):
if v == None:
return None
if key == v.key:
return splay(v)
if key < v.key and v.left != None:
return find(v.left, key)
if key > v.key and v.right != None:
return find(v.right, key)
return splay(v)
Завершающий функцию return гарантирует, что если поиск неудачен, то последняя просмотренная вершина будет «выдернута» наверх. Это зачем такое?
if v == None:
return None
if key == v.key:
return splay(v)
if key < v.key and v.left != None:
return find(v.left, key)
if key > v.key and v.right != None:
return find(v.right, key)
return splay(v)
Завершающий функцию return гарантирует, что если поиск неудачен, то последняя просмотренная вершина будет «выдернута» наверх. Это зачем такое?
Представьте, что в какой-то момент дерево выстроилось в односвязный список. Ключ с наименьшим значением в самом низу. Пусть все запросы спрашивают условно минус бесконечность. Без splay-а каждый запрос будет обрабатываться за линейное время. А так, мы выдергиваем один из ближайших элементов наверх и в следующий раз нам не придется лезть глубоко.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Splay-деревья