<html>
  <head>

    <meta http-equiv="content-type" content="text/html; charset=utf-8">
  </head>
  <body 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="moz-signature" cols="72">-- 
Jonathan Hartley    <a class="moz-txt-link-abbreviated" href="mailto:tartley@tartley.com">tartley@tartley.com</a>    <a class="moz-txt-link-freetext" href="http://tartley.com">http://tartley.com</a>
Made out of meat.   +1 507-513-1101        twitter/skype: tartley

</pre>
  </body>
</html>