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

[Jonathan Hartley]

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 Hartley    tartley at tartley.com    http://tartley.com
Made out of meat.   +1 507-513-1101        twitter/skype: tartley

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-uk/attachments/20170607/3691f248/attachment.html>