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

[Stestagg]

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> 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 Hartley    tartley at tartley.com    http://tartley.com
> Made out of meat.   +1 507-513-1101 <(507)%20513-1101>        twitter/skype: tartley
>
>
> _______________________________________________
> python-uk mailing list
> python-uk at python.org
> https://mail.python.org/mailman/listinfo/python-uk
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-uk/attachments/20170607/2cf68f56/attachment.html>