title: Python performance: iteration and operations on nested lists
body: <p><strong>Problem</strong>  Hey folks.  I'm looking for some advice on python performance.  Some background on my problem:</p>
  
  <p>Given: </p>
  
  <ol>
  <li>A <code>(x,y)</code> mesh of nodes each with a value <code>(0...255)</code> starting at 0</li>
  <li>A list of <code>N</code> input coordinates each at a specified location within the range <code>(0...x, 0...y)</code></li>
  <li>A value <code>Z</code> that defines the "neighborhood" in count of nodes </li>
  </ol>
  
  <p>Increment the value of the node at the input coordinate and the node's neighbors.   Neighbors beyond the mesh edge are ignored.  (No wrapping)</p>
  
  <p><em>BASE CASE:</em> A mesh of size <code>1024x1024</code> nodes, with <code>400</code> input coordinates and a range <code>Z</code> of <code>75</code> nodes.</p>
  
  <p>Processing should be <code>O(x*y*Z*N)</code>.  I expect x, y and Z to remain roughly around the values in the base case, but the number of input coordinates N could increase up to 100,000.  <strong>My goal</strong> is to minimize processing time. </p>
  
  <p><strong>Current results</strong> Between my start and the comments below, we've got several implementations.</p>
  
  <p>Running speed on my 2.26 GHz Intel Core 2 Duo with Python 2.6.1:</p>
  
  <pre><code>  f1: 2.819s
    f2: 1.567s
    f3: 1.593s
     f: 1.579s
   f3b: 1.526s
    f4: 0.978s
  </code></pre>
  
  <p><code>f1</code> is the initial naive implementation:  three nested <code>for</code> loops.
  <code>f2</code> is replaces the inner <code>for</code> loop with a list comprehension.
  <code>f3</code> is based on Andrei's suggestion in the comments and replaces the outer <code>for</code> with <code>map()</code>
  <code>f</code> is Chris's suggestion in the answers below
  <code>f3b</code> is kriss's take on <code>f3</code>
  <code>f4</code> is Alex's contribution. </p>
  
  <p>Code is included below for your perusal.  </p>
  
  <p><strong>Question</strong> How can I further reduce the processing time?  I'd prefer sub-1.0s for the test parameters. </p>
  
  <p><strong>Please,</strong> keep the recommendations to native Python.  I know I can move to a third-party package such as <a href="http://numpy.scipy.org/" rel="nofollow noreferrer">numpy</a>, but I'm trying to avoid <em>any</em> third party packages.   Also, I've generated random input coordinates, and simplified the definition of the node value updates to keep our discussion simple.  The specifics have to change slightly and are outside the scope of my question.  </p>
  
  <p>thanks much!</p>
  
  <p><hr>
  <strong><code>f1</code> is the initial naive implementation:  three nested <code>for</code> loops.</strong></p>
  
  <pre><code>def f1(x,y,n,z):
      rows = [[0]*x for i in xrange(y)]
  
      for i in range(n):
          inputX, inputY = (int(x*random.random()), int(y*random.random()))
          topleft = (inputX - z, inputY - z)
          for i in xrange(max(0, topleft[0]), min(topleft[0]+(z*2), x)):
              for j in xrange(max(0, topleft[1]), min(topleft[1]+(z*2), y)):
                  if rows[i][j] &lt;= 255: rows[i][j] += 1
  </code></pre>
  
  <p><strong><code>f2</code> is replaces the inner <code>for</code> loop with a list comprehension.</strong></p>
  
  <pre><code>def f2(x,y,n,z):
      rows = [[0]*x for i in xrange(y)]
  
      for i in range(n):
          inputX, inputY = (int(x*random.random()), int(y*random.random()))
          topleft = (inputX - z, inputY - z)
          for i in xrange(max(0, topleft[0]), min(topleft[0]+(z*2), x)):
              l = max(0, topleft[1])
              r = min(topleft[1]+(z*2), y)
              rows[i][l:r] = [j+(j&lt;255) for j in rows[i][l:r]]
  </code></pre>
  
  <p><strong>UPDATE:</strong> <code>f3</code> is based on <a href="https://stackoverflow.com/users/124831/andrei-tanasescu">Andrei</a>'s suggestion in the comments and replaces the outer <code>for</code> with <code>map()</code>.  My first hack at this requires several out-of-local-scope lookups, specifically <a href="http://www.python.org/doc/essays/list2str.html" rel="nofollow noreferrer">recommended against</a> by Guido: <em>local variable lookups are much faster than global or built-in variable lookups</em>   I hardcoded all but the reference to the main data structure itself to minimize that overhead. </p>
  
  <pre><code>rows = [[0]*x for i in xrange(y)]
  
  def f3(x,y,n,z):
      inputs = [(int(x*random.random()), int(y*random.random())) for i in range(n)]
      rows = map(g, inputs)
  
  def g(input):
      inputX, inputY = input
      topleft = (inputX - 75, inputY - 75)
      for i in xrange(max(0, topleft[0]), min(topleft[0]+(75*2), 1024)):
          l = max(0, topleft[1])
          r = min(topleft[1]+(75*2), 1024)
          rows[i][l:r] = [j+(j&lt;255) for j in rows[i][l:r]]
  </code></pre>
  
  <p><strong>UPDATE3:</strong> <a href="https://stackoverflow.com/users/81179/christophed">ChristopeD</a> also pointed out a couple improvements. </p>
  
  <pre><code>def f(x,y,n,z):
      rows = [[0] * y for i in xrange(x)]
      rn = random.random
      for i in xrange(n):
          topleft = (int(x*rn()) - z, int(y*rn()) - z)
          l = max(0, topleft[1])
          r = min(topleft[1]+(z*2), y)
          for u in xrange(max(0, topleft[0]), min(topleft[0]+(z*2), x)):
              rows[u][l:r] = [j+(j&lt;255) for j in rows[u][l:r]]
  </code></pre>
  
  <p><strong>UPDATE4:</strong> <a href="https://stackoverflow.com/users/168465/kriss">kriss</a> added a few improvements to <code>f3</code>, replacing min/max with the new ternary operator syntax. </p>
  
  <pre><code>def f3b(x,y,n,z):
      rn = random.random    
      rows = [g1(x, y, z) for x, y in [(int(x*rn()), int(y*rn())) for i in xrange(n)]]
  
  def g1(x, y, z):
      l = y - z if y - z &gt; 0 else 0
      r = y + z if y + z &lt; 1024 else 1024
      for i in xrange(x - z if x - z &gt; 0 else 0, x + z if x + z &lt; 1024 else 1024 ):
          rows[i][l:r] = [j+(j&lt;255) for j in rows[i][l:r]]
  </code></pre>
  
  <p><strong>UPDATE5:</strong> <a href="https://stackoverflow.com/users/95810/alex-martelli">Alex</a> weighed in with his substantive revision, adding a separate <code>map()</code> operation to cap the values at 255 and removing all non-local-scope lookups.  The perf differences are non-trivial. </p>
  
  <pre><code>def f4(x,y,n,z):
      rows = [[0]*y for i in range(x)]
      rr = random.randrange
      inc = (1).__add__
      sat = (0xff).__and__
  
      for i in range(n):
          inputX, inputY = rr(x), rr(y)
          b = max(0, inputX - z)
          t = min(inputX + z, x)
          l = max(0, inputY - z)
          r = min(inputY + z, y)
          for i in range(b, t):
              rows[i][l:r] = map(inc, rows[i][l:r])
      for i in range(x):
        rows[i] = map(sat, rows[i])
  </code></pre>
  
  <p>Also, since we all seem to be hacking around with variations, here's my test harness to compare speeds: <em>(improved by ChristopheD)</em></p>
  
  <pre><code>def timing(f,x,y,z,n):
      fn = "%s(%d,%d,%d,%d)" % (f.__name__, x, y, z, n)
      ctx = "from __main__ import %s" % f.__name__ 
      results = timeit.Timer(fn, ctx).timeit(10)
      return "%4.4s: %.3f" % (f.__name__, results / 10.0)
  
  if __name__ == "__main__":
      print timing(f, 1024, 1024, 400, 75)
      #add more here.
  </code></pre>