У нас есть последовательность операций. Время выполнение каждой ведет себя как-то непонятно: где-то быстро, где-то медленно. Хочется посчитать суммарное время работы.
Амортизационная стоимость, как, например, в методе банкира — это такая усредненная по всем выполненным операциям верхняя оценка. Никакой случайности здесь нет. Среднее берем по выполненным операциям.
Это печально. На самом деле уровень организации конкурса для внешнего наблюдателя является неплохим мерилом того, что происходит внутри компании. Мне кажется, этот уровень можно было бы повысить почти бесплатно.
Я могу сказать, чтобы сделал бы я на месте организатора.
1. По своему опыту, качественно проверять стоит только два-три исходника за один заход. В день можно сделать четыре захода — 8-12 исходников. Итого, на 400 посылок получаем примерно 40 рабочих дней на ответ, т.е. два месяца.
2. Безмолвно заставлять ждать людей два месяца некрасиво. Я бы сообщил о том, как устроена проверка, выдал участнику номер, и где-нибудь вывесил список ориентировочной даты ответа (номер -> дата). Для этого, можно было бы даже написать бота.
3. Условия конкурса можно было бы сформулировать более четко. Нигде не описан формат посылки. Я бы с удовольствием перед проверкой глазами, прогнал решения через автоматические тесты. Приводить к стандартному виду все исходники — лишняя работа для проверяющего.
Программы у многих заведений открыты. Некоторые даже видеозаписи выкладывают. Если Вы сомневаетесь, что лекционный материал идет на экзамен… ну, сомневайтесь.
Представьте, что в какой-то момент дерево выстроилось в односвязный список. Ключ с наименьшим значением в самом низу. Пусть все запросы спрашивают условно минус бесконечность. Без splay-а каждый запрос будет обрабатываться за линейное время. А так, мы выдергиваем один из ближайших элементов наверх и в следующий раз нам не придется лезть глубоко.
Я думаю, Вам надо провести практическое исследование. Нагенерируйте разные последовательности запросов, возьмите что-то из реальной жизни и протестируйте это на разных деревьях, в том числе, придуманных Вами. Потом можете рассказать, что у Вас получилось в отдельном посте на Хабре.
1. Если все известно заранее, то splay дерево не нужно. Мне кажется, что решение должно быть каким-то таким. Берем ключ такой, что сумма частот слева и справа от него меньше половины. Делаем его корнем. Строим поддеревья рекурсивно. С точностью до константы, это дерево точно будет оптимальным.
Хаффман, если что, меняет порядок ключей. Так что его технику использовать напрямую не получится.
2 (и 3). Мне пока не очень понятно, как именно у вас происходит балансировка. Кроме того, статистика — это доп. информация, которую надо хранить. В AVL, красно-черных деревьях достаточно одного-двух битов доп. информации, в splay — нуля.
3. Нет, от тяжелых запросов деревья не защищены. В некоторых случаях делают splay через раз, или подбрасывают монетку, делать ли splay. Но вообще, такое может случиться. Если нужны быстрые ответы на единичные запросы, лучше использовать другие деревья: AVL, B, красно-черные.
В теории есть алгоритм Левина, который решает любую задачу за асимптотически оптимальное время. Он перебирает все возможные программы и запускает их параллельно. Но константа там большая, да…
По поводу практической части. Да, действительно, каждый раз делать splay — это печально. Начиная с 2000 люди предложили несколько эвристик, которые позволяют оптимизировать работу splay-дерева. Кое-каких результатов на практике добились. Я видимо напишу заметку-дополнение как ответ этому комментарию и одному выше, что хорошего здесь происходило.
Да, можно. Все зависит от того, какое распределение требуется.
Вопрос я не очень понял. У меня в конце поста есть идея, как из скобочной последовательности получить дерево произвольной арности из n + 1 вершины и бинарное дерево из n вершин. Распределение и там, и там равномерное. Значение n можно выбрать любое.
У каждого инструмента есть своя область применения. Splay-деревья ведут себя хорошо при последовательной обработке большого набора запросов с произвольным распределением. Они экономичны в плане количества информации, которую требуется хранить в узлах. Кроме того, splay-дерево — это сливаемая структура данных.
С другой стороны я согласен, что постоянное изменение структуры не делает их привлекательными для параллельного или чисто-функционального программирования. Чтобы что-то получить, нужно чем-то расплатиться.
А как вам такой фильтр? Оставляем комментарий, если он удовлетворяет хотя бы одному следующему условию.
а) содержит строго больше одной точки;
б) содержит ссылку;
в) содержит вопросительный знак;
г) имеет длину, больше чем 150 символов.
Можно сделать себе дебетовую карточку с нулевой комиссией специально для интернет-платежей. Когда я это делал, мне выдали сразу две карточки. Сказали, что одну можно использовать как скрытую и хранить на ней деньги, а другой расплачиваться. Переводить деньги между карточками можно через интернет-банкинг тоже без комиссии.
Альтернативный вариант: можно заводить виртуальную дочернюю карточку с ограниченной исходящей суммой. Мне кажется, это идеальное решение для всякий Google Play и т.п.
Персистентность бывает разной. Различают три вида.
1. Частичная. Можем читать любую версию, но менять только последнюю. Граф версий представляет собой односвязный список.
2. Полная. Можем читать и менять любую версию. Граф версий — это дерево.
3. Конфлюэнтная. Это полная персистентность с возможностью мерджа версий. Граф версий — даг (ориентированный ациклический граф).
ЧФСД гарантирует все три уровня персистентности. С другой стороны, почти любую императивную структуру данных можно превратить в частичную или полную с амортизационно константным ухудшением по памяти и времени. Правда, она не будет ЧФСД.
Я в доказательство верю. Правда можно было немного прокомментировать смысл определений.
Ваше определение не-фундаментальности говорит, что ткни в любой элемент последовательности, дальше найдется еще один, который отстоит от первого на расстоянии > eps. Определение препода — откинь сколько хочешь первых элементов, и я все равно найду два таких, что между ними расстояние > eps.
Суть доказательства:
(1) -> (2) Откинули k элементов. Для следующего по определению (1) найдется элемент, отдаленный на eps.
(2) -> (1) Взяли k-ый. После него найдутся два элемента, между которыми расстояние > eps. Ну значит, хотя бы до одного из них от k-ого расстояние будет eps / 2.
P.S. Я, правда, не знаю, стало ли понятней… Но мне это видится так.
Амортизационная стоимость, как, например, в методе банкира — это такая усредненная по всем выполненным операциям верхняя оценка. Никакой случайности здесь нет. Среднее берем по выполненным операциям.
Я могу сказать, чтобы сделал бы я на месте организатора.
1. По своему опыту, качественно проверять стоит только два-три исходника за один заход. В день можно сделать четыре захода — 8-12 исходников. Итого, на 400 посылок получаем примерно 40 рабочих дней на ответ, т.е. два месяца.
2. Безмолвно заставлять ждать людей два месяца некрасиво. Я бы сообщил о том, как устроена проверка, выдал участнику номер, и где-нибудь вывесил список ориентировочной даты ответа (номер -> дата). Для этого, можно было бы даже написать бота.
3. Условия конкурса можно было бы сформулировать более четко. Нигде не описан формат посылки. Я бы с удовольствием перед проверкой глазами, прогнал решения через автоматические тесты. Приводить к стандартному виду все исходники — лишняя работа для проверяющего.
P.S. Есть ощущение, что письмо генерировали умным автопереводом на русский.
Для школьников: ЛКШ
Для студентов: МГУ, КТ ИТМО, Академический ун-т, ШАД, CS Center. Знающие могут дополнить список.
1. Если все известно заранее, то splay дерево не нужно. Мне кажется, что решение должно быть каким-то таким. Берем ключ такой, что сумма частот слева и справа от него меньше половины. Делаем его корнем. Строим поддеревья рекурсивно. С точностью до константы, это дерево точно будет оптимальным.
Хаффман, если что, меняет порядок ключей. Так что его технику использовать напрямую не получится.
2 (и 3). Мне пока не очень понятно, как именно у вас происходит балансировка. Кроме того, статистика — это доп. информация, которую надо хранить. В AVL, красно-черных деревьях достаточно одного-двух битов доп. информации, в splay — нуля.
3. Нет, от тяжелых запросов деревья не защищены. В некоторых случаях делают splay через раз, или подбрасывают монетку, делать ли splay. Но вообще, такое может случиться. Если нужны быстрые ответы на единичные запросы, лучше использовать другие деревья: AVL, B, красно-черные.
Вам анализ не нужен, кому-то интересен, а у кого-то это splay-деревья с анализом — билет в экзамене.
По поводу практической части. Да, действительно, каждый раз делать splay — это печально. Начиная с 2000 люди предложили несколько эвристик, которые позволяют оптимизировать работу splay-дерева. Кое-каких результатов на практике добились. Я видимо напишу заметку-дополнение как ответ этому комментарию и одному выше, что хорошего здесь происходило.
Вопрос я не очень понял. У меня в конце поста есть идея, как из скобочной последовательности получить дерево произвольной арности из n + 1 вершины и бинарное дерево из n вершин. Распределение и там, и там равномерное. Значение n можно выбрать любое.
С другой стороны я согласен, что постоянное изменение структуры не делает их привлекательными для параллельного или чисто-функционального программирования. Чтобы что-то получить, нужно чем-то расплатиться.
а) содержит строго больше одной точки;
б) содержит ссылку;
в) содержит вопросительный знак;
г) имеет длину, больше чем 150 символов.
Можно сделать себе дебетовую карточку с нулевой комиссией специально для интернет-платежей. Когда я это делал, мне выдали сразу две карточки. Сказали, что одну можно использовать как скрытую и хранить на ней деньги, а другой расплачиваться. Переводить деньги между карточками можно через интернет-банкинг тоже без комиссии.
Альтернативный вариант: можно заводить виртуальную дочернюю карточку с ограниченной исходящей суммой. Мне кажется, это идеальное решение для всякий Google Play и т.п.
Персистентность бывает разной. Различают три вида.
1. Частичная. Можем читать любую версию, но менять только последнюю. Граф версий представляет собой односвязный список.
2. Полная. Можем читать и менять любую версию. Граф версий — это дерево.
3. Конфлюэнтная. Это полная персистентность с возможностью мерджа версий. Граф версий — даг (ориентированный ациклический граф).
ЧФСД гарантирует все три уровня персистентности. С другой стороны, почти любую императивную структуру данных можно превратить в частичную или полную с амортизационно константным ухудшением по памяти и времени. Правда, она не будет ЧФСД.
Ваше определение не-фундаментальности говорит, что ткни в любой элемент последовательности, дальше найдется еще один, который отстоит от первого на расстоянии > eps. Определение препода — откинь сколько хочешь первых элементов, и я все равно найду два таких, что между ними расстояние > eps.
Суть доказательства:
(1) -> (2) Откинули k элементов. Для следующего по определению (1) найдется элемент, отдаленный на eps.
(2) -> (1) Взяли k-ый. После него найдутся два элемента, между которыми расстояние > eps. Ну значит, хотя бы до одного из них от k-ого расстояние будет eps / 2.
P.S. Я, правда, не знаю, стало ли понятней… Но мне это видится так.