Page 1 of 1

## Calculating the runtime of a function

### #1 atraub

• Pythoneer

Reputation: 734
• Posts: 1,890
• Joined: 23-December 08

Posted 05 May 2012 - 07:52 PM

I see this question come up a lot in the forums! Ho do I determine how long it takes for a function to execute? Maybe you're curious, maybe you're trying to compare the efficiency of algorithms, maybe you want to see how well a builtin function is implemented.

In python, this is really easy.

```import time

startTime = time.time()

#run code here

elapsedTime = time.time() - startTime

```

There you have it, a simple way to check the time it took for a function to run. If this is for testing purposes, I usually will run it about 5 or 10 times and take the average.

This is pretty cool, but we can even generalize it a bit. For the purposes of this tutorial, I created this function
```__author__ = "atraub"
__date__= "5/5/2012"

import time

def calculateRunTime(function, *args):
"""run a function and return the run time and the result of the function
if the function requires arguments, those can be passed in too"""
startTime = time.time()
result = function(*args)
return time.time() - startTime, result

```

This is a generalized function that will handle the time for ANY function, even if that function requires parameters! It returns a tuple containing the elapsed time and the result of the function.

For testing it, I'm going to use a quicksort and a bubblesort, both were written by KYA, a well respected guy here at DIC.

Here's his quicksort:
```# Quick Sort
# KYA
# 7-20-08

def partition(theList, start, end):
pivot = theList[end]                     # place the pivot at the end
bottom = start-1                         # begin "outside"
top = end                                # place other side for partitioning

done = 0
while not done:                             # begin
while not done:
bottom = bottom + 1

if bottom == top:                   # has we reached the end?
done = 1                        # if so, exit!
break
if theList[bottom] > pivot:         # move values '>' "above"
theList[top] = theList[bottom]
break

while not done:
top = top-1

if top == bottom:                   # if end is reached, exit!
done = 1
break
if theList[top] < pivot:            # do the opposite of the above
theList[bottom] = theList[top]  # '<' are moved "below"
break

theList[top] = pivot
return top

def quicksort(theList, start, end):
if start < end:                             # verifies the list is not empty
split = partition(theList, start, end)      # partition the sublist
quicksort(theList, start, split-1)          # sort both halves.
quicksort(theList, split+1, end)            # recursion
else:
return

```

and here's his bubblesort
```# Bubble Sort
# KYA
# 7-20-08
def bubbleSort(theList, max):
for n in range(0,max): #upper limit varies based on size of the list
temp = 0
for i in range(1, max): #keep this for bounds purposes
temp = theList[i]
if theList[i] < theList[i-1]:
theList[i] = theList[i-1]
theList[i-1] = temp

```

Keep in mind KYA wrote these sorts while he was new to Python, and he really did all of us a favor in creating them because he was contributing to a topic that was grossly lacking in content. So, if you have any criticisms about the sorts, keep them to yourself.

alright, let's do this!

```
def main(count=10, minimumValue=0, maximumValue=100, sampleSize=1200):
quickTimes = []
bubbleTimes = []
for i in range(count):
x = [random.randint(minimumValue,maximumValue) for i in range(sampleSize)]
y = list(x)

quickTimes.append(calculateRunTime(bubbleSort,x,len(x))[0])
bubbleTimes.append(calculateRunTime(quicksort,y,0,len(y)-1)[0])

print("Average BubbleSort time: " + str(sum(bubbleTimes)/len(bubbleTimes)))
print("Average  QuickSort time: " + str(sum(quickTimes)/len(quickTimes)))

```

This function creates two lists for containing run times. It creates two identical lists of sample input. it then runs bubbleSort and quickSort using the lists. notice how I passed 3 arguments into calculateRunTime for bubble sort and 4 arguments for quicksort. When that was done, I calculated the average run time and communicated it back to the user. Which one will run faster? Will the inefficient bubblesort lose? Or will the resource heavy, recursive quicksort fall short? On my system, this was my result:
```Average BubbleSort time: 0.0047999382019
Average  QuickSort time: 0.400500059128

```

Try it for yourself, or create your own functions to compare side by side!

Is This A Good Question/Topic? 0

## Replies To: Calculating the runtime of a function

### #2 Nallo

• D.I.C Head

Reputation: 159
• Posts: 241
• Joined: 19-July 09

Posted 30 July 2012 - 11:48 AM

Ok as an introduction to runtime testing. But there are 2 Problems with timing this way:

1. You forgot to mention, that the measurement depends on system activity. Whatever your operation system or other programs do end up in your measurement. No help here, as python obviously can't control the underlying system. But a mention of that problem would have been nice.

2. Handing out your own calculate_run_time function makes the assumption, that the python interperter behaves nicely while measuring. But what if during some part of your measurement pythons own garbage collector feels like right now it's time to clean the floor (i.e. delete unused objects)? You get grossly wrong results there. Better use Pythons own timeit module. That gets rid of the second problem.
Was This Post Helpful? 0

### #3 atraub

• Pythoneer

Reputation: 734
• Posts: 1,890
• Joined: 23-December 08

Posted 02 August 2012 - 03:03 PM

As for your first gripe, that's valid. I suppose the I figured that by making all my examples run multiple times and averaging the runtimes, that would be implicitly understood, but I probably should have explicitly explained that somewhere.

As for your second gripe, I had never actually heard of the timeit module. Pretty cool stuff, I'll test it out some when I have time. I noticed that the module does say that it's for small code snippets, so I don't know what that will mean for larger functions.
Was This Post Helpful? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }