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

[Mark Lawrence]

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