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

[Mark Lawrence]

On 13/06/2017 16:29, Jonathan Hartley wrote:
> 
> 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? :-)
> 
Fine by me, on my calendar for 13th July :-)

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

Mark Lawrence