[python-uk] A stack with better performance than using a list

Mark Lawrence breamoreboy at yahoo.co.uk
Tue Jun 13 10:04:11 EDT 2017

On 07/06/2017 18:50, Jonathan Hartley wrote:
> I recently submitted a solution to a coding challenge, in an employment 
> context. One of the questions was to model a simple stack. I wrote a 
> solution which appended and popped from the end of a list. This worked, 
> but failed with timeouts on their last few automated tests with large 
> (hidden) data sets.
>  From memory, I think I had something pretty standard:
> class Stack:
> def __init__(self):
>          self.storage = []
> def push(arg):
>          self.storage.append(arg)
> def pop():
> return self.storage.pop() if self.storage else None
> def add_to_first_n(n, amount):
> for n in range(n):
>              self.storage[n] += amount
> def dispatch(self, line)
>          tokens = line.split()
>          method = getattr(self, tokens[0])
>          args = tokens[1:]
>          method(*args)
> def main(lines):
>      stack = Stack()
> for line in lines:
>          stack.dispatch(line)
> (will that formatting survive? Apologies if not)
> Subsequent experiments have confirmed that appending to and popping from 
> the end of lists are O(1), amortized.
> So why is my solution too slow?
> This question was against the clock, 4th question of 4 in an hour. So I 
> wasn't expecting to produce Cython or C optimised code in that timeframe 
> (Besides, my submitted .py file runs on their servers, so the 
> environment is limited.)
> So what am I missing, from a performance perspective? Are there other 
> data structures in stdlib which are also O(1) but with a better constant?
> Ah. In writing this out, I have begun to suspect that my slicing of 
> 'tokens' to produce 'args' in the dispatch is needlessly wasting time. 
> Not much, but some.
> Thoughts welcome,
>      Jonathan
> -- 
> Jonathan Hartleytartley at tartley.com     http://tartley.com
> Made out of meat.   +1 507-513-1101        twitter/skype: tartley

Any objections to me putting this thread up on the main Python mailing 
list and reddit as it seems rather interesting?

My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

More information about the python-uk mailing list