<p dir="ltr">I was able to get about a 20% speed up over Steve's solution, on some benchmark data I created, by:</p>
<p dir="ltr">* converting LOAD_GLOBAL to LOAD_FAST for __builtins__<br>
* eliminating the conditional in each loop in favour of a conditional on pop only <br>
* eliminating string comparison for the operation in favour of testing line[1] against byte values</p>
<p dir="ltr">None of these had a significant effect in either direction:</p>
<p dir="ltr">* replacing range objects with counts <br>
* replacing the string.split()/int() calls with a hand-rolled space-separated integer parser in Python.</p>
<p dir="ltr">Oh, in my benchmarking, the print() calls were huge and highly variable... I stubbed them out first.</p>
<br><div class="gmail_quote"><div dir="ltr">On Thu, 8 Jun 2017, 21:39 Stestagg, <<a href="mailto:stestagg@gmail.com">stestagg@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Apologies, In my previous email, I meant 'insert a marker', rather than 'push a marker'</div><br><div class="gmail_quote"><div dir="ltr">On Thu, Jun 8, 2017 at 7:17 PM Stestagg <<a href="mailto:stestagg@gmail.com" target="_blank">stestagg@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I tracked down the challenge on the site, and have a working solution (I won't share for obvious reasons). Basically the timeouts were being caused by 'add_to_first_n' being called in horrible ways in the test cases. <div><br></div><div>Because add_to_first_n alters the bottom of the stack, you can just push a marker onto the stack rather than iterating and mutating each entry, doing this made those test cases pass</div><div><br></div><div>Personally, I think it's not a well-described problem, because it's expecting you to tune the algo to specific shapes of data without allowing any visibility on the data, or a description of what to code for. An algo junkie may jump straight to the optimized version, but a pragmatic developer would, in my opinion, hesitate to do that without any actual evidence that the problem required it.</div><div><br></div><div>Steve</div><div><br></div><div><br><div><br></div><div> </div></div></div><br><div class="gmail_quote"><div dir="ltr">On Thu, Jun 8, 2017 at 5:27 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>Yep, that's a great elimination of the suspicious small
overheads.</p>
<p>line_profiler is beautiful, I'll definitely be adding it to my
toolbox, thanks for that!<br>
</p>
<p>I tried a variant of accumulating the output and printing it all
as a single string, but of course this didn't help, printing is
already buffered.</p></div><div bgcolor="#FFFFFF" text="#000000">
<p> Jonathan<br>
</p></div><div bgcolor="#FFFFFF" text="#000000">
<br>
<div class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994moz-cite-prefix">On 6/8/2017 03:54, Stestagg wrote:<br>
</div>
<blockquote type="cite">
<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_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1">Line #<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>Hits <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>Time<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>Per Hit <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>% Time<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>Line Contents</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1">==============================================================</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>12 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>@profile</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>13 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>def
main(lines):</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>14 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>4<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>4.0<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.0<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>stack = []</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>15 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>2000001 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>949599<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.5 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>11.5<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>for line in lines:</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>16 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>2000000<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1126944<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.6 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>13.7<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>meth = line[:3]<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space"> </span></span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>17 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>2000000 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>974635<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.5 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>11.8<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>if meth == b'pus':</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>18 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1000000<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1002733<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1.0 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>12.2<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>stack.append(int(line[5:]))</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>19 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1000000 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>478756<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.5<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>5.8<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>elif meth == b'pop':</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>20<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>999999 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>597114<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.6<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>7.2<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>stack.pop()</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>21 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>else:</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>22 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>6<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>6.0<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.0<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>parts = line[15:].split()</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>23 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>2<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>2.0<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.0<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>end = len(stack)-1</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>24 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1.0<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.0<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>amount = int(parts[1])</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>25<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>500001 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>241227<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.5<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>2.9<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>for x in range(int(parts[0])):</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>26<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>500000 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>273477<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.5<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>3.3<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>index = end - x</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>27<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>500000 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>309033<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>0.6<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>3.7<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>stack[index] += amount</span></p>
<p class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-p1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-s1"><span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>28 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>2000000<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>2295803<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>1.1 <span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762inbox-inbox-Apple-converted-space">
</span>27.8<span class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_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_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_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_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762m_-1346269059825002404m_-7825971627947445388moz-signature" cols="72">--
Jonathan Hartley <a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762m_-1346269059825002404m_-7825971627947445388moz-txt-link-abbreviated" href="mailto:tartley@tartley.com" target="_blank">tartley@tartley.com</a> <a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_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_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762m_-1346269059825002404mimeAttachmentHeader"></fieldset>
<br>
<pre>_______________________________________________
python-uk mailing list
<a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762m_-1346269059825002404moz-txt-link-abbreviated" href="mailto:python-uk@python.org" target="_blank">python-uk@python.org</a>
<a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_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_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762m_-1346269059825002404moz-signature" cols="72">--
Jonathan Hartley <a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762m_-1346269059825002404moz-txt-link-abbreviated" href="mailto:tartley@tartley.com" target="_blank">tartley@tartley.com</a> <a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994m_5373425284023800762m_-1346269059825002404moz-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>
</div>
<br>
<fieldset class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994mimeAttachmentHeader"></fieldset>
<br>
<pre>_______________________________________________
python-uk mailing list
<a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994moz-txt-link-abbreviated" href="mailto:python-uk@python.org" target="_blank">python-uk@python.org</a>
<a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994moz-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_-7883362109925650851m_-3564840514078781177m_3287686112171487994moz-signature" cols="72">--
Jonathan Hartley <a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994moz-txt-link-abbreviated" href="mailto:tartley@tartley.com" target="_blank">tartley@tartley.com</a> <a class="m_-7883362109925650851m_-3564840514078781177m_3287686112171487994moz-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></blockquote></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>