[python-uk] A stack with better performance than using a list
tartley at tartley.com
Thu Jun 8 11:09:12 EDT 2017
I wondered about that too, but decided (without measuring) that it is no
better. A deque allows us to append and pop elements from both ends, but
the question didn't require that, it only needed from one end, which a
list provides at O(1).
On 6/8/2017 03:30, Simon Hayward wrote:
> Rather than using a list, aren't deques more appropriate as a data
> structure for stack like behaviour.
> On Wed, 7 Jun 2017, at 19:33, Jonathan Hartley wrote:
>> 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
>>> 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?
>>> 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):
>>> 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)
>>> args = tokens[1:]
>>> def main(lines):
>>> stack = Stack()
>>> for line in lines:
>>> (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 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>
>>> python-uk mailing list
>>> python-uk at python.org
>> Jonathan Hartley tartley at tartley.com http://tartley.com
>> Made out of meat. +1 507-513-1101 twitter/skype: tartley
>> python-uk mailing list
>> python-uk at python.org
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...
More information about the python-uk