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

Jonathan Hartley 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.
>
> https://docs.python.org/3.6/library/collections.html#collections.deque
>
>
> Regards
> Simon
>
>
> On Wed, 7 Jun 2017, at 19:33, Jonathan Hartley wrote:
>> Hey.
>>
>> 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
>>> 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
>>> <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):
>>>              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 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>
>>>      https://mail.python.org/mailman/listinfo/python-uk
>>>
>>>
>>>
>>> _______________________________________________
>>> python-uk mailing list
>>> python-uk at python.org
>>> https://mail.python.org/mailman/listinfo/python-uk
>> -- 
>> 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
>> https://mail.python.org/mailman/listinfo/python-uk
>

-- 
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/20170608/e6edda36/attachment-0001.html>


More information about the python-uk mailing list