Amortized Analysis of Spreading and Gathering
Learn about the analysis of gather and spread methods.
We'll cover the following...
Next, we consider the cost of the _gather(u)
and _spread(u)
methods that may be executed by the add(i, x)
and remove(i)
methods. For the sake of completeness, here they are:
class SEList(BaseList):class BDeque(ArrayDeque):"""A bounded-size deque"""def __init__(self, b):super(SEList.BDeque, self).__init__()self.a = new_array(b+1)def _resize(self):passclass Node(object):def __init__(self, b):self.d = SEList.BDeque(b)self.prev = Noneself.next = Nonedef __init__(self, b):super(SEList, self).__init__()self.b = bself._initialize()def _spread(self, u):w = ufor j in range(self.b):w = w.nextw = self._add_before(w)while w is not u:while w.d.size() < self.b:w.d.add_first(w.prev.d.remove_last())w = w.prev
The implementation of the _gather()
method is:
class SEList(BaseList):class BDeque(ArrayDeque):"""A bounded-size deque"""def __init__(self, b):super(SEList.BDeque, self).__init__()self.a = new_array(b+1)def _resize(self):passclass Node(object):def __init__(self, b):self.d = SEList.BDeque(b)self.prev = Noneself.next = Nonedef __init__(self, b):super(SEList, self).__init__()self.b = bself._initialize()def _gather(self, u):w = ufor j in range(self.b-1):while w.d.size() < self.b:w.d.add_last(w.next.d.remove_first())w = w.nextself._remove_node(w)
Amortization
The running time of each of these methods is dominated by the two nested loops. Both the inner and outer loops execute at most times, so the total running time of each of these methods is . However, the following lemma shows that these methods execute on at most one out of every calls to add(i, x)
or remove(i)
.
Lemma: If an empty SEList
is created and any sequence of calls to add(i, x)
and remove(i)
is performed, then the total time spent during all calls to_ _spread()
and _gather()
is .
Proof: We will use the potential method of amortized analysis. We say that a node u
is fragile if u
’s block does not contain elements (so that u
is either the last node, or contains ...