[python-uk] A stack with better performance than using a list
Jonathan Hartley
tartley at tartley.com
Wed Jun 7 13:50:40 EDT 2017
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 twitter/skype: tartley
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-uk/attachments/20170607/3691f248/attachment.html>
More information about the python-uk
mailing list