In this video we will see how cProfile (default Python library) can help you to get run-times from your Python program.
Queue vs Python lists
In this video we will compare the performance of a simple Queue implemented directly into Python (no optimisations) with the default Python list.
Can it compare with it on performance?
This is where time complexity analysis come into the picture. A Queue insert and deletion is O(1) time complexity. A Python list used as a queue has O(n) time complexity.
But does the performance and run-time show the same? Here we compare the run-time by using cProfile in Python.
Want to learn more about Linked-lists, Stacks and Queues?
We all know what a queue is. You go to the grocery store and get spinach, strawberry and bananas for your shake. Then you see a long line of people in front of the register. That line is a queue.
The same holds in programming. You create queues to process data or input of any kind.
How to implement a Queue in Python
It is easier than you think.
First you create a Node class to represent each node in a queue. A node is an abstraction to represent a point to the next node and the actual element.
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
Then you create the class for the Queue.
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, element):
if self.head is None:
self.head = self.tail = Node(element)
else:
n = Node(element, self.tail)
self.tail.next_node = n
self.tail = n
def dequeue(self):
element = self.head.element
if self.tail == self.head:
self.tail = self.head = None
else:
self.head = self.head.next_node
return element
def is_empty(self):
return self.head is None
How does it work. Let’s make a simple example.
q = Queue()
for i in range(10):
q.enqueue(i)
while not q.is_empty():
print(q.dequeue())
Which will output.
0
1
2
3
4
5
6
7
8
9
Yes! You guessed it.
How do we test performance?
I like to use the cProfile library. It is easy to use and gives informative results.
So how do you test performance? You simply import the cProfile library and use the cProfile.run(…) call.
You also need to do some operations to see how your Queue performs. See the code as an example.
import cProfile
def profile_queue(n):
q = Queue()
for i in range(n):
q.enqueue(i)
while not q.is_empty():
q.dequeue()
def profile(n):
profile_queue(n)
cProfile.run("profile(100000)")
The interesting line is line 9, which tells us how much time is spend in the call to profile_queue.
But is the result good?
We need to compare it to other implementations.
Performance testing the Queue with a Python list
Python lists are used for anything. Can we use a Python list as a Queue. Of course. Let’s try to implement that and compare it to our Queue.
import cProfile
def profile_queue(n):
q = Queue()
for i in range(n):
q.enqueue(i)
while not q.is_empty():
q.dequeue()
def profile_list_as_queue(n):
q = []
for i in range(n):
q.insert(0,i)
while len(q) > 0:
q.pop()
def profile(n):
profile_queue(n)
profile_list_as_queue(n)
cProfile.run("profile(100000)")
