On 06/13/2017 09:04 AM, Mark Lawrence via python-uk wrote:
On 07/06/2017 18:50, Jonathan Hartley 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 hartleytart...@tartley.com http://tartley.com
Made out of meat. +1 507-513-1101 twitter/skype: tartley
Any objections to me putting this thread up on the main Python mailing
list and reddit as it seems rather interesting?
I'd rather not if I get any say in that, because I agreed in the T&C of
the coding challenge that I wouldn't discuss the problem or solutions
with others, and I don't want to annoy them right now. How about in a
month? :-)
--
Jonathan Hartley tart...@tartley.com http://tartley.com
Made out of meat. +1 507-513-1101 twitter/skype: tartley
_______________________________________________
python-uk mailing list
python-uk@python.org
https://mail.python.org/mailman/listinfo/python-uk
