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

[Simon Hayward]

Rather than using a list, aren't deques more appropriate as a data
structure for stack like behaviour.

https://docs.python.org/3.6/library/collections.html#collections.deque


Regards
Simon


On Wed, 7 Jun 2017, at 19:33, Jonathan Hartley wrote:
> Hey.
> 
> Thanks for engaging, but I can't help with the most important of those 
> questions - the large data sets on which my solution failed due to 
> timeout are hidden from candidates. Not unreasonable to assume that they 
> do exercise deep stacks, and large args to add_to_first_n, etc.
> 
> Yes, the input looks exactly like your example. All args are integers. 
> The question asked for output corresponding to the top of the stack 
> after every operation. I omitted this print from inside the 'for' loop 
> in 'main', thinking it irrelevant.
> 
> I converted to integers inside 'dispatch'. 'args' must have actually 
> been created with:
> 
> args = [int(i) for i in tokens[1:]]
> 
> Where len(tokens) is never going to be bigger than 3.
> 
> Return values (from 'pop') were unused.
> 
> 
> On 6/7/2017 13:25, Stestagg wrote:
> > Do you have any more context?
> > For example, is the add_to_first_n likely to be called with very large 
> > numbers, or very often? Does the stack get very deep, or stay shallow?
> >
> > I'm assuming that lines look like this:
> >
> > push 1
> > push 2
> > add_to_first_n 2 10
> > pop
> > pop
> >
> > with all arguments as integers, and the final value being returned 
> > from main()?
> > How did you convert from string inputs to numeric values?
> > How did you manage return values?
> >
> > :D
> >
> > On Wed, Jun 7, 2017 at 6:51 PM Jonathan Hartley <tartley at tartley.com 
> > <mailto:tartley at tartley.com>> 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 <mailto:tartley at tartley.com>     http://tartley.com
> >     Made out of meat.+1 507-513-1101 <tel:%28507%29%20513-1101>         twitter/skype: tartley
> >
> >     _______________________________________________
> >     python-uk mailing list
> >     python-uk at python.org <mailto:python-uk at python.org>
> >     https://mail.python.org/mailman/listinfo/python-uk
> >
> >
> >
> > _______________________________________________
> > python-uk mailing list
> > python-uk at python.org
> > https://mail.python.org/mailman/listinfo/python-uk
> 
> -- 
> Jonathan Hartley    tartley at tartley.com    http://tartley.com
> Made out of meat.   +1 507-513-1101        twitter/skype: tartley
> 
> _______________________________________________
> python-uk mailing list
> python-uk at python.org
> https://mail.python.org/mailman/listinfo/python-uk


-- 
  Simon
  simon at fastmail.to