Measuring time every n iterations in merge sort

Question

I need to get measurements every 500 iterations in merge sorting algorithm. I've been trying to make it using Python's time module but it doesn't work well.

import random
import time

start_time = time.time()
count = [1]


def mergesort(A):
    if len(A) > 1:
        m = len(A)//2
        l = A[:m]
        r = A[m:]
        mergesort(l)
        mergesort(r)
        i = j = k = 0
        count.append(1)

        while i < len(l) and j < len(r):
            if l[i] < r[j]:
                A[k] = l[i]
                i += 1
            else:
                A[k] = r[j]
                j += 1
            k += 1

        while i < len(l):
            A[k] = l[i]
            i += 1
            k += 1

        while j < len(r):
            A[k] = r[j]
            j += 1
            k += 1

    if sum(count) >= 500 and sum(count) % 500 == 0:
        print(sum(count))
        print(time.time() - start_time)


A = random.sample(range(0, 99999), 11000)
mergesort(A)
print(A)

Instead, it prints the time sometimes multiple times and some skips. What could I do to make it actually work?

user_3066077 · Answer

We can use a decorator.

Decorator insures conditional timing is checked on every function call.

Online Version of running code

Code

from time import time
import random

def timer_func(func):
  '''
    Decorator to show the times called and cumulative 
    elapsed time each 500 iterations
  
  '''
  start_time = time()
  cnt = 0
  def wrap_func(*args, **kwargs):
      nonlocal cnt
      result = func(*args, **kwargs)
      cnt += 1
      if cnt % 500 == 0:
          print(f'Function {func.__name__!r}:: Iter: {cnt} Elapsed time: {time() - start_time:.4f}')
      return result
  return wrap_func

@timer_func
def mergesort(A):
    if len(A) > 1:
        m = len(A)//2
        l = A[:m]
        r = A[m:]
        mergesort(l)
        mergesort(r)
        i = j = k = 0

        while i < len(l) and j < len(r):
            if l[i] < r[j]:
                A[k] = l[i]
                i += 1
            else:
                A[k] = r[j]
                j += 1
            k += 1

        while i < len(l):
            A[k] = l[i]
            i += 1
            k += 1

        while j < len(r):
            A[k] = r[j]
            j += 1
            k += 1

# Test
A = random.sample(range(0, 99999), 11000)
mergesort(A)

Output

Function 'mergesort':: Iter: 500 Elapsed time: 0.0120
Function 'mergesort':: Iter: 1000 Elapsed time: 0.0140
Function 'mergesort':: Iter: 1500 Elapsed time: 0.0160
Function 'mergesort':: Iter: 2000 Elapsed time: 0.0170
Function 'mergesort':: Iter: 2500 Elapsed time: 0.0190
Function 'mergesort':: Iter: 3000 Elapsed time: 0.0210
Function 'mergesort':: Iter: 3500 Elapsed time: 0.0230
Function 'mergesort':: Iter: 4000 Elapsed time: 0.0240
Function 'mergesort':: Iter: 4500 Elapsed time: 0.0260
Function 'mergesort':: Iter: 5000 Elapsed time: 0.0280
Function 'mergesort':: Iter: 5500 Elapsed time: 0.0320
Function 'mergesort':: Iter: 6000 Elapsed time: 0.0330
Function 'mergesort':: Iter: 6500 Elapsed time: 0.0340
Function 'mergesort':: Iter: 7000 Elapsed time: 0.0360
Function 'mergesort':: Iter: 7500 Elapsed time: 0.0380
Function 'mergesort':: Iter: 8000 Elapsed time: 0.0400
Function 'mergesort':: Iter: 8500 Elapsed time: 0.0430
Function 'mergesort':: Iter: 9000 Elapsed time: 0.0440
Function 'mergesort':: Iter: 9500 Elapsed time: 0.0460
Function 'mergesort':: Iter: 10000 Elapsed time: 0.0470
Function 'mergesort':: Iter: 10500 Elapsed time: 0.0490
Function 'mergesort':: Iter: 11000 Elapsed time: 0.0560
Function 'mergesort':: Iter: 11500 Elapsed time: 0.0580
Function 'mergesort':: Iter: 12000 Elapsed time: 0.0590
Function 'mergesort':: Iter: 12500 Elapsed time: 0.0610
Function 'mergesort':: Iter: 13000 Elapsed time: 0.0620
Function 'mergesort':: Iter: 13500 Elapsed time: 0.0640
Function 'mergesort':: Iter: 14000 Elapsed time: 0.0670
Function 'mergesort':: Iter: 14500 Elapsed time: 0.0680
Function 'mergesort':: Iter: 15000 Elapsed time: 0.0700
Function 'mergesort':: Iter: 15500 Elapsed time: 0.0720
Function 'mergesort':: Iter: 16000 Elapsed time: 0.0730
Function 'mergesort':: Iter: 16500 Elapsed time: 0.0770
Function 'mergesort':: Iter: 17000 Elapsed time: 0.0790
Function 'mergesort':: Iter: 17500 Elapsed time: 0.0800
Function 'mergesort':: Iter: 18000 Elapsed time: 0.0820
Function 'mergesort':: Iter: 18500 Elapsed time: 0.0830
Function 'mergesort':: Iter: 19000 Elapsed time: 0.0850
Function 'mergesort':: Iter: 19500 Elapsed time: 0.0870
Function 'mergesort':: Iter: 20000 Elapsed time: 0.0890
Function 'mergesort':: Iter: 20500 Elapsed time: 0.0900
Function 'mergesort':: Iter: 21000 Elapsed time: 0.0920
Function 'mergesort':: Iter: 21500 Elapsed time: 0.0940

