[airmalley]

So I am trying to write a function that creates a random list of 30000 numbers and tests the speed between insertion sort and the built in sort function in python, timsort. I want the timing results to be put in a text file. I am having problems with the timeit function or just timing in general. Here is what I have so far.

import time
import random
import timeit

A = [ random.randint(1,999) for i in xrange(30000) ]

def InsertionSort(A):
    for i in range(1,len(A),1):
        target = A[i]
        j = i - 1
        while j >=0 and target < A[j]:
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = target
        
    return A

InsertionSort(A)

TimSort = A.sort


writeFile = open("isps.txt", "w")
for item in A:
#Really kind of clueless at this part.

[Simown]

We can help you, but we'd like you to provide an attempt at the timing, which is the function of this program.

Are you confined to using timeit? I like using time.time() for estimating execution time (which timeit uses by default on non-Windows platforms):

import time

start = time.time()
// CODE
// MORE CODE
end = time.time()
timeTaken = end - start

This post has been edited by Simown: 22 November 2011 - 01:48 PM

[airmalley]

I am not confined to timeit, just thought I should try it out. I will try it with time instead and get back to here, thanks

[airmalley]

Ok so this is my first time trying to time something so I am not quite if I have it right. Well actually I know its wrong because its only returning 0.0 for both functions. Here is what I have again.

import time
import random
import timeit

A = [ random.randint(1,999) for i in xrange(30000) ]

start = time.time()
def InsertionSort(A):
    for i in range(1,len(A),1):
        target = A[i]
        j = i - 1
        while j >=0 and target < A[j]:
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = target
        
    return A

end = time.time()

timeTaken = end - start
print timeTaken

start1 = time.time()
def TimSort(A):
    TimSort = A.sort
    return A

end1 = time.time()
timeTaken1 = end1 - start1
print timeTaken1

[Motoma]

The timeit library is pretty straight-forward; you merely pass the command you want to execute as an argument, and it tells you how long it took:

import timeit
import time
t = timeit.timeit('time.sleep(1)', number=10)
print("Took %f seconds, averaging %f seconds per run" % (t, t/10))

Make sure to specify a number, the default is 1000000!

In your code, you will want to re-generate the random list each time around; otherwise you would probably see subsequent sorts finish in no time.

EDIT: BEATEN TO THE PUNCH!

[Simown]

You have defined the functions within time.time() you need to test executing them functions.

def InsertionSort(A):
   ...
   ....

def TimSort(A):
    timSort = sorted(A)
    return timSort

And to test it:

A = [ random.randint(1,999) for i in xrange(30000) ]

start = time.time()
#Executing the function
X = InsertionSort(A)
end = time.time()

print "Insertion sort took", end - start

start = time.time()
#Executing the function on the same input
X = TimSort(A)
end = time.time()

print "Timsort took", end - start

As Motoma pointed out, you want to regenerate (or at least revert) the sorted list if you are going to test it again with timeit, one run through sorts it, and then the subsequent runs won't have a lot to do. To get a better estimate of the time, you probably want to run the sorting methods X times to get a nice average.

Note: I changed your timsort function slightly, if you are going to assign the value of the sort, you want to use sorted()

This post has been edited by Simown: 22 November 2011 - 02:44 PM