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