Stack, Quque, Deque¶
Introduction¶
In [5]:
# Using a Python list (array) and adding/removing elements
s=[2,3,4]
s.append(5)
s.insert(0,1)
print (s)
print ("s before:",s)
print ("pop(): ", s.pop())
print ("s after:", s)
print ("pop(): ", s.pop())
print ("s after:", s)
print ("pop(0): ", s.pop(0))
print ("s finally:", s)
[1, 2, 3, 4, 5] s before: [1, 2, 3, 4, 5] pop(): 5 s after: [1, 2, 3, 4] pop(): 4 s after: [1, 2, 3] pop(0): 1 s finally: [2, 3]
In [4]:
# plotting works very similar to MATLAB
%matplotlib inline
import matplotlib.pyplot as plt
x = [10, 50, 100, 150]
y = [3, 5, 10, 22]
plt.plot(x, y, 'o-')
plt.show()
In [5]:
# Implement a Stack:
class MyStack:
""" simple stack implemented using a Python list (array)"""
def __init__(self):
self.data = []
def push(self,x):
self.data.append(x)
def pop(self):
return self.data.pop()
def is_empty(self):
return len(self.data) == 0
s = MyStack()
s.push(3)
s.push(4)
s.push(5)
print (s.pop(), s.pop(), s.pop())
print (s.is_empty())
5 4 3 True
In [9]:
def stack_fill_and_empty(n):
S = MyStack()
for item in range(n):
S.push(item)
while n>0:
S.pop()
n -= 1
sizes = [10000, 20000, 40000, 80000, 160000, 320000]
for n in sizes:
%timeit stack_fill_and_empty(n)
100 loops, best of 3: 10.1 ms per loop 10 loops, best of 3: 20.3 ms per loop 10 loops, best of 3: 42.2 ms per loop 10 loops, best of 3: 84.3 ms per loop 10 loops, best of 3: 171 ms per loop 1 loop, best of 3: 336 ms per loop
In [6]:
import numpy as np
def fit_poly(x,y,k):
n = len(x)
x = np.array(x)
y = np.array(y)
A = np.zeros((n,k+1))
for i in range(k+1):
A[:,i] = np.array(x)**i
c = np.linalg.lstsq(A,y)[0]
misfit = np.linalg.norm(np.dot(A,c)-y)
return c, misfit
In [12]:
x = sizes
y = [5, 9.96, 19.9, 41, 80, 167]
c, misfit = fit_poly(x, y, 3) # find a good coefficient!
print ("coefficients:",c)
print ("misfit:", misfit)
coefficients: [ 1.87340498e-08 5.17145190e-04 -2.15266843e-10 7.18392359e-16] misfit: 0.888829000074
In [13]:
xx = np.linspace(0,x[-1],100)
yy = xx * 0
for idx,cc in enumerate(c):
yy = yy + cc*xx**idx
plt.plot(x, y, 'o')
plt.plot(xx, yy, 'r')
plt.show()
In [14]:
# alternatively fitting f(x)=c0 x^c1:
c, misfit = fit_poly(np.log(x),np.log(y),1)
print ("best fitting polynomial:",np.exp(c[0]),"x^",c[1])
best fitting polynomial: 0.000449869695702 x^ 1.01054524356
We can conclude that pushing n elements to the stack and removing them again takes O(n) time. This means each operation is O(1) (on average!)
1. Test queue operations using a Python list¶
We first use a Python list (array) as an (inefficient) queue. Our test consists of queueing n elements and then dequeueing all of them. Complete the code below, time for different n, create a fit of the right degree and conclude what the cost of queueing and dequeueing one element is.
In [15]:
def fill_and_empty_queue_using_list(n):
L = []
for item in range(n):
# queue item in L (add to end):
L.append(item)
while n>0:
# dequeue item in L (remove from start):
L.pop(0)
n -= 1
sizes = [10000,20000,40000,80000,160000]
for n in sizes:
%timeit fill_and_empty_queue_using_list(n)
10 loops, best of 3: 32 ms per loop 10 loops, best of 3: 114 ms per loop 1 loop, best of 3: 433 ms per loop 1 loop, best of 3: 1.71 s per loop 1 loop, best of 3: 7.62 s per loop
In [21]:
x = sizes
y = [32,114,433,1710,7620] # fill
c, misfit = fit_poly(x,y,3)
print ("coefficients:",c )
print ("misfit:", misfit)
xx = np.linspace(0,x[-1],100)
yy = xx * 0
for idx,cc in enumerate(c):
yy = yy + cc*xx**idx
plt.plot(x, y, 'o')
plt.plot(xx, yy, 'r')
plt.show()
coefficients: [ -1.46669513e+01 2.49499663e-03 1.94077714e-07 5.53479138e-13] misfit: 4.21615602063
In [19]:
c, misfit = fit_poly(np.log(x),np.log(y),1)
print ("best fitting polynomial:",np.exp(c[0]),"x^",c[1])
best fitting polynomial: 3.95860390174e-07 x^ 1.96980411604
fill_and_empty_queue_using_list(n) takes O(n^2). To conclude:
- enqueue one element (append to a list) takes O(n)
- dequeuing one element (remove from the left) takes O(n)
- while removing the last element takes O(1).
2. Using a deque¶
First determine the correct functions to call to enqueue (add to the right) and dequeue (pop from the left) an element from a deque. Try it out in the next block (it should print 1, then 2, then 3). Then complete dequeue_fill_and_empty() with those commands, benchmark it, fit a curve, and conclude.
In [1]:
from collections import deque
Q = deque()
Q.append(1) # enqueue 1
Q.append(2) # enqueue 2
Q.append(3) # enqueue 3
print (Q.popleft()) # dequeue and print
print (Q.popleft()) # dequeue and print
print (Q.popleft()) # dequeue and print
1 2 3
In [2]:
def dequeue_fill_and_empty(n):
L = deque()
for item in range(n):
L.append(item) # enqueue
while n>0:
L.popleft() # now dequeue
n -= 1
sizes = [10000,20000,40000,80000,160000]
for n in sizes:
%timeit dequeue_fill_and_empty(n)
100 loops, best of 3: 4.02 ms per loop 100 loops, best of 3: 7.74 ms per loop 100 loops, best of 3: 15.9 ms per loop 10 loops, best of 3: 33.7 ms per loop 10 loops, best of 3: 66.8 ms per loop
In [12]:
x = sizes
y = [405,826,1690,3460,7020] # fill
c, misfit = fit_poly(x,y,3)
print ("coefficients:",c)
print ("misfit:", misfit)
xx = np.linspace(0,x[-1],100)
yy = xx * 0
for idx,cc in enumerate(c):
yy = yy + cc*xx**idx
plt.plot(x, y, 'o')
plt.plot(xx, yy, 'r')
plt.show()
coefficients: [ -1.17192045e+01 4.12576009e-02 3.66996621e-08 -1.24282529e-13] misfit: 1.43208966732
In [13]:
c, misfit = fit_poly(np.log(x),np.log(y),1)
print ("best fitting polynomial:",np.exp(c[0]),"x^",c[1])
best fitting polynomial: 0.0308013560467 x^ 1.02975127859
Filling and emptying a queue (n elements) based on Python's deque takes: O(n). Therefore, a single enqueue() or dequeue() takes: O(1). Read up on wikipedia on "deque" an state the cost for the operations for:
- add element on left: O(1)
- add element on right: O(1)
- remove element on left: O(1)
- remove element on right: O(1)
Is that what you see? Yes
3: Now implement a deque using a doubly-linked list¶
Complete the implementation, make sure the tests work, and finally time the operations.
In [15]:
class MyDeque:
""" a double-ended queue implemented using a linked list"""
class ListItem:
""" an item in a doubly-linked list"""
def __init__(self, x, prev, next):
self.item = x
self.prev = prev
self.next = next
def __init__(self):
self.head = None
self.tail = None
def push_right(self, x):
if self.head == None:
self.head = MyDeque.ListItem(x,None, None)
self.tail = self.head
else:
n = MyDeque.ListItem(x, self.tail, None)
self.tail.next = n
self.tail = n
def push_left(self, x):
if self.head == None:
self.head = MyDeque.ListItem(x,None, None)
self.tail = self.head
else:
n = MyDeque.ListItem(x, None, self.head)
self.head.prev = n
self.head=n
def pop_left(self):
if self.head == None:
return None
item = self.head.item
if self.head.next == None:
self.head = None
self.tail = None
else:
newhead = self.head.next
newhead.prev = None
self.head = newhead
return item
def pop_right(self):
if self.head == None:
return None
item = None
item = self.tail.item
if self.tail.prev == None:
self.head = None
self.tail = None
else:
newtail = self.tail.prev
newtail.next = None
self.tail = newtail
return item
def print_it(self):
it = self.head
print ("llbracket ", end="")
while it != None:
print (it.item, end=" ")
it = it.next
print ("]]")
Q = MyDeque()
Q.push_right(1)
Q.push_right(2)
Q.push_right(3)
Q.push_left(0)
Q.push_right(4)
Q.print_it()
print ("pop_left:", Q.pop_left())
print ("pop_right:", Q.pop_right())
Q.print_it()
print ("pop_left:", Q.pop_left())
Q.print_it()
print ("pop_left:", Q.pop_left())
print ("pop_right:", Q.pop_right())
Q.print_it()
print ("pop_left:", Q.pop_left())
print ("pop_right:", Q.pop_right())
llbracket 0 1 2 3 4 ]] pop_left: 0 pop_right: 4 llbracket 1 2 3 ]] pop_left: 1 llbracket 2 3 ]] pop_left: 2 pop_right: 3 llbracket ]] pop_left: None pop_right: None
In [16]:
# some more tests:
Q = MyDeque()
Q.push_left(1)
Q.push_right(2)
assert(Q.head.item == 1)
assert(Q.tail.item == 2)
assert(Q.head.next == Q.tail)
assert(Q.head.prev == None)
assert(Q.tail.prev == Q.head)
assert(Q.pop_right()==2)
assert(Q.head.item == 1)
assert(Q.head == Q.tail)
assert(Q.head.prev == None)
assert(Q.head.next == None)
assert(Q.pop_right()==1)
assert(Q.head == None)
assert(Q.tail == None)
for n in range(5):
Q.push_right(n)
Q.print_it()
for n in range(5):
assert(Q.pop_left()==n)
assert(Q.pop_left()==None)
for n in range(5):
Q.push_left(n)
Q.print_it()
for n in range(5):
assert(Q.pop_right()==n)
assert(Q.pop_right()==None)
for n in range(5):
Q.push_right(n)
Q.print_it()
for n in range(5):
assert(Q.pop_right()==4-n)
for n in range(5):
Q.push_left(n)
Q.print_it()
for n in range(5):
assert(Q.pop_left()==4-n)
print ("ok")
llbracket 0 1 2 3 4 ]] llbracket 4 3 2 1 0 ]] llbracket 0 1 2 3 4 ]] llbracket 4 3 2 1 0 ]] ok
In [17]:
def test_our_deque(n):
Q = MyDeque()
for idx in range(n):
Q.push_right(n)
Q.push_left(n)
for idx in range(n):
Q.pop_left()
Q.pop_right()
sizes = [10000, 20000, 40000, 80000, 160000]
for n in sizes:
%timeit test_our_deque(n)
10 loops, best of 3: 66.1 ms per loop 10 loops, best of 3: 135 ms per loop 1 loop, best of 3: 269 ms per loop 1 loop, best of 3: 539 ms per loop 1 loop, best of 3: 1.09 s per loop
In [18]:
c, misfit = fit_poly(np.log(x),np.log(y),1)
print ("best fitting polynomial:",np.exp(c[0]),"x^",c[1])
best fitting polynomial: 0.0308013560467 x^ 1.02975127859
test_our_deque() takes: O(n). Therefore, all operations take O(1) as expected!