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

[Jonathan Hartley]

On 06/13/2017 09:04 AM, Mark Lawrence via python-uk wrote:
> 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?
>

I'd rather not if I get any say in that, because I agreed in the T&C of 
the coding challenge that I wouldn't discuss the problem or solutions 
with others, and I don't want to annoy them right now. How about in a 
month? :-)


-- 
Jonathan Hartley    tartley at tartley.com    http://tartley.com
Made out of meat.   +1 507-513-1101        twitter/skype: tartley