Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Amortized Analysis of Spreading and Gathering

Explore the amortized analysis of the _spread and _gather methods within SELists, learning how these methods impact the efficiency of add and remove operations. Understand how potential method helps measure performance, and discover how varying block sizes balance between ArrayList and DLList efficiencies for managing linked list data.

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:

Python 3.10.4
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):
            pass
        
    class Node(object):
        def __init__(self, b):
            self.d = SEList.BDeque(b)
            self.prev = None
            self.next = None
            
    def __init__(self, b):
        super(SEList, self).__init__()
        self.b = b
        self._initialize()
        
    def _spread(self, u):
        w = u
        for j in range(self.b):
            w = w.next
        w = 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 ...

Python 3.10.4
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):
            pass
        
    class Node(object):
        def __init__(self, b):
            self.d = SEList.BDeque(b)
            self.prev = None
            self.next = None
            
    def __init__(self, b):
        super(SEList, self).__init__()
        self.b = b
        self._initialize()
    def _gather(self, u):
        w = u
        for j in range(self.b-1):
            while w.d.size() < self.b:
                w.d.add_last(w.next.d.remove_first())
            w = w.next
        self._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 b+1b + 1 times, so the total running time of each of these methods is ...