Персистентный дек — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(откамелкезил конспект; исправил согласно своим правилам)
Строка 1: Строка 1:
  
  
'''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т.е. их можно удалять и добавлять как в начало, так и в конец дека.
+
'''Дек''' (англ. ''deque'' {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т.е. их можно удалять и добавлять как в начало, так и в конец дека.
  
 
Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать {{---}} с обоих.
 
Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать {{---}} с обоих.
Строка 10: Строка 10:
 
Персистентный дек можно визуально представить как односвязный список, где каждый узел хранит пару - левый элемент и правый, а также ''ребёнка'' {{---}} ссылку на следующий узел. Только левый и правый элемент каждого узла хранят в два раза больше объектов, чем предыдущий. Это удобно сделать с помощью типа ''пара''.  
 
Персистентный дек можно визуально представить как односвязный список, где каждый узел хранит пару - левый элемент и правый, а также ''ребёнка'' {{---}} ссылку на следующий узел. Только левый и правый элемент каждого узла хранят в два раза больше объектов, чем предыдущий. Это удобно сделать с помощью типа ''пара''.  
  
Тип <tex>Pair</tex> хранит пару элементов <tex>first</tex> и <tex>last</tex> типов <tex>T</tex>.
+
Тип <tex>\mathrm{Pair}</tex> хранит пару элементов <tex>first</tex> и <tex>last</tex> типов <tex>T</tex>.
 
<code style = "display: inline-block;">
 
<code style = "display: inline-block;">
   Pair<<tex>T</tex>> {
+
   Pair<T> {
     <tex>T ~first;</tex>
+
     T first
     <tex>T ~last;</tex>
+
     T last
   };
+
   }
 
</code>
 
</code>
Сам дек можно инициализировать напрямую, вызвав конструктор <tex>Deque(left, ~child, ~right)</tex>, или через шаблоны <tex>Deque<T></tex>, тогда произойдёт следующее:
+
Сам дек можно инициализировать напрямую, вызвав конструктор <tex>\mathrm{Deque(left, ~child, ~right)}</tex>, или через шаблоны <tex>\mathrm{Deque<T>}</tex>, тогда произойдёт следующее:
 
<code style = "display: inline-block;">
 
<code style = "display: inline-block;">
   Deque<<tex>T</tex>> {
+
   Deque<T<> {
     <tex>T</tex> left;
+
     T left
     <tex>T</tex> right;
+
     T right
     Deque<Pair<<tex>T</tex>>> child;
+
     Deque<Pair<T>> child
   };
+
   }
 
</code>
 
</code>
Наша структура данных персистентна, следовательно операция <tex> push\_front(x, ~D) </tex> возвращает новый дек <tex> D' </tex> c элементом <tex> x </tex>, добавленным в начало <tex> D </tex>.
+
Наша структура данных персистентна, следовательно операция <tex> \mathrm{pushFront(x, ~D)} </tex> возвращает новый дек <tex> D' </tex> c элементом <tex> x </tex>, добавленным в начало <tex> D </tex>.
  
Пустой дек будем обозначать значком <tex> \emptyset </tex>, а пустую пару {{---}} <tex> \varnothing </tex>, чтобы было яснее, когда мы обращаемся к деку, а когда к элементу. Когда мы хотим добавить элемент в начало дека или удалить из начала, то прежде всего обращаемся к полю ''left''. Если же работаем с концом, то обращаемся сперва к полю ''right''.
+
Пустой дек будем обозначать значком <tex> \emptyset </tex>, а пустую пару {{---}} <tex> \varnothing </tex>, чтобы было яснее, когда мы обращаемся к деку, а когда к элементу. Когда мы хотим добавить элемент в начало дека или удалить из начала, то прежде всего обращаемся к полю <tex>left</tex>. Если же работаем с концом, то обращаемся сперва к полю <tex>right</tex>.
 
<code>
 
<code>
   push_front(x, D)
+
   '''pushFront'''(x, D)
     if D == <tex> \emptyset </tex>
+
     '''if''' D == <tex> \emptyset </tex>
 
       // если дек пустой, то формируем новый дек
 
       // если дек пустой, то формируем новый дек
       return Deque(x, <tex> \emptyset ,~ \varnothing </tex>)
+
       '''return''' Deque(x, <tex> \emptyset ,~ \varnothing </tex>)
     else if D.left == <tex> \varnothing </tex>
+
     '''else if''' D.left == <tex> \varnothing </tex>
 
       // если левый ребенок не существует, то сделаем <tex> x </tex> левым ребёнком
 
       // если левый ребенок не существует, то сделаем <tex> x </tex> левым ребёнком
       return Deque(x, D.child, D.right)
+
       '''return''' Deque(x, D.child, D.right)
     else
+
     '''else'''
 
       // иначе объединим левого ребёнка с новым элементом и попытаемся добавить в дек на следующем уровне
 
       // иначе объединим левого ребёнка с новым элементом и попытаемся добавить в дек на следующем уровне
       return Deque(<tex> \varnothing </tex>, push_front(Pair(x, D.left), D.child), D.right)
+
       '''return''' Deque(<tex> \varnothing </tex>, pushFront(Pair(x, D.left), D.child), D.right)
 
</code>
 
</code>
  
Метод <tex> pop\_front(D) </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.
+
Метод <tex> \mathrm{popFront(D)} </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.
 
<code>
 
<code>
   pop_front(D)
+
   '''popFront'''(D)
     if D == <tex> \emptyset </tex>
+
     '''if''' D == <tex> \emptyset </tex>
 
       // изъятие элемента из пустого дека возвращает пару "нулевой элемент {{---}} пустой дек"
 
       // изъятие элемента из пустого дека возвращает пару "нулевой элемент {{---}} пустой дек"
       return <tex> \mathcal{h} \varnothing ,~ \emptyset \mathcal{i} </tex>
+
       '''return''' <tex> \mathcal{h} \varnothing ,~ \emptyset \mathcal{i} </tex>
     else if D.left <tex> \neq ~\varnothing</tex>
+
     '''else''' if D.left <tex> \neq ~\varnothing</tex>
 
       // если левый ребёнок не пуст, то возвращаем пару из него и нового дека без левого ребёнка,
 
       // если левый ребёнок не пуст, то возвращаем пару из него и нового дека без левого ребёнка,
 
       // но если остался только левый ребёнок, но возвращаем его и пустой дек
 
       // но если остался только левый ребёнок, но возвращаем его и пустой дек
       if D.child = <tex> \emptyset </tex> and D.right = <tex> \varnothing </tex>
+
       '''if''' D.child = <tex> \emptyset </tex> '''and''' D.right = <tex> \varnothing </tex>
         return <tex> \mathcal{h} </tex>D.left, <tex> \emptyset \mathcal{i} </tex>
+
         '''return''' <tex> \mathcal{h} </tex>D.left, <tex> \emptyset \mathcal{i} </tex>
       return <tex> \mathcal{h} </tex>D.left, Deque(<tex> \varnothing </tex>, D.child, D.right)<tex> \mathcal{i} </tex>
+
       '''return''' <tex> \mathcal{h} </tex>D.left, Deque(<tex> \varnothing </tex>, D.child, D.right)<tex> \mathcal{i} </tex>
     else if D.child == <tex> \varnothing</tex>
+
     '''else if''' D.child == <tex> \varnothing</tex>
 
       // если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует,
 
       // если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует,
 
       // то вернём пару из правого ребёнка и абсолютно пустого дека
 
       // то вернём пару из правого ребёнка и абсолютно пустого дека
       return <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex>
+
       '''return''' <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex>
     else
+
     '''else'''
 
       /*  
 
       /*  
       * если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод pop_front()
+
       * если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод <tex>\mathrm{popFront}</tex>
       * и возвращённую пару "элемент {{---}} новый дек" сохраняем в переменные temp & newDeque
+
       * и возвращённую пару "элемент {{---}} новый дек" сохраняем в переменные <tex>temp</tex> и <tex>newDeque</tex>.
       * Рекурсивные вызовы прекратятся, как только левый ребёнок окажется существующим
+
       * Рекурсивные вызовы прекратятся, как только левый ребёнок окажется не пустым
       * или в деке будет отсутствовать ссылка на следующий дек
+
       * или в деке будет отсутствовать ссылка на следующий дек.
 
       */     
 
       */     
       temp, newDeque <tex> \leftarrow </tex> pop_front(D.child)
+
       temp, newDeque <tex> \leftarrow </tex> popFront(D.child)
       if temp == <tex> \varnothing </tex>
+
       '''if''' temp == <tex> \varnothing </tex>
 
         /*
 
         /*
 
         * это возможно только тогда, когда в деке на максимальной глубине все элементы оказались пусты,
 
         * это возможно только тогда, когда в деке на максимальной глубине все элементы оказались пусты,
         * значит, мы сейчас на предпоследнем уровне, левый ребёнок пустой и child ссылается на абсолютно пустой дек,
+
         * значит, мы сейчас на предпоследнем уровне, левый ребёнок пустой и <tex>child</tex> ссылается на абсолютно пустой дек,
         * поэтому возвращаем right текущего дека и пустой дек
+
         * поэтому возвращаем <tex>right</tex> текущего дека и пустой дек
 
         */
 
         */
         return <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex>
+
         '''return''' <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex>
       else
+
       '''else'''
 
         /*
 
         /*
         * если всё же temp не пуст, то надо вернуть первый элемент пары temp;  
+
         * если всё же <tex>temp</tex> не пуст, то надо вернуть первый элемент пары temp;  
         * в качестве left нового дека надо поставить temp.last (на уровне ниже temp хранил
+
         * в качестве left нового дека надо поставить <tex>temp.last</tex> (на уровне ниже <tex>temp</tex> хранил
         * в два раза больше элементов, поэтому на текущем уровне temp.last будет соответствовать  
+
         * в два раза больше элементов, поэтому на текущем уровне <tex>temp.last</tex> будет соответствовать  
         * требуемому количеству элементов); newDeque делаем child'ом
+
         * требуемому количеству элементов); <tex>newDeque</tex> делаем <tex>child</tex>'ом
         * нового дека, а right текущего right'ом нового
+
         * нового дека, а <tex>right</tex> текущего <tex>right</tex>'ом нового
 
         */
 
         */
         return <tex> \mathcal{h} </tex>temp.first, Deque(temp.last, newDeque, D.right)<tex> \mathcal{i} </tex>
+
         '''return''' <tex> \langle </tex>temp.first, Deque(temp.last, newDeque, D.right)<tex> \rangle </tex>
 
</code>
 
</code>
  
Строка 93: Строка 93:
 
Рассмотрим поподробнее операции. В худшем случае элементы будут добавляться только в один конец, а извлекаться из другого.
 
Рассмотрим поподробнее операции. В худшем случае элементы будут добавляться только в один конец, а извлекаться из другого.
  
=== push_front ===
+
=== pushFront ===
  
Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Процесс добавления можно представить, как прибавление 1 к разряду числа в двоичном представлении: если в разряде 1, то подряд идущие за ней единицы обнулятся {{---}} элементы объединяются в пары, иначе становятся на место этого разряда.
+
Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Процесс добавления можно представить, как прибавление <tex>1</tex> к разряду числа в двоичном представлении: если в разряде <tex>1</tex>, то подряд идущие за ней единицы обнулятся {{---}} элементы объединяются в пары, иначе становятся на место этого разряда.
 
[[Файл:PushDequeExample.png|700px]]
 
[[Файл:PushDequeExample.png|700px]]
  
=== pop_front ===
+
=== popFront ===
  
Посмотрим, как работает ''pop_front'' на примере дека, симметричного нашему предыдущему (в рисунке надо понять, что элементы хранятся слева направо: ''4 3 2 1'').
+
Посмотрим, как работает <tex>\mathrm{popFront}</tex> на примере дека, симметричного нашему предыдущему (в рисунке надо понять, что элементы хранятся слева направо: <tex>4 ~3 ~2 ~1</tex>).
  
Запустим первый <tex> pop\_front() </tex>. Он будет рекурсивно вызывать сам себя, пока не дойдёт до последней ветки. Тогда в пару <tex> \left \langle temp, ~newDeque \right \rangle </tex> сохранятся две пары элементов и пустой дек высоты 0. Так как <tex> temp </tex> не пуст, то в предыдущий рекурсивный вызов вернётся пара: в temp новый сохранится пара ''4 3'', на текущем уровне будет пара ''2 1'', а <tex> child </tex> будет ссылаться на пустой дек. Потом пара ''4 3'' передастся выше, ''child'' сохраняет ссылку на предыдущий дек, и, наконец, ''4'' извлечётся. И так далее. Аналогично добавлению, процесс извлечения элемента можно представить, как вычитание 1 из младшего разряда двоичного числа.
+
Запустим первый <tex> \mathrm{popFront} </tex>. Он будет рекурсивно вызывать сам себя, пока не дойдёт до последней ветки. Тогда в пару <tex> \left \langle temp, ~newDeque \right \rangle </tex> сохранятся две пары элементов и пустой дек высоты <tex>0</tex>. Так как <tex> temp </tex> не пуст, то в предыдущий рекурсивный вызов вернётся пара: в <tex>temp</tex> новый сохранится пара <tex>4 ~3</tex>, на текущем уровне будет пара <tex>2 ~1</tex>, а <tex> child </tex> будет ссылаться на пустой дек. Потом пара <tex>4 ~3</tex> передастся выше, <tex>child</tex> сохраняет ссылку на предыдущий дек, и, наконец, <tex>4</tex> извлечётся. И так далее. Аналогично добавлению, процесс извлечения элемента можно представить, как вычитание <tex>1</tex> из младшего разряда двоичного числа.
  
 
[[Файл:PopDequeExample.png|700px]]
 
[[Файл:PopDequeExample.png|700px]]

Версия 19:33, 11 ноября 2013


Дек (англ. deque — double ended queue — очередь с двумя концами) — структура данных с двусторонним доступом к элементам, т.е. их можно удалять и добавлять как в начало, так и в конец дека.

Кроме дека ещё существует структура данных, называемая steque, которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать — с обоих.

Эффективная реализация

Tree deque.png

Персистентный дек можно визуально представить как односвязный список, где каждый узел хранит пару - левый элемент и правый, а также ребёнка — ссылку на следующий узел. Только левый и правый элемент каждого узла хранят в два раза больше объектов, чем предыдущий. Это удобно сделать с помощью типа пара.

Тип [math]\mathrm{Pair}[/math] хранит пару элементов [math]first[/math] и [math]last[/math] типов [math]T[/math].

 Pair<T> {
   T first
   T last
 }

Сам дек можно инициализировать напрямую, вызвав конструктор [math]\mathrm{Deque(left, ~child, ~right)}[/math], или через шаблоны [math]\mathrm{Deque\lt T\gt }[/math], тогда произойдёт следующее:

 Deque<T<> {
   T left
   T right
   Deque<Pair<T>> child
 }

Наша структура данных персистентна, следовательно операция [math] \mathrm{pushFront(x, ~D)} [/math] возвращает новый дек [math] D' [/math] c элементом [math] x [/math], добавленным в начало [math] D [/math].

Пустой дек будем обозначать значком [math] \emptyset [/math], а пустую пару — [math] \varnothing [/math], чтобы было яснее, когда мы обращаемся к деку, а когда к элементу. Когда мы хотим добавить элемент в начало дека или удалить из начала, то прежде всего обращаемся к полю [math]left[/math]. Если же работаем с концом, то обращаемся сперва к полю [math]right[/math].

 pushFront(x, D)
   if D == [math] \emptyset [/math]
     // если дек пустой, то формируем новый дек
     return Deque(x, [math] \emptyset ,~ \varnothing [/math])
   else if D.left == [math] \varnothing [/math]
     // если левый ребенок не существует, то сделаем [math] x [/math] левым ребёнком
     return Deque(x, D.child, D.right)
   else
     // иначе объединим левого ребёнка с новым элементом и попытаемся добавить в дек на следующем уровне
     return Deque([math] \varnothing [/math], pushFront(Pair(x, D.left), D.child), D.right)

Метод [math] \mathrm{popFront(D)} [/math] возвращает пару [math] \left \langle e, ~D' \right \rangle [/math] из первого элемента и нового дека, полученного из старого изъятием этого элемента.

 popFront(D)
   if D == [math] \emptyset [/math]
     // изъятие элемента из пустого дека возвращает пару "нулевой элемент — пустой дек"
     return [math] \mathcal{h} \varnothing ,~ \emptyset \mathcal{i} [/math]
   else if D.left [math] \neq ~\varnothing[/math]
     // если левый ребёнок не пуст, то возвращаем пару из него и нового дека без левого ребёнка,
     // но если остался только левый ребёнок, но возвращаем его и пустой дек
     if D.child = [math] \emptyset [/math] and D.right = [math] \varnothing [/math]
       return [math] \mathcal{h} [/math]D.left, [math] \emptyset \mathcal{i} [/math]
     return [math] \mathcal{h} [/math]D.left, Deque([math] \varnothing [/math], D.child, D.right)[math] \mathcal{i} [/math]
   else if D.child == [math] \varnothing[/math]
     // если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует,
     // то вернём пару из правого ребёнка и абсолютно пустого дека
     return [math] \mathcal{h} [/math]D.right, [math]\emptyset \mathcal{i} [/math]
   else
     /* 
      * если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод [math]\mathrm{popFront}[/math]
      * и возвращённую пару "элемент — новый дек" сохраняем в переменные [math]temp[/math] и [math]newDeque[/math].
      * Рекурсивные вызовы прекратятся, как только левый ребёнок окажется не пустым 
      * или в деке будет отсутствовать ссылка на следующий дек.
      */     
     temp, newDeque [math] \leftarrow [/math] popFront(D.child)
     if temp == [math] \varnothing [/math]
       /*
        * это возможно только тогда, когда в деке на максимальной глубине все элементы оказались пусты,
        * значит, мы сейчас на предпоследнем уровне, левый ребёнок пустой и [math]child[/math] ссылается на абсолютно пустой дек,
        * поэтому возвращаем [math]right[/math] текущего дека и пустой дек
        */
       return [math] \mathcal{h} [/math]D.right, [math]\emptyset \mathcal{i} [/math]
     else
       /*
        * если всё же [math]temp[/math] не пуст, то надо вернуть первый элемент пары temp; 
        * в качестве left нового дека надо поставить [math]temp.last[/math] (на уровне ниже [math]temp[/math] хранил
        * в два раза больше элементов, поэтому на текущем уровне [math]temp.last[/math] будет соответствовать 
        * требуемому количеству элементов); [math]newDeque[/math] делаем [math]child[/math]'ом
        * нового дека, а [math]right[/math] текущего [math]right[/math]'ом нового
        */
       return [math] \langle [/math]temp.first, Deque(temp.last, newDeque, D.right)[math] \rangle [/math]

Операции добавления в правый конец и извлечение из него делаются симметрично.

Таким образом, если мы добавляем элементы только в один конец, то на [math] i [/math]-ом уровне дека не более [math] 2^i [/math] элементов. Пусть глубина текущего дека [math] d. [/math] Тогда в нём может находится не более [math] n ~=~ 1 ~+~ 2 ~+~ 4 ~+...+~ 2^d [/math] объектов, откуда получаем [math] d = \mathcal{b} \log_2 ~n \mathcal{c} [/math].

Чтобы извлечь элемент, придётся спуститься не больше, чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за [math] O(\log ~n) [/math]

Пример

Рассмотрим поподробнее операции. В худшем случае элементы будут добавляться только в один конец, а извлекаться из другого.

pushFront

Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Процесс добавления можно представить, как прибавление [math]1[/math] к разряду числа в двоичном представлении: если в разряде [math]1[/math], то подряд идущие за ней единицы обнулятся — элементы объединяются в пары, иначе становятся на место этого разряда. PushDequeExample.png

popFront

Посмотрим, как работает [math]\mathrm{popFront}[/math] на примере дека, симметричного нашему предыдущему (в рисунке надо понять, что элементы хранятся слева направо: [math]4 ~3 ~2 ~1[/math]).

Запустим первый [math] \mathrm{popFront} [/math]. Он будет рекурсивно вызывать сам себя, пока не дойдёт до последней ветки. Тогда в пару [math] \left \langle temp, ~newDeque \right \rangle [/math] сохранятся две пары элементов и пустой дек высоты [math]0[/math]. Так как [math] temp [/math] не пуст, то в предыдущий рекурсивный вызов вернётся пара: в [math]temp[/math] новый сохранится пара [math]4 ~3[/math], на текущем уровне будет пара [math]2 ~1[/math], а [math] child [/math] будет ссылаться на пустой дек. Потом пара [math]4 ~3[/math] передастся выше, [math]child[/math] сохраняет ссылку на предыдущий дек, и, наконец, [math]4[/math] извлечётся. И так далее. Аналогично добавлению, процесс извлечения элемента можно представить, как вычитание [math]1[/math] из младшего разряда двоичного числа.

PopDequeExample.png

См. также

Ссылки