Welcome, guest | Sign In | My Account | Store | Cart
import collections
import time

# Requires Python 2.7

class Node(object):
   
def __init__(self, value):
       
self.value = value
       
self.next = None
       
self.prev = None

   
def __repr__(self):
       
if not self:
           
return '%s()' % (self.__class__.__name__,)
       
return '%s(%r)' % (self.__class__.__name__, self.value)


class LinkedList(collections.MutableSequence):
   
def __init__(self, iterable=None):
       
self.sentinel = Node(None)
       
self.sentinel.next = self.sentinel
       
self.sentinel.prev = self.sentinel
       
self.__len = 0
       
if iterable is not None:
           
self += iterable        

   
def get_node(self, index):
        node
= sentinel = self.sentinel
        i
= 0
       
while i <= index:
            node
= node.next
           
if node == sentinel:
               
break
            i
+= 1
       
if node == sentinel:
            node
= None
       
return node

   
def __getitem__(self, index):
        node
= self.__get_node(index)
       
return node.value
   
   
def __len__(self):
       
return self.__len

   
def __setitem__(self, index, value):
        node
= self.get_node(index)
        node
.value = value
       
   
def __delitem__(self, index):
        node
= self.get_node(index)
       
if node:
            node
.prev.next = node.next
           
if node.next:
                node
.next.prev = node.prev    
            node
.prev = None
            node
.next = None
            node
.value = None
           
self.__len -= 1
               
   
def __repr__(self):
       
if not self:
           
return '%s()' % (self.__class__.__name__,)
        list_
= [self.__get_node(i).value for i in range(len(self))]
       
return '%s(%r)' % (self.__class__.__name__, list_)
   
   
def append(self, value):
        sentinel
= self.sentinel
        node
= Node(value)
       
self.insert_between(node, sentinel.prev, sentinel)

   
def insert(self, index, value):
        sentinel
= self.sentinel
        new_node
= Node(value)
        len_
= len(self)
       
if len_ == 0:
           
self.insert_between(new_node, sentinel, sentinel)
       
elif index >= 0 and index < len_:
            node
= self.get_node(index)  
           
self.insert_between(new_node, node.prev, node)
       
elif index == len_:
           
self.insert_between(new_node, sentinel.prev, sentinel)
       
else:
           
raise IndexError
       
self.__len += 1
               
   
def insert_between(self, node, left_node, right_node):
       
if node and left_node and right_node:
            node
.prev = left_node
            node
.next = right_node
            left_node
.next = node
            right_node
.prev = node
       
else:
           
raise IndexError
       
   
class Stopwatch(object):
   
def __init__(self):
       
self.__start = 0.0
       
self.__stop = 0.0
       
self.__duration = 0.0
   
   
def start(self):
       
self.__start = time.time()
       
return self
   
   
def stop(self):
       
self.__stop = time.time()
       
self.__duration = self.__stop - self.__start
       
return self.__duration
   
   
def duration(self):
       
return self.__duration  

class Profiler(object):
   
def __init__(self, size):
       
self.size = size
       
self.list = None
       
self.linked_list = None
       
self.sw_create_list = Stopwatch()
       
self.sw_create_linked_list = Stopwatch()
       
self.sw_pop_list = Stopwatch()
       
self.sw_pop_linked_list = Stopwatch()
       
   
def create_list(self):
       
self.sw_create_list.start()
       
self.list = [i for i in range(self.size)]
       
self.sw_create_list.stop()
   
   
def create_linked_list(self):
       
self.sw_create_linked_list.start()
       
self.linked_list = LinkedList()
       
for value in self.list:
           
self.linked_list.append(value)
       
self.sw_create_linked_list.stop()
   
   
def pop_list(self):
       
self.sw_pop_list.start()
       
for i in range(self.size):
           
del self.list[0]
       
self.sw_pop_list.stop()
   
   
def pop_linked_list(self):
       
self.sw_pop_linked_list.start()
       
for i in range(self.size):
           
del self.linked_list[0]
       
self.sw_pop_linked_list.stop()
       
   
def report(self):
       
print("%6s %10d" % ("Size", self.size))
       
print("%6s %10s %10s %10s" % ("Type", "Create", "Pop", "Total"))
       
print("%6s %10.2f %10.2f %10.2f" % ("List", self.sw_create_list.duration(), \
               
self.sw_pop_list.duration(), self.sw_create_list.duration() + self.sw_pop_list.duration()))
       
print("%6s %10.2f %10.2f %10.2f" % ("Linked", self.sw_create_linked_list.duration(), \
               
self.sw_pop_linked_list.duration(), self.sw_create_linked_list.duration() + \
               
self.sw_pop_linked_list.duration()))
       
print
       
   
def run(self):
       
self.create_list()
       
self.pop_list()
       
self.create_linked_list()
       
self.pop_linked_list()
       
self.report()
   
if __name__ == '__main__':
   
Profiler(1000).run()
   
Profiler(2000).run()
   
Profiler(5000).run()
   
Profiler(10000).run()
   
Profiler(20000).run()
   
Profiler(50000).run()
   
Profiler(100000).run()
   
print "Complete."

History