user_17829451 · Answer

Since the code incrementing the counter is inside the recursive portion of the function it isn't being applied uniformly.

Try moving the timing portion to the top of the function call. Including the counting portion. It might with the calls being made more consistently.

import random
import time

start_time = time.time()
count = [1]

def mergesort(A):
    count[0] += 1
    # if not count[0] % 500:   <- simplified conditional
    if sum(count) >= 500 and sum(count) % 500 == 0:   # <- original
        print(count[0])
        print(time.time() - start_time)
    if len(A) > 1:
        m = len(A)//2
        l = A[:m]
        r = A[m:]
        mergesort(l)
        mergesort(r)
        i = j = k = 0
        while i < len(l) and j < len(r):
            if l[i] < r[j]:
                A[k] = l[i]
                i += 1
            else:
                A[k] = r[j]
                j += 1
            k += 1
        while i < len(l):
            A[k] = l[i]
            i += 1
            k += 1
        while j < len(r):
            A[k] = r[j]
            j += 1
            k += 1


A = random.sample(range(0, 99999), 11000)
mergesort(A)
print(A)

When I run the above code my output is:

500
0.004991292953491211
1000
0.005989789962768555
1500
0.005989789962768555
2000
0.0069882869720458984
2500
0.00798797607421875
3000
0.008810281753540039
3500
0.008986473083496094
4000
0.01007533073425293
4500
0.010997295379638672
5000
0.010997295379638672
5500
0.01198720932006836
6000
0.013178110122680664
6500
0.013999700546264648
7000
0.014998435974121094
7500
0.014998435974121094
8000
0.015987157821655273
8500
0.01720261573791504
9000
0.01720261573791504
9500
0.01798725128173828
10000
0.018998384475708008
10500
0.019986867904663086
11000
0.020987272262573242
11500
0.023231029510498047
12000
0.023231029510498047
12500
0.023987293243408203
13000
0.024986743927001953
13500
0.024986743927001953
14000
0.026865005493164062
14500
0.027907133102416992
15000
0.02800726890563965
15500
0.028907060623168945
16000
0.029872655868530273
16500
0.030872344970703125
17000
0.0328829288482666
17500
0.0328829288482666
18000
0.03387165069580078
18500
0.03387165069580078
19000
0.03486943244934082
19500
0.035881996154785156
20000
0.035881996154785156
20500
0.036870718002319336
21000
0.03787088394165039
21500
0.03787088394165039
22000
0.038871049880981445
[5, 9, 10, 13, 27, 33, 42, 46, 52, 59, 72, 83, ...]

Measuring time every n iterations in merge sort

2 Answers