<div dir="ltr">Do you have any more context? <div>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?<div><br></div><div>I'm assuming that lines look like this:</div><div><br></div><div>push 1</div><div>push 2</div><div>add_to_first_n 2 10</div><div>pop</div><div>pop</div><div><br></div><div>with all arguments as integers, and the final value being returned from main()?</div><div>How did you convert from string inputs to numeric values?</div><div>How did you manage return values?</div><div><br></div><div>:D</div></div></div><br><div class="gmail_quote"><div dir="ltr">On Wed, Jun 7, 2017 at 6:51 PM Jonathan Hartley <<a href="mailto:tartley@tartley.com">tartley@tartley.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<p>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.</p>
<p> From memory, I think I had something pretty standard:</p>
<p><font face="Consolas" size="-2"><font color="#3333ff">class </font>Stack:<br>
<br>
<font color="#3333ff">def </font>__init__(self):<br>
self.storage = []<br>
<br>
<font color="#3333ff">def </font>push(arg):<br>
self.storage.append(arg)<br>
<br>
<font color="#3333ff">def </font>pop():<br>
<font color="#3333ff">return </font>self.storage.pop()
if self.storage else None<br>
<br>
<font color="#3333ff">def </font>add_to_first_n(n,
amount):<br>
<font color="#3333ff">for </font>n <font color="#3333ff">in </font><font color="#009900">range</font>(n):<br>
self.storage[n] += amount<br>
<br>
<font color="#3333ff">def </font>dispatch(self, line)<br>
tokens = line.split()<br>
method = <font color="#009900">getattr</font>(self,
tokens[<font color="#993399">0</font>])<br>
args = tokens[<font color="#993399">1</font>:]<br>
method(*args)<br>
<br>
<font color="#3333ff">def </font>main(lines):<br>
stack = Stack()<br>
<font color="#3333ff">for </font>line <font color="#3333ff">in </font>lines:<br>
stack.dispatch(line)</font><br>
</p>
<p><br>
</p>
<p>(will that formatting survive? Apologies if not)<br>
</p>
<p>Subsequent experiments have confirmed that appending to and
popping from the end of lists are O(1), amortized.</p>
So why is my solution too slow?<br>
<br>
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.)<br>
<br>
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?<br>
<br>
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.<br>
<br>
Thoughts welcome,<br>
<br>
Jonathan<br>
<pre class="m_-7825971627947445388moz-signature" cols="72">--
Jonathan Hartley <a class="m_-7825971627947445388moz-txt-link-abbreviated" href="mailto:tartley@tartley.com" target="_blank">tartley@tartley.com</a> <a class="m_-7825971627947445388moz-txt-link-freetext" href="http://tartley.com" target="_blank">http://tartley.com</a>
Made out of meat. <a href="tel:(507)%20513-1101" value="+15075131101" target="_blank">+1 507-513-1101</a> twitter/skype: tartley
</pre>
</div>
_______________________________________________<br>
python-uk mailing list<br>
<a href="mailto:python-uk@python.org" target="_blank">python-uk@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/python-uk" rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/python-uk</a><br>
</blockquote></div>