Amortization

• Objective: estimate the complexity of sequences of operations rather than individual ones
• Allows distributing the costs of a few “expensive” operations over many “cheap” ones
  • e.g., a sequence of \(n\) operations can be \(O(n)\) even if some individual operations are not \(O(1)\)

Amortization (cont.)

• Amortization is an analysis tool used for classic algorithms (Tarjan 1985)
• But is often useful in the analysis of functional data structures

Reference:

“Purely functional data structures” Chris Okasaki, Cambridge University Press, 1998.

(Extended version of the author’s PhD thesis.)

Example: FIFO queues

• Remove elements from the front
• Add elements to the back
• “First-in, first-out” order

Queue API

type Queue     -- type of queues
type Elem      -- type of elements

enqueue :: Elem -> Queue -> Queue
              -- add an element to the back
dequeue :: Queue -> (Elem, Queue)
          -- get the element from the front
          -- and the smaller queue

empty :: Queue      -- make an empty queue

isEmpty :: Queue -> Bool  -- test emptyness

Naive implementation

type Queue = [Elem]

enqueue :: Elem -> Queue -> Queue
enqueue x list = list ++ [x]

dequeue :: Queue -> (Elem, Queue)
dequeue (first:rest) = (first, rest)
dequeue []   = error "dequeue: empty queue"

empty :: Queue
empty = []

isEmpty :: Queue -> Bool
isEmpty = null

Complexity

• dequeue, empty and isEmpty take \(O(1)\) time
• But enqueue takes \(O(n)\):

    enqueue x list = list ++ [x]
                       -- ^^ O(length list)

• Using imperative programming we could implement all operations in \(O(1)\)
  • e.g., using a pair of pointers into a linked-list
• Can we do a better purely functional implementation?

Batched queues

Represent the queue by a pair of lists:

• the front part;
• the back part, in reverse order.

type Queue = ([Elem],  [Elem])
           -- ^ front  ^ back 

Idea:

• dequeue from the begining of front
• enqueue into the begining of back

Batched queues

\[ \text{dequeue} \leftarrow \underbrace{\begin{array}{|c|c|c|c|} \hline 3 & 1 & 7 & 2 \\ \hline \end{array}}_{\text{front}}\! \underbrace{\begin{array}{|c|c|c|} \hline 4 & 5 & 9 \\ \hline \end{array}}_{\text{back}} \leftarrow \text{enqueue} \]

Can be represented as:

  ([3,1,7,2], [9,5,4])

(Note that the back list is in reverse order.)

Different representations

\[ \leftarrow \begin{array}{|c|c|c|c|c|c|c|} \hline 3 & 1 & 7 & 2 & 4 & 5 & 9 \\ \hline \end{array} \leftarrow \]

The representation is not unique, e.g.:

([3,1,7,2], [9,5,4])
([3,1,7], [9,5,4,2])

Also, the front or back may be empty:

([], [9,5,4,2,7,1,3])
([3,1,7,2,4,5,9], [])

Implementation

Recall: dequeue from the start of front and enqueue into the start of back.

Special case: to dequeue when the front is empty we must first reverse the back and move it to the front.

Implementation (cont.)

enqueue :: Elem -> Queue -> Queue
enqueue elem (front, back) = (front, elem:back)

dequeue :: Queue -> (Elem, Queue)
dequeue ([],back) = extract (reverse back) []
dequeue (front, back) = extract front back

-- helper function
extract (x:front) back = (x, (front,back))
extract [] back        = error "empty queue"

Complexity

• enqueue is always \(O(1)\)
• But the cost of dequeue is variable

cheap

if the front is not empty, we just extract the head: \(O(1)\)

expensive

if the front is empty, we need to reverse the back: \(O(n)\)

We will use amortization to show that \(n\) operations take only \(O(n)\) time (because expensive dequeues are infrequent).

Principles of amortization

Consider \(n\) operations over a data structure:

\[ s_0 \stackrel{t_1}{\mapsto} s_1 \stackrel{t_2}{\mapsto} s_2 \mapsto \cdots \stackrel{t_n}{\mapsto} s_n \]

\(s_{i-1}\) is the state before operation \(i\)

\(s_i\) is the state after operation \(i\) (and before \(i+1\))

\(t_i\) is the actual cost for operation \(i\)

We want an upper bound to the accumulated cost: \[ \sum_{i=1}^n t_i \]

Amortized cost

• Assign each operation an amortized cost \(a_i\)
• The amortized cost may be lower or higher than the actual cost
• But the following inequality should hold: \[ \sum_{i=1}^n a_i \geq \sum_{i=1}^n t_i \]
• The accumulated amortized costs should be an upper-bound on the accumulated actual costs
• Hence: we can use \(\sum_i a_i\) as an upper-bound for the cost of a sequence of \(n\) operations

Applying amortization

• We need choose some amortized costs \(a_i\) for each operation such that \[ \sum_{i=1}^n a_i \geq \sum_{i=1}^n t_i \]
• Instead of attempting this directly, we can employ special techniques:
  • “banker’s method”
  • “potential method” (also known as “physicist’s method”)
• We will show the potential method in detail

Potential method

Assume we find a function (called potential):

\[ \phi : S \rightarrow \mathbb{R}^+_0 \]

from the states \(s_0\), \(s_1\), etc. to non-negative numbers.

Define amortized costs \(a_i\) of operation \(i\):

\[ a_i := \underbrace{t_i}_{\text{actual cost}} + \underbrace{\phi(s_i)}_{\text{potential after}} - \underbrace{\phi(s_{i-1})}_{\text{potential before}} \]

