Page 1 of 1

Calculating the runtime of a function

#1 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • 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  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 161
  • View blog
  • Posts: 247
  • 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  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • 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