Measuring time every n iterations in merge sort-CodePudding

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?

CodePudding user response：

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:
        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)

CodePudding user response：

We can use a decorator.

Decorator insures conditional timing is checked on every function call.

Code

from time import time
  
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
        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

Test

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

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