Problem

For pedagogical purposes, I would like to count how many times a given line is executed in a given function without modifying or decorating it. For instance, for the function:

def binary_search(seq, x):
    (a, b) = (0, len(seq) - 1)
    while a <= b:
        m = (a + b) / 2
        if x < seq[m]:
            b = m - 1
        elif x > seq[m]:
            a = m + 1
        else:
            return m

I would just write something like this:

print count_exec(binary_search, range(100), 44, line_number = 4) 

... or even like that:

print count_exec(binary_search(range(100), 44), line = "m = (a + b) / 2")

... 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:

Non solutions

My current solution consists in adding a function attribute:

def binary_search(seq, x):
    binary_search.count = 0 # <------------------ added
    (a, b) = (0, len(seq) - 1)
    while a <= b:
        binary_search.count += 1 # <------------- added
        m = (a + b) / 2
        if x < seq[m]:
            b = m - 1
        elif x > seq[m]:
            a = m + 1
        else:
            return m

binary_search(range(100), 44)
print binary_search.count

I guess I could create a decorated function count_this_line:

def binary_search(seq, x):
    (a, b) = (0, len(seq) - 1)
    while a <= b:
        count_this_line() # <-------------------- added
        m = (a + b) / 2
        ...

May be it is possible to decorate the function binary_search itself, but for me this counts as modifying it.

Ideas

• The standard library ast can retrieve the abstract syntax tree of any given script, and even execute it.
• I have little experience in using a Python profiler. It seems quite heavy handed for my needs. Could it be the way to go?

You can use the line_profiler module to do this (see docs). Note that I had to get a 3.x compatible version from a forked repo - not sure if it's merged yet.

For example. I put your binary search function in a file and then added this:

prof = profile(binary_search)
prof(range(100), 44)

This is the same thing as a @profile decorator as mentioned in the docs, but you don't have to modify the original code. I ran

kernprof.py -l binsearch.py
python -m line_profiler binsearch.py.lprof

And out popped this:

Function: binary_search at line 1
Total time: 4.1e-05 s

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     1                                           def binary_search(seq, x):
     2         1            6      6.0     14.6      (a, b) = (0, len(seq) - 1)
     3         7            8      1.1     19.5      while a <= b:
     4         7            7      1.0     17.1          m = (a + b) // 2
     5         7            8      1.1     19.5          if x < seq[m]:
     6         2            2      1.0      4.9              b = m - 1
     7         5            5      1.0     12.2          elif x > seq[m]:
     8         4            4      1.0      9.8              a = m + 1
     9                                                   else:
    10         1            1      1.0      2.4              return m

"Hits" is the number you're looking for. As a bonus you get timing information too, though that would be more accurate with many executions.