<div dir="ltr">I honestly can't see a way to improve this in python. My best solution is:<div><br></div><div><div>def main(lines):</div><div> stack = []</div><div> sa = stack.append</div><div> sp = stack.pop</div><div> si = stack.__getitem__</div><div> for line in lines:</div><div> meth = line[:3] </div><div> if meth == b'pus':</div><div> sa(int(line[5:]))</div><div> elif meth == b'pop':</div><div> sp()</div><div> else:</div><div> parts = line[15:].split()</div><div> end = len(stack)-1</div><div> amount = int(parts[1])</div><div> for x in range(int(parts[0])):</div><div> index = end - x</div><div> stack[index] += amount</div><div> print(stack[-1] if stack else None)</div></div><div><br></div><div>which comes out about 25% faster than your solution.</div><div><br></div><div>One tool that's interesting to use here is: line_profiler: <a href="https://github.com/rkern/line_profiler" target="_blank">https://github.com/rkern/line_profiler</a></div><div><br></div><div>putting a @profile decorator on the above main() call, and running with kernprof produces the following output:</div><div><br></div><div>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1">Line #<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>Hits <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>Time<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>Per Hit <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>% Time<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>Line Contents</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1">==============================================================</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>12 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>@profile</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>13 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>def main(lines):</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>14 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>4<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>4.0<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.0<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>stack = []</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>15 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>2000001 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>949599<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.5 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>11.5<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>for line in lines:</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>16 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>2000000<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1126944<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.6 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>13.7<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>meth = line[:3]<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span></span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>17 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>2000000 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>974635<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.5 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>11.8<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>if meth == b'pus':</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>18 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1000000<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1002733<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1.0 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>12.2<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>stack.append(int(line[5:]))</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>19 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1000000 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>478756<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.5<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>5.8<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>elif meth == b'pop':</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>20<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>999999 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>597114<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.6<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>7.2<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>stack.pop()</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>21 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>else:</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>22 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>6<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>6.0<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.0<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>parts = line[15:].split()</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>23 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>2<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>2.0<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.0<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>end = len(stack)-1</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>24 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1.0<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.0<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>amount = int(parts[1])</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>25<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>500001 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>241227<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.5<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>2.9<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>for x in range(int(parts[0])):</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>26<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>500000 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>273477<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.5<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>3.3<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>index = end - x</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>27<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>500000 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>309033<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>0.6<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>3.7<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>stack[index] += amount</span></p>
<p class="m_5373425284023800762inbox-inbox-p1"><span class="m_5373425284023800762inbox-inbox-s1"><span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>28 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>2000000<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>2295803<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>1.1 <span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>27.8<span class="m_5373425284023800762inbox-inbox-Apple-converted-space"> </span>print(stack[-1])</span></p></div><div><br></div><div>which shows that there's no obvious bottleneck (line by line) here (for my sample data). </div><div><br></div><div>Note the print() overhead dominates the runtime, and that's with me piping the output to /dev/null directly.</div><div><br></div><div>I had a go at using arrays, deques, and numpy arrays in various ways without luck, but we're getting fairly close to the native python statement execution overhead here (hence folding it all into one function).</div><div><br></div><div>My only thoughts would be to see if there were some magic that could be done by offloading the work onto a non-python library somehow.</div><div><br></div><div>Another thing that might help some situations (hence my previous questions) would be to implement the add_to_first_n as a lazy operator (i.e. have a stack of the add_to_first_n values and dynamically add to the results of pop() but that would proabably be much slow in the average case.</div><div><br></div><div>Steve</div><br><div class="gmail_quote"><div dir="ltr">On Wed, Jun 7, 2017 at 7:34 PM Jonathan Hartley <<a href="mailto:tartley@tartley.com" target="_blank">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">
Hey.<br>
<br>
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.<br>
<br>
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.<br>
<br>
I converted to integers inside 'dispatch'. 'args' must have actually
been created with:<br>
<br>
<font face="Consolas" size="-2">args = [int(i) for i in tokens[<font color="#993399">1</font>:]]</font><br>
<br>
Where len(tokens) is never going to be bigger than 3.<br>
<br>
Return values (from 'pop') were unused. <br></div><div bgcolor="#FFFFFF" text="#000000">
<br>
<br>
<div class="m_5373425284023800762m_-1346269059825002404moz-cite-prefix">On 6/7/2017 13:25, Stestagg wrote:<br>
</div>
<blockquote type="cite">
<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" target="_blank">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_5373425284023800762m_-1346269059825002404m_-7825971627947445388moz-signature" cols="72">--
Jonathan Hartley <a class="m_5373425284023800762m_-1346269059825002404m_-7825971627947445388moz-txt-link-abbreviated" href="mailto:tartley@tartley.com" target="_blank">tartley@tartley.com</a> <a class="m_5373425284023800762m_-1346269059825002404m_-7825971627947445388moz-txt-link-freetext" href="http://tartley.com" target="_blank">http://tartley.com</a>
Made out of meat. <a href="tel:%28507%29%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>
<br>
<fieldset class="m_5373425284023800762m_-1346269059825002404mimeAttachmentHeader"></fieldset>
<br>
<pre>_______________________________________________
python-uk mailing list
<a class="m_5373425284023800762m_-1346269059825002404moz-txt-link-abbreviated" href="mailto:python-uk@python.org" target="_blank">python-uk@python.org</a>
<a class="m_5373425284023800762m_-1346269059825002404moz-txt-link-freetext" href="https://mail.python.org/mailman/listinfo/python-uk" target="_blank">https://mail.python.org/mailman/listinfo/python-uk</a>
</pre>
</blockquote>
<br>
<pre class="m_5373425284023800762m_-1346269059825002404moz-signature" cols="72">--
Jonathan Hartley <a class="m_5373425284023800762m_-1346269059825002404moz-txt-link-abbreviated" href="mailto:tartley@tartley.com" target="_blank">tartley@tartley.com</a> <a class="m_5373425284023800762m_-1346269059825002404moz-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></div>