Calculating average time for sort methods

Question

In my test class Ordena, I'm trying to calculate the average time for the execution of 30 repeats for some sort methods, for example, insertion sort:

@staticmethod
def insertionSort(v):
    for i in range(len(v)-1):
        temp = v[i]
        j = i-1
        while j >=0 and temp < v[j]:
            v[j+1] = v[j]
            j = j-1
        v[j + 1] = temp

My timing and averaging function looks like this:

@staticmethod
def average(x, function, repeat=30):
    total_time = 0
    sequence = Ordena.getList(x)
    print(sequence)
    for n in range(repeat):
        time_start = time.time()
        print(time_start)
        assert function(sequence)
        total_time += time.time()+time_start
        print(total_time)

I'm doing the implementation myself (without using the timeit module) for academic practice.

Now when I call the average function like Ordena.average(x, Ordena.insertionSort), I'm getting the following error:

  File "<input>", line 1, in <module>
  File "C:/Users/sandr/PycharmProjects/Trabalho 3/main.py", line 140, in average
    assert function(sequence)
AssertionError

What am I doing wrong here?

Answer 1

The line assert function(sequence) causes that the sort function is invoked, consuming the time you want to measure, and, after that, checks if the function result is something that evaluates to True (that's what assert is for). Since you are calling it for your sort function (insertionSort) which implicitly returns None, the result will be evaluated to False hence the error. In order to measure how much time a function consumes, you just call it and you'll be fine.

So, by removing assert before function(sequence) the AssertionError will be gone.

But there are still other issues with your approach:

• you include the time for printing the start_time
• you include the time for adding to total_time
• you sorting the sequence with the first call and working on a sorted sequence later
• you don't actually average

Possible approach

Something like this will probably give you better results (class stuff stripped for simplicity):

import random
import time

def getSampleList(x):
    return random.sample(range(x), x)

def insertionSort(v):
    for i in range(len(v)-1):
        temp = v[i]
        j = i-1
        while j >=0 and temp < v[j]:
            v[j+1] = v[j]
            j = j-1
        v[j + 1] = temp

def average(x, function, repeat=30):
    # get the shuffled sample list once
    mastersequence = getSampleList(x)
    # create repeat copies of this sequence
    sequences = [mastersequence[:] for i in range(repeat)]
    time_start = time.time()
    for sequence in sequences:
        function(sequence)
    return (time.time() - time_start)/repeat
        
print(average(100, insertionSort, 10_000))

Refinement

After some helpful comments by Kelly Bundy ^{thanks by the way} , I figured out that the high memory consumption (I already was aware of) isn't the only problem with this approach. An important problem is that its result heavily depends on just one random shuffle. For some algorithms, the sorting speed is closely coupled to how sorted the input is, think for example of Bubblesort on sorted input. So let's look into average2, a variation of average (which is also closer to the function in the question):

def average2(x, function, repeat=30):
    timeConsumption = 0
    for _ in range(repeat):
        sequence = getSampleList(x)
        time_start = time.time()
        function(sequence)
        timeConsumption += time.time() - time_start
    return timeConsumption/repeat

print('avarage:')
for i in range(10):
    print(f"{average(100, insertionSort, 10_000):.7f}")
    
print('avarage2:')
for i in range(10):
    print(f"{average2(100, insertionSort, 10_000):.7f}")

See the results for 10 runs of average and avarage2 (rounded to 7 digits):

avarage:
0.0002911
0.0002815
0.0002785
0.0002695
0.0002932
0.0002778
0.0002640
0.0002979
0.0002990
0.0003177
avarage2:
0.0002880
0.0002880
0.0002842
0.0002874
0.0002864
0.0002891
0.0002860
0.0002921
0.0002893
0.0002873

Here it gets obvious that the variance of the results of the second measurement is lower, so I would trust it more.