title: Python: counting how many times a given line is executed
body: <h1>Problem</h1>
  
  <p>For pedagogical purposes, I would like to count how many times a given line is executed in a given function <strong>without modifying or decorating it</strong>. For instance, for the function:</p>
  
  <pre><code>def binary_search(seq, x):
      (a, b) = (0, len(seq) - 1)
      while a &lt;= b:
          m = (a + b) / 2
          if x &lt; seq[m]:
              b = m - 1
          elif x &gt; seq[m]:
              a = m + 1
          else:
              return m
  </code></pre>
  
  <p>I would just write something like this:</p>
  
  <pre><code>print count_exec(binary_search, range(100), 44, line_number = 4) 
  </code></pre>
  
  <p>... or even like that:</p>
  
  <pre><code>print count_exec(binary_search(range(100), 44), line = "m = (a + b) / 2")
  </code></pre>
  
  <p>... which both should print the number of times the 4th line is executed (which is 7). The ultimate goal is to provide an empirical approach to the complexity of any function:</p>
  
  <p><a href="https://i.stack.imgur.com/sZ0GH.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/sZ0GH.png" alt="Complexity of binary search"></a></p>
  
  <h1>Non solutions</h1>
  
  <p>My current solution consists in adding a function attribute:</p>
  
  <pre><code>def binary_search(seq, x):
      binary_search.count = 0 # &lt;------------------ added
      (a, b) = (0, len(seq) - 1)
      while a &lt;= b:
          binary_search.count += 1 # &lt;------------- added
          m = (a + b) / 2
          if x &lt; seq[m]:
              b = m - 1
          elif x &gt; seq[m]:
              a = m + 1
          else:
              return m
  
  binary_search(range(100), 44)
  print binary_search.count
  </code></pre>
  
  <p>I guess I could create a decorated function <code>count_this_line</code>:</p>
  
  <pre><code>def binary_search(seq, x):
      (a, b) = (0, len(seq) - 1)
      while a &lt;= b:
          count_this_line() # &lt;-------------------- added
          m = (a + b) / 2
          ...
  </code></pre>
  
  <p>May be it is possible to decorate the function <code>binary_search</code> itself, but for me this counts as modifying it.</p>
  
  <h1>Ideas</h1>
  
  <ul>
  <li>The standard library <a href="https://docs.python.org/2/library/ast.html" rel="nofollow noreferrer">ast</a> can retrieve the abstract syntax tree of any given script, and even execute it.</li>
  <li>I have little experience in using a Python profiler. It seems quite heavy handed for my needs. Could it be the way to go?</li>
  </ul>