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

[Tom Wright]

Algorithms questions are always fun. Quick time to answer before other
people!

You might be hitting problems with the "amortized part" if their code
didn't run for large enough n or used dumb special cases or bounds. They
may have (inadvertantly?) meant "realtime constant" (python lists
occasionally taking O(n) for a single insert, with the possibility of
patterns of push and pop that are O(n) on average if your list frees up
memory in a timely fashion).

The structure they may well have been after is a (singly) linked list...
although you appear to be randomly accessing your stack. To my knowledge
there is no built in linked list in the stdlib but it's not exactly hard to
write one. I would be unsurprised if other languages used a link list for
their abstract stack (or a linked list of arrays)

Fun fact of the day: closed over variables are internally stored in a
linked list (last time looked).

Enthusiastically,

Uncle Tom


On 7 Jun 2017 6:50 p.m., "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/dbe2f904/attachment-0001.html>