Как стать автором
Обновить

Комментарии 5

Хорошая статья, иллюстрации сделаны шикарно — видно, старались. Я помню мне на втором курсе универа, на экзамене, в качестве одного из вопросов как раз попалась персистентная очередь :)
Спасибо. Если не секрет, какой алгоритм вы проходили, с кучей стеков?
Да, именно его.
Интересно. Но что-то я не могу прикинуть в уме асимптотику — у нас получается же O(n) амортизированное?
И какой порядок константы перед этим самым n?
Начиная с какого порядка размера очереди она начнёт выигрвать по производительности у O(n*log(n)), которая явно проще в реализации?
Интересно. Но что-то я не могу прикинуть в уме асимптотику — у нас получается же O(n) амортизированное?
Если вы про теоретическое описание, то нет, никакой амортизационный анализ не применяется, каждый запрос выполняется строго за O(1), об этом даже где-то по тексту написано. Если же вы про мою реализацию, то да, там в силу использования вектора для хранения очередей, каждый push или pop выполняется за амортизированное O(1). Естественно, можно обойтись и без него, например, используя односвязный список и выдавая указатель на его элемент вместо числового id, я использовал вектор для упрощения и соответствия интерфейсу теоретического описания.
И какой порядок константы перед этим самым n?
В каких единицах надо это оценить?
Начиная с какого порядка размера очереди она начнёт выигрывать по производительности у O(n*log(n)), которая явно проще в реализации?
Что вы имеете в виду под простой реализацией за O(n log n): реализацию с помощью персистентного дерева поиска по неявному ключу? По-хорошему, надо просто написать и сравнить. Но осмелюсь предположить, что на данных, при которых эти реализации будут быстрее наивной за n2, мой алгоритм всегда будет выигрывать. Почему я так считаю? Потому что при добавлении или удалении вершины из персистентного дерева (операции push и pop, соотвественно), мы вынуждены будем создать копию каждой вершины на пути до корня. А на таких данных, длина этого пути будет не меньше 10 (она порядка log n). Впрочем, это лишь гипотеза. К слову, я не считаю её явно проще в реализации, она скорее проще в понимании, потому что от неперсистентного варианта почти не отличается, объем же кода будет примерно одним и тем же.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории