Re: A stack with better performance than using a list
Jonathan Hartley <[email protected]>
| Newsgroups | gmane.comp.python.org.uk |
|---|---|
| Message-ID | <[email protected]> |
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 <[email protected] >>> <mailto:[email protected]>> 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 [email protected] <mailto:[email protected]> http://tartley.com >>> Made out of meat.+1 507-513-1101 <tel:%28507%29%20513-1101> twitter/skype: tartley >>> >>> _______________________________________________ >>> python-uk mailing list >>> [email protected] <mailto:[email protected]> >>> https://mail.python.org/mailman/listinfo/python-uk >>> >>> >>> >>> _______________________________________________ >>> python-uk mailing list >>> [email protected] >>> https://mail.python.org/mailman/listinfo/python-uk >> -- >> Jonathan Hartley [email protected] http://tartley.com >> Made out of meat. +1 507-513-1101 twitter/skype: tartley >> >> _______________________________________________ >> python-uk mailing list >> [email protected] >> https://mail.python.org/mailman/listinfo/python-uk > -- Jonathan Hartley [email protected] http://tartley.com Made out of meat. +1 507-513-1101 twitter/skype: tartley _______________________________________________ python-uk mailing list [email protected] https://mail.python.org/mailman/listinfo/python-uk