A Stack?
A Stack is using the principle first-in-last-out.
It is like a stack of plates. The last one you put on the top is the first one you take.
How can you implement them in Python? Well, we are in luck, you can use a Stack, and if done correctly, you will have the same performance as an actual Stack implementation will have.
But first, how can you do it wrong?
Well, you might think that the first element of the list is the top of your stack, hence in you will insert the elements on the first position, and, hence, remove them from the first position as well.
# Create a list as a stack
s = []
# Insert into the first position.
element = 7
s.insert(0, element)
# Remove from the first position.
s.pop(0)
Sounds about right?
Let’s test that and compare it with a different approach. To add the newest element to the end of the list, and, hence, remove them from the end of the list.
# Create a list and use it as stack
s = []
# Insert element in last postion
element = 7
s.append(element)
# Remove from the last position
s.pop()
Let’s check the performance of those two approaches.
Comparing the performance of the two approaches
How do you compare. You can use cProfile library. It is easy to use and informative results
See the sample code below, which compares the two approaches by create a stack each and inserting n elements to it and removing them afterwards.
import cProfile
def profile_list_as_queue_wrong(n):
s = []
for i in range(n):
s.insert(0, i)
while len(s) > 0:
s.pop(0)
def profile_list_as_queue_correct(n):
s = []
for i in range(n):
s.append(i)
while len(s) > 0:
s.pop()
def profile(n):
profile_list_as_queue_wrong(n)
profile_list_as_queue_correct(n)
cProfile.run("profile(100000)")
The results are given here.
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 5.842 5.842 <string>:1(<module>)
1 0.078 0.078 0.107 0.107 Stack.py:12(profile_list_as_queue_correct)
1 0.000 0.000 5.842 5.842 Stack.py:20(profile)
1 0.225 0.225 5.735 5.735 Stack.py:4(profile_list_as_queue_wrong)
200002 0.017 0.000 0.017 0.000 {len}
100000 0.007 0.000 0.007 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
100000 3.547 0.000 3.547 0.000 {method 'insert' of 'list' objects}
200000 1.954 0.000 1.954 0.000 {method 'pop' of 'list' objects}
2 0.014 0.007 0.014 0.007 {range}
Observe that the “wrong” implementation takes over 5 seconds and the “correct” takes approximately 0.1 second. Over a factor 50 in difference.
Looking into the details
If we look at the complexities given by Python, it explains it all.
The Python lists amortised complexities are given on this page.
And you notice that the append and pop (last element) are O(1), which means constant time. Constant time, means that the operations are independent on the size of the lists. That means the correct implementation gives O(n) time complexity.
On the other hand, the insert and pop(0) have linear performance. That basically means that we with the wrong implementation end up with O(n^2) time complexity.
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.
