Comments 26
С практической точки зрения, ворочать структуру при каждом запросе — сомнительная идея.
+1
UFO just landed and posted this here
У каждого инструмента есть своя область применения. Splay-деревья ведут себя хорошо при последовательной обработке большого набора запросов с произвольным распределением. Они экономичны в плане количества информации, которую требуется хранить в узлах. Кроме того, splay-дерево — это сливаемая структура данных.
С другой стороны я согласен, что постоянное изменение структуры не делает их привлекательными для параллельного или чисто-функционального программирования. Чтобы что-то получить, нужно чем-то расплатиться.
С другой стороны я согласен, что постоянное изменение структуры не делает их привлекательными для параллельного или чисто-функционального программирования. Чтобы что-то получить, нужно чем-то расплатиться.
+3
Имеет смысл добавить это в статью. Приведите примеры таких запросов. Мне кажется, это было бы полезнее, чем доказательства теор. результатов — я готов поверить на слово, что вы их не перевираете :)
+6
Добавил ссылку на обзор. Splay-деревья сравнивали с красно-черными и AVL-деревьями на реальных данных. Можете посмотреть таблицы.
Вам анализ не нужен, кому-то интересен, а у кого-то это splay-деревья с анализом — билет в экзамене.
Вам анализ не нужен, кому-то интересен, а у кого-то это splay-деревья с анализом — билет в экзамене.
0
Простите, а у кого такое билетом в экзамене? Просто интересна презентативная выборка заведений.
0
Провокационный вопрос: прибегут, забанят за рекламу =)
Для школьников: ЛКШ
Для студентов: МГУ, КТ ИТМО, Академический ун-т, ШАД, CS Center. Знающие могут дополнить список.
Для школьников: ЛКШ
Для студентов: МГУ, КТ ИТМО, Академический ун-т, ШАД, CS Center. Знающие могут дополнить список.
0
Все в столичных кругах по сути: СПб, Москва. А за ее пределами медведи с косами ходют и на балалайке играют.
0
Я сомневаюсь, что и в перечисленных заведениях конкретно такой вопрос есть на экзамене, больно специфично. Ну, может, где-то в одном месте есть преподаватель-любитель этой структуры данных.
А формально курс «Алгоритмы и структуры данных» с проработкой темы на различной глубине есть почти везде, где его можно ожидать.
А формально курс «Алгоритмы и структуры данных» с проработкой темы на различной глубине есть почти везде, где его можно ожидать.
0
Программы у многих заведений открыты. Некоторые даже видеозаписи выкладывают. Если Вы сомневаетесь, что лекционный материал идет на экзамен… ну, сомневайтесь.
0
В Яндексе, похоже, есть, и в вашем вузе, надо понимать. У нас Бауманке такие вещи идут на экзамен без формального доказательства, только результаты, на отлично — пара вопросов «на понимание».
0
Да, вы правы — алгоритмы и структуры есть практически в каждом техновузе, с разных сторон IT. И хорошо, что вы подметили про глубину — с ней то и возникает основная проблема. В зависимости от вида сбоку грабель — для каждых грабель — разная она. У меня допустим splay именно не было, всего лишь основы основ и фундаментальные кирпичики.
0
Однако в компиляторах, например, GCC, это одна из основных структур данных. Splay-tree там используется при трансформации из AST в трех-адресный код. Пример использования: github.com/mirrors/gcc/blob/master/gcc/omp-low.c
+2
статья в лучших и всего 4 комментария. Верный признак того что написанно умно но никто ничего не понял )
+5
Меня всегда беспокоят алгоритмы, в которых о константах думают свысока. Например, запись в ответ на запрос чтения — это же ужасно. Особенно, если это несколько записей.
На практике пренебрежение константами превращается в ужасающего едва ворочающегося монстра, у которого o(logn), но такие константы, что до времён, когда логарифм становится важным, просто не доходят.
На практике пренебрежение константами превращается в ужасающего едва ворочающегося монстра, у которого o(logn), но такие константы, что до времён, когда логарифм становится важным, просто не доходят.
+1
В теории есть алгоритм Левина, который решает любую задачу за асимптотически оптимальное время. Он перебирает все возможные программы и запускает их параллельно. Но константа там большая, да…
По поводу практической части. Да, действительно, каждый раз делать splay — это печально. Начиная с 2000 люди предложили несколько эвристик, которые позволяют оптимизировать работу splay-дерева. Кое-каких результатов на практике добились. Я видимо напишу заметку-дополнение как ответ этому комментарию и одному выше, что хорошего здесь происходило.
По поводу практической части. Да, действительно, каждый раз делать splay — это печально. Начиная с 2000 люди предложили несколько эвристик, которые позволяют оптимизировать работу splay-дерева. Кое-каких результатов на практике добились. Я видимо напишу заметку-дополнение как ответ этому комментарию и одному выше, что хорошего здесь происходило.
+1
Можно пояснить следующие моменты?
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
Можно. =)
1. Если все известно заранее, то splay дерево не нужно. Мне кажется, что решение должно быть каким-то таким. Берем ключ такой, что сумма частот слева и справа от него меньше половины. Делаем его корнем. Строим поддеревья рекурсивно. С точностью до константы, это дерево точно будет оптимальным.
Хаффман, если что, меняет порядок ключей. Так что его технику использовать напрямую не получится.
2 (и 3). Мне пока не очень понятно, как именно у вас происходит балансировка. Кроме того, статистика — это доп. информация, которую надо хранить. В AVL, красно-черных деревьях достаточно одного-двух битов доп. информации, в splay — нуля.
3. Нет, от тяжелых запросов деревья не защищены. В некоторых случаях делают splay через раз, или подбрасывают монетку, делать ли splay. Но вообще, такое может случиться. Если нужны быстрые ответы на единичные запросы, лучше использовать другие деревья: AVL, B, красно-черные.
1. Если все известно заранее, то splay дерево не нужно. Мне кажется, что решение должно быть каким-то таким. Берем ключ такой, что сумма частот слева и справа от него меньше половины. Делаем его корнем. Строим поддеревья рекурсивно. С точностью до константы, это дерево точно будет оптимальным.
Хаффман, если что, меняет порядок ключей. Так что его технику использовать напрямую не получится.
2 (и 3). Мне пока не очень понятно, как именно у вас происходит балансировка. Кроме того, статистика — это доп. информация, которую надо хранить. В AVL, красно-черных деревьях достаточно одного-двух битов доп. информации, в splay — нуля.
3. Нет, от тяжелых запросов деревья не защищены. В некоторых случаях делают splay через раз, или подбрасывают монетку, делать ли splay. Но вообще, такое может случиться. Если нужны быстрые ответы на единичные запросы, лучше использовать другие деревья: AVL, B, красно-черные.
0
Если правильно распорядиться Хаффманом, то порядок ключей не изменится.
Единственная сложность в том, что при равномерном распределении все ключи должны были бы находиться на одинаковой глубине, а в ДДП в любом случае корневой ключ имеет преимущество.
Как это представить в коде Хаффмана, я ещё не придумал, но истина где-то рядом.
Итак, схема примерно такая.
1) строим код Хаффмана в соответствии с частотами
2) забываем про нолики и единички, нас интересует только длина кодов
3) располагаем ключи по порядку
4) рисуем над ними дерево, так, что каждый ключ оказывается на той глубине, которая соответствует длине его кода
Единственная сложность в том, что при равномерном распределении все ключи должны были бы находиться на одинаковой глубине, а в ДДП в любом случае корневой ключ имеет преимущество.
Как это представить в коде Хаффмана, я ещё не придумал, но истина где-то рядом.
Итак, схема примерно такая.
1) строим код Хаффмана в соответствии с частотами
2) забываем про нолики и единички, нас интересует только длина кодов
3) располагаем ключи по порядку
4) рисуем над ними дерево, так, что каждый ключ оказывается на той глубине, которая соответствует длине его кода
0
Про балансировку. Вот мне как раз и непонятно.
Процедура 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), то выгода от простоты структуры принесёт ощутимые плоды.
Чем меньше возни и чем меньше памяти, тем быстрее, — даже если количество итераций будет больше (в пределах логарифма).
0
Ну и последнее, что хотел сказать: обычное дерево — не cache friendly.
Априорный частотный анализ позволил бы разместить наиболее популярные ключи (первые ярусы дерева) в одной странице.
Апостериорный — MRU или MFU, — ясное дело, потребует перемещения ключей, а это дорогое удовольствие.
Если дерево по-настоящему большое, и мы хотим выжать все оптимизационные соки из него, то лучше, всё-таки, взять априорную статистику и выстроить структуру по-хаффмановски, а в памяти расположить по-ярусно. Да и вообще подумать в сторону Б-деревьев.
Априорный частотный анализ позволил бы разместить наиболее популярные ключи (первые ярусы дерева) в одной странице.
Апостериорный — MRU или MFU, — ясное дело, потребует перемещения ключей, а это дорогое удовольствие.
Если дерево по-настоящему большое, и мы хотим выжать все оптимизационные соки из него, то лучше, всё-таки, взять априорную статистику и выстроить структуру по-хаффмановски, а в памяти расположить по-ярусно. Да и вообще подумать в сторону Б-деревьев.
+1
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 гарантирует, что если поиск неудачен, то последняя просмотренная вершина будет «выдернута» наверх. Это зачем такое?
0
Представьте, что в какой-то момент дерево выстроилось в односвязный список. Ключ с наименьшим значением в самом низу. Пусть все запросы спрашивают условно минус бесконечность. Без splay-а каждый запрос будет обрабатываться за линейное время. А так, мы выдергиваем один из ближайших элементов наверх и в следующий раз нам не придется лезть глубоко.
0
Sign up to leave a comment.
Splay-деревья