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

[Jonathan Hartley]

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

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