Комментарии 42
> Заключение. Сегодня мы рассмотрели
Откуда это вот берётся? :) Уже в куче статей в последнее время видел. Вы ж не лабораторную сдаёте и не курсовой, дык зачем этот официоз? В конце-концов, резюме, конечно, нужно, но чаще всего оно в таком виде подаётся, что ощущаешь себя преподом, принимающим списанную лабу.
Откуда это вот берётся? :) Уже в куче статей в последнее время видел. Вы ж не лабораторную сдаёте и не курсовой, дык зачем этот официоз? В конце-концов, резюме, конечно, нужно, но чаще всего оно в таком виде подаётся, что ощущаешь себя преподом, принимающим списанную лабу.
Да, пожалуй вы правы. Видимо это от чрезмерного старания — как-никак первый раз пробую себя на хабре =)
Это полезная штука.
Есть стандартная структура статей: вступление, основная часть и заключение.
Вступление нужно для того, чтобы дать высокоуровненвый обзор; чтобы читатель знал, на что обращать внимание.
А заключение нужно для того, чтобы еще раз напомнить основную идею, чтобы у вас сложилась цельная картина.
Кроме того, повторение--мать учения. Кажется, чтобы информация запомнилась, ее надо повторять через 20 минут, через пару чаов и через пару дней. Заключение как раз и соответствует первому повторению.
Есть стандартная структура статей: вступление, основная часть и заключение.
Вступление нужно для того, чтобы дать высокоуровненвый обзор; чтобы читатель знал, на что обращать внимание.
А заключение нужно для того, чтобы еще раз напомнить основную идею, чтобы у вас сложилась цельная картина.
Кроме того, повторение--мать учения. Кажется, чтобы информация запомнилась, ее надо повторять через 20 минут, через пару чаов и через пару дней. Заключение как раз и соответствует первому повторению.
А я и не говорил, что заключение не нужно. Нужно, конечно же. Но вот стиль подачи у многих очень попахивает университетской банальностью. «Мы рассмотрели бла-бла-бла, из чего сделали вывод бла-бла-бла».
Мы ж на хабре, а не на сдаче курсовой, да? К чему все эти ненужности? Можно простым языком написать, а не используя этот банальный штамп, вбитый всем нам в голову в институтах.
Мы ж на хабре, а не на сдаче курсовой, да? К чему все эти ненужности? Можно простым языком написать, а не используя этот банальный штамп, вбитый всем нам в голову в институтах.
А в какой литературе с этими структурами данных можно познакомиться поподробнее?
Насколько я знаю, это направление возникло относительно недавно, и в больших книжках (да и в маленьких тоже) о нём не прочитать.
P.S. о_О Ваш первый комментарий за последние почти 4 года.
P.S. о_О Ваш первый комментарий за последние почти 4 года.
Относительно недавно это стало модно на олимпиадах использовать, насколько я знаю.
Вот описание в точности такого же стека. Дата публикации: 15 December 1983.
Если не ошибаюсь, можно поискать что-нибудь Тарьяна
да, да, тоже на него наткнулся www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf
НЛО прилетело и опубликовало эту надпись здесь
Насколько я знаю, это направление возникло относительно недавно, и в больших книжках (да и в маленьких тоже) о нём не прочитать.
P.S. о_О Ваш первый комментарий за последние почти 4 года.
P.S. о_О Ваш первый комментарий за последние почти 4 года.
очень похоже все это на immutable stack из блога Эрика Липперта. Там только упор делается не на возможность получения любой версии, а на неизменяемость объекта. Впрочем, по-моему получилось тоже самое. кстати там целый цикл великолепный статей про неизменяемость (immutability)
На ВКОШПе последнем была задачка, которая решалась в том числе персистентным деревом отрезков.
> Очевидно, что один запрос работает за O(1)
Мне не очевидно :) Вы не заострили внимание, что это зависит от того, как мы ищем i-й элемент. На вскидку массив даст константный доступ, но или нужно зарезервировать достаточно места, либо его расширять динамически. Хотя в алгоритмах я не разбираюсь, и буду рад, если укажите, где я ошибся :)
Мне не очевидно :) Вы не заострили внимание, что это зависит от того, как мы ищем i-й элемент. На вскидку массив даст константный доступ, но или нужно зарезервировать достаточно места, либо его расширять динамически. Хотя в алгоритмах я не разбираюсь, и буду рад, если укажите, где я ошибся :)
Да, пожалуй стоило упомянуть, что речь идет о структуре типа массив.
Насчет динамического расширенияВ данном случае можно зарезервировать изначально массив из 1-го элемента. Далее при каждом добавлении количество элементов растет, и когда оно становится равным зарезервированному количеству мы расширяем его в два раза. Каждое расширение работает за O от количества элементов на момент расширения.
Если мы добавили n элементов (округлим n вверх так, чтобы n = 2 ^ k), то суммируя количество операций расширения получим: 1 + 2 + 4 + 8 +… + 2 ^ k = 2 ^ (k + 1) = 2 * n, откуда получаем O(n). Таким образом количество операций, потраченных на расширение имеет тот же порядок, что и количество операций добавления, что не может не радовать.
Насчет динамического расширенияВ данном случае можно зарезервировать изначально массив из 1-го элемента. Далее при каждом добавлении количество элементов растет, и когда оно становится равным зарезервированному количеству мы расширяем его в два раза. Каждое расширение работает за O от количества элементов на момент расширения.
Если мы добавили n элементов (округлим n вверх так, чтобы n = 2 ^ k), то суммируя количество операций расширения получим: 1 + 2 + 4 + 8 +… + 2 ^ k = 2 ^ (k + 1) = 2 * n, откуда получаем O(n). Таким образом количество операций, потраченных на расширение имеет тот же порядок, что и количество операций добавления, что не может не радовать.
Ах жаль, с тегом промазал =(
Ну и стоит упомянуть, что vector в c++ делает именно это.
Какое суммирование, вы о чем? Я нахожусь на n-ом шаге и до этого только добавлял, и мне нужно целиком скопировать весь массив. Это O(n)! В худшем случае, добавление займет O(n). Понятно, что в среднем, особенно если я буду часто удалять, это будет O(1), но это совсем не гарантировано.
Я правильно понял, что вы пытались усреднить?
Я правильно понял, что вы пытались усреднить?
А у понятия персистентная структура есть русское название?
Никогда не встречал, мне кажется что нет =)
«Неизменяемая» (хотя это скорее immutable), «сохраняемая», не? Хотя вообще отличеие persistent jn immutable лишь в хранении указателей на старые версии насколько я понимаю.
Вообще, мне казалось, что персистентный означает сохраняемый между запусками программы. Так что для таких структур, ИМХО, immutable лучше подходит.
Прочитав статью автора мне показалось, что его персистентный стек не что иное как immutable стэк. Беглое гугление привело меня в википедию, где написано «Persistent data structures are effectively immutable». То есть всякая persistent data structure является immutable. Но там не говорится, являются ли эти классы эквивалентными, то есть immutable -> persistent. Беглое гугление на этот вопрос ответа уже не дало, придумать immutable, но не persistent структуру мне не удалось. Поэтому я бы не стал утверждать, что «immutable лучше подходит» без должного обоснования.
«Persistence in computer science refers to the characteristic of state that outlives the process that created it» — с вики
По прочтении статьи возникло стойкое желание прочитать кого-нибудь авторитетного по этим структурам данных. Гугл мямлит что-то о модуле для Перла. Не более.
На мой скорый взгляд, тут описано некий намек на реализацию дерева с числовым индексом в виде идентификатора узла.
Меня гложат большие сомнения по поводу адекватности производительности поиска по несбалансированному дереву по цифровому индексу (в статье — номер ревизии стека) для обращения к элементам дерева\стека.
Непонятен вопрос, как собрать все конечные состояния стека (а их может быть список)?
Как держать актуальный список головных ревизий? /Головная ревизия — последнее на текущий момент изменение всех веток развития стека/
На мой скорый взгляд, тут описано некий намек на реализацию дерева с числовым индексом в виде идентификатора узла.
Меня гложат большие сомнения по поводу адекватности производительности поиска по несбалансированному дереву по цифровому индексу (в статье — номер ревизии стека) для обращения к элементам дерева\стека.
Непонятен вопрос, как собрать все конечные состояния стека (а их может быть список)?
Как держать актуальный список головных ревизий? /Головная ревизия — последнее на текущий момент изменение всех веток развития стека/
Головная ревизия — набор всех изменений одной ветки развития стека.
Чего-то не проснусь никак… Зачеркните мой предыдущий пост. :)
Головная ревизия — это последнее на текущий момент изменение в одной ветке развития.
Разрисована оранжевым фоном.
Состояние стека в одной из веток может быть получен, как я понимаю, проходом через все узлы соответствующей ветки (помечена красной окантовкой)
Головная ревизия — это последнее на текущий момент изменение в одной ветке развития.
Разрисована оранжевым фоном.
Состояние стека в одной из веток может быть получен, как я понимаю, проходом через все узлы соответствующей ветки (помечена красной окантовкой)
НЛО прилетело и опубликовало эту надпись здесь
Все это дело можно хранить на массиве (например vector в с++). Выше я писал почему это работает достаточно быстро. Никаких деревьев не нужно.
Классная задача и элегантный метод решения, супер. Интересно, каким способом можно реализовать персистентность произвольного графа.
Спасибо, полезная статья!
Можно привести еще несколько задач на эту структуру данных? И, если возможно, с контестером — чтобы можно было проверить решение.
Можно привести еще несколько задач на эту структуру данных? И, если возможно, с контестером — чтобы можно было проверить решение.
Конкретно на стэк — не знаю. Это достаточно простая структура. Есть задача на персистентное дерево отрезков с ВКОШП-2010 (I, «Откаты»). Но она довольно сложная.
Условия и тесты
Условия и тесты
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Персистентные структуры, часть 1: персистентный стек