Comments 15
жоский перевод
-5
Прорекламирую свою статью про персистентную очередь, выполняющую каждую операцию за фактическое (не амортизационное) O(1), может кому-то будет интересно. Есть ещё альтернативная реализация, использующая 5 или 6 персистентных стеков. Обе реализации обладают свойством иммутабельности, значит могут быть реализованы на функциональном языке программирования (хотя я, конечно, не знаток).
Последовательность (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов)Это называется дек (deque).
+2
К слову, если персистентность не нужна (вы всегда работаете только с последней версией структуры), то можно просто эмулировать очередь двумя стеками, это будет работать за амортизированное O(1).
0
можно поподробней как добраться до конца очереди (или эмулировать это) за О(1). Можно в пальчиковых деревьях использовать не 2-3 деревья, а бинарные деревья, но как 2мя стеками сэмулировать — не знаю. Хочу заметить в иммутабельных переменных указателей как таковых нет.
0
можно поподробней как добраться до конца очереди (или эмулировать это) за О(1)Никак. У очереди нет операции «обойти все элементы», есть только «положить в начало» и «забрать из конца».
Очередь на двух стеках А и Б делается по следующим правилам:
1. Элементы кладутся в стек А.
2. Элементы забираются из стека Б.
3. Стек Б пустой тогда и только тогда, когда очередь пуста.
Из третьего правила легко догадаться, почему реализация за амортизированное O(1).
+1
Сори, а как положить что-то в конец за О(1)? Ведь всё равно надо дойти до конца.
0
Я вот не хочу прямо спойлерить. Вместо этого я ещё раз поставлю ударение на словах амортизированная сложность и два стека. Думайте, как два стека могут делать вид, что они очередь, в большинстве случаев извлекая элементы за постоянное время, но иногда тратя больше времени на некоторое действие.
0
Смотрите, есть списки:
ну, или используя встроенный синтаксис:
Пусть у нас есть список:
Как мне за О(1) добраться до конца? напоминаю, у нас нет указателей.
Для того, чтобы добавить в начало, это О(1):
А для того, чтобы получить всё, кроме последнего элемента, или просто получить последний элемент — О(н):
data List a = Nil | Cons a (List a)
ну, или используя встроенный синтаксис:
data [a] = [] | a : [a]
Пусть у нас есть список:
stack = 5 : 4 :3 : 2 : 1 : []
stack_ = Cons 5 (Cons 4 (Cons 3 (Cons 2 (Cons 1 Nil))))
Как мне за О(1) добраться до конца? напоминаю, у нас нет указателей.
Для того, чтобы добавить в начало, это О(1):
stack1 = 6 : stack
stack1_ = Cons 6 : stack_
А для того, чтобы получить всё, кроме последнего элемента, или просто получить последний элемент — О(н):
last [] = error "last"
last [x] = x
last (x:xs) = last xs
init [] = error "inits"
init [x] = []
init (x:xs) = x : inits xs
0
Ок, сдаюсь
empty_queue = ([], [])
enqueue :: a -> ([a], [a]) -> ([a], [a])
dequeue :: ([a], [a]) -> (a, ([a], [a]))
-- O(1)
enqueue x (a, b) = (x:a, b)
-- O(n)
reversed list = reversed' list []
where
reversed' [] reversed = reversed
reversed' (x:xs) reversed = reversed' xs (x:reversed)
dequeue ([], []) = error "Dequeuing an empty queue"
-- O(1)
dequeue (a, x:b) = (x, (a, b))
-- O(n)
dequeue (a, []) = dequeue ([], reversed a)
+1
Пиковое вытаскивание так и остаётся О(n). Хотя средняя сложность, конечно, падает, согласен.
Я бы добавил тип сюда:
Кстати, в следующей части статьи я опишу как добавлять к пальчиковому дереву. Пиковая сложность там будет O(lg n). Соединение 2х очередей — O(lg(min(m,n)))
Я бы добавил тип сюда:
type Queue a = ([a], [a])
enqueue :: a -> Queue a -> Queue a
dequeue :: Queue a -> (a, Queue a)
Кстати, в следующей части статьи я опишу как добавлять к пальчиковому дереву. Пиковая сложность там будет O(lg n). Соединение 2х очередей — O(lg(min(m,n)))
+1
Кстати, возможно не так очевидно, как для очереди, но дек также можно эмулировать двумя стеками, имея при этом амортизированное O(1) на каждую операцию. Основная идея, собственно, точно такая же: заводим два стека, один символизирует голову, второй — хвост, соответственно при вставке/удалении из головы/хвоста, добавляем или удаляем из нужного стека. Единственная разница, когда стек, из которого нам нужно удалить, оказывается пустым, то мы перемещаем в него из другого стека не все элементы сразу, а только нижнюю половину (можно взять и другую пропорцию).
0
дубль
0
Однако, для уменьшения информативности, требование ослаблено для пальчиковых деревьев, и, вместо этого, каждый префикс и суффикс содержат от 1 до 4 элементов.
Кто-нибудь понял, что это значит? Почему не до 3-х элементов?
+1
Я так понял, что это означает, что каждое 2-3 дерево является пальчиковым, но не каждое пальчиковое является 2-3 деревом (если существуют аффиксы размера 4).
При этом, каждое пальчиковое дерево является 2-3-4 деревом, но не каждое 2-3-4 дерево является пальчиковым (если существуют ветки размера 4).
При этом, каждое пальчиковое дерево является 2-3-4 деревом, но не каждое 2-3-4 дерево является пальчиковым (если существуют ветки размера 4).
0
Sign up to leave a comment.
Пальчиковые деревья (Часть 1. Представление)