Physicist method (cont.)

Theorem: If

• \(\phi\) is non-negative;
• \(\phi(s_0) = 0\)
• and \(a_i := t_i + \phi(s_i) - \phi(s_{i-1})\)

then: \[ \sum_{i=1}^n a_i \geq \sum_{i=1}^n t_i\ . \]

(The accumulated amortized costs are an upper-bound on the accumulated actual costs.)

Proving the upper bound

\[ \begin{align} \sum_{i=1}^n a_i & = \sum_{i=1}^n \left(t_i + \phi(s_i) - \phi(s_{i-1})\right) \\ & = \sum_{i=1}^n t_i + \underbrace{\sum_{i=1}^n \left(\phi(s_i) - \phi(s_{i-1})\right)}_{\text{telescoping sum}} \\ & = \sum_{i=1}^n t_i + \phi(s_n) - \phi(s_0) \\ & \geq \sum_{i=1}^n t_i \quad (\text{because}~\phi(s_0)=0 ~\text{and}~ \phi(s_n)\geq0) \end{align} \]

Choosing potential

When doing amortized analysis we can choose the potential function such that:

• cheap operations increase potential
• expensive operations decrease potential
• changes in potential offset the higher costs of expensive operations

\[ \begin{array}{ccc} s_{i-1} &\stackrel{t_i}{\longmapsto} & s_i \\ \vdots & & \vdots \\ \phi(s_{i-1}) & \underbrace{\color{blue}{\phi(s_i) - \phi(s_{i-1})}}_{\text{change}} & \phi(s_i) \end{array} \]

Batched Queues (revisited)

type Queue = ([Elem], [Elem]) -- front, back

enqueue :: Elem -> Queue -> Queue
enqueue elem (front, back) = (front, elem:back)

dequeue :: Queue -> (Elem, Queue)
dequeue ([],back) = extract (reverse back) []
dequeue (front, back) = extract front back

-- helper function
extract (x:front) back = (x, (front,back))
extract [] back        = error "empty queue"

Complexity

We will use potential method to show that:

• the amortized cost of each operation is \(O(1)\)
• hence, the cost of \(n\) operations is \(O(n)\)

Potential for queues

Recall that we first need to define a potential function:

\[ \phi : \text{Queue} \to \mathbb{R}^+_0 \]

Let

\[ \phi(f,b) := \text{length}~b \]

Observe:

\[ \begin{array}{rl} \phi(f,b) & \geq 0\\ \phi(\texttt{[]},\texttt{[]}) &= 0 \end{array} \]

Amortized cost of enqueue

        enqueue x (f,b) = (f, x:b)

The amortized cost \(a\) is:

\[ \begin{array}{rccc} a & =& \underbrace{1}_{\text{actual cost}} &+\quad \underbrace{\phi(f,x:b)}_{\text{potential after}} &-\quad \underbrace{\phi(f, b)}_{\text{potential before}} \\ & =& 1 & +\quad (1+\text{length}~b) &-\quad \text{length}~b\\ & =& 2 \end{array} \]

Amortized cost of dequeue (1)

If the front is non-empty:

         dequeue (x:f, b) = (x, (f, b))

The amortized cost is:

\[ \begin{array}{rccc} a & =& \underbrace{1}_{\text{actual cost}} &+\quad \underbrace{\phi(f,b)}_{\text{potential after}} &-\quad \underbrace{\phi(x:f, b)}_{\text{potential before}} \\ & =& 1 &+\quad \text{length}~b &-\quad \text{length}~ b \\ & =& 1 \end{array} \]

Amortized cost of dequeue (2)

If the front non-empty:

   dequeue ([], b) = (x, (xs,[])) 
   where x:xs = reverse b

The actual cost is \(\text{length}~b + 1\). The amortized cost is:

\[ \begin{array}{rccc} a & =& \underbrace{1+\text{length}~b}_{\text{actual cost}} &+\quad \underbrace{\phi(xs,\texttt{[]})}_{\text{potential after}} &-\quad \underbrace{\phi(\texttt{[]}, b)}_{\text{potential before}} \\ & =& 1 + \text{length}~b & + \quad 0 & - \quad \text{length}~b\\ & = &1 \end{array} \]

Amortized costs

Conclusion: all operations have \(O(1)\) amortized cost.

Conclusion

• The basic amortization technnique presented assumes that data structures are used in an ephemeral way
  • e.g. old versions of a queue are not re-used at a later time
• However, it is possible to reconcile amortization and persistence using lazy evaluation (cf. Okasaki’s PhD thesis)

Exercise 1

Implement a Haskell module for an abstract type for queues that are polymorphic on items, e.g.

data Queue a = Queue [a] [a]

Export all needed operations but don’t export the constructor.

Exercise 2: double-ended queues

Implement a variant that allows inserting and extracting from both the front and the back of the queue.

type Deque
type Elem

empty :: Deque
isEmpty :: Deque -> Bool
pushFront :: Elem -> Deque -> Deque
pushBack :: Elem -> Deque -> Deque
popFront :: Deque -> (Elem, Deque)
popBack :: Deque -> (Elem, Deque)

Execise 2 (cont.)

• Again the dequeue is represented by a pair of lists (the back is reversed)
• If one list becomes empty when extracting an element:
  • split the other list in half (or differing length by one)
  • reverse one of the halves
• Define the potential to be absolute value of the length difference: \[ \phi(f,b) := | \text{length}~ f - \text{length}~ b| \]
• Show the amortized cost of all operations is still \(O(1)\)