What will we cover in this article
- What is a Queue?
- Implement a Queue in Python
- Make performance testing of it
- Compare it with performance of a Python list
What is a Queue?
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)")
Which will result in the following output.
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.819 0.819 <string>:1(<module>)
100000 0.310 0.000 0.351 0.000 Queue.py:11(enqueue)
100000 0.308 0.000 0.308 0.000 Queue.py:19(dequeue)
100000 0.041 0.000 0.041 0.000 Queue.py:2(__init__)
100001 0.021 0.000 0.021 0.000 Queue.py:27(is_empty)
1 0.132 0.132 0.819 0.819 Queue.py:34(profile_queue)
1 0.000 0.000 0.819 0.819 Queue.py:42(profile)
1 0.000 0.000 0.000 0.000 Queue.py:7(__init__)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.008 0.008 0.008 0.008 {range}
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)")
How does that compare? Let’s see.
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 3.680 3.680 <string>:1(<module>)
100000 0.295 0.000 0.331 0.000 Queue.py:11(enqueue)
100000 0.298 0.000 0.298 0.000 Queue.py:19(dequeue)
100000 0.036 0.000 0.036 0.000 Queue.py:2(__init__)
100001 0.019 0.000 0.019 0.000 Queue.py:27(is_empty)
1 0.104 0.104 0.756 0.756 Queue.py:34(profile_queue)
1 0.101 0.101 2.924 2.924 Queue.py:42(profile_list_as_queue)
1 0.000 0.000 3.680 3.680 Queue.py:50(profile)
1 0.000 0.000 0.000 0.000 Queue.py:7(__init__)
100001 0.005 0.000 0.005 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
100000 2.805 0.000 2.805 0.000 {method 'insert' of 'list' objects}
100000 0.012 0.000 0.012 0.000 {method 'pop' of 'list' objects}
2 0.004 0.002 0.004 0.002 {range}
Wow. Our Queue is way faster than the Python list.
But how is it comparing in general?
While it is difficult to see, the performance of the Queue is O(n) (linear) while the performance of the Python list as a Queue is O(n^2).
Hence, the Queue will outperform the Python list for this use case.
Python for Finance: Unlock Financial Freedom and Build Your Dream Life
Discover the key to financial freedom and secure your dream life with Python for Finance!
Say goodbye to financial anxiety and embrace a future filled with confidence and success. If you’re tired of struggling to pay bills and longing for a life of leisure, it’s time to take action.
Imagine breaking free from that dead-end job and opening doors to endless opportunities. With Python for Finance, you can acquire the invaluable skill of financial analysis that will revolutionize your life.
Make informed investment decisions, unlock the secrets of business financial performance, and maximize your money like never before. Gain the knowledge sought after by companies worldwide and become an indispensable asset in today’s competitive market.
Don’t let your dreams slip away. Master Python for Finance and pave your way to a profitable and fulfilling career. Start building the future you deserve today!
Python for Finance a 21 hours course that teaches investing with Python.
Learn pandas, NumPy, Matplotlib for Financial Analysis & learn how to Automate Value Investing.
“Excellent course for anyone trying to learn coding and investing.” – Lorenzo B.
