在合并排序中每 n 次迭代测量时间
Measuring time every n iterations in merge sort
我需要在合并排序算法中每 500 次迭代获取一次测量值。我一直在尝试使用 Python 的时间模块来实现它，但效果不佳。
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)
相反，它有时会多次打印时间，有时会跳过。
我该怎么做才能让它真正发挥作用？
由于递增计数器的代码在函数的递归部分内，因此未统一应用。
尝试将计时部分移到函数调用的顶部。包括计数部分。它可能会更一致地进行调用。
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)
当我运行上面的代码时，我的输出是：
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, ...]
我们可以使用 decorator.
装饰器确保在每次函数调用时检查条件计时。
Online Version of running 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)
输出
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
我需要在合并排序算法中每 500 次迭代获取一次测量值。我一直在尝试使用 Python 的时间模块来实现它，但效果不佳。
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)
相反，它有时会多次打印时间，有时会跳过。 我该怎么做才能让它真正发挥作用？
由于递增计数器的代码在函数的递归部分内，因此未统一应用。
尝试将计时部分移到函数调用的顶部。包括计数部分。它可能会更一致地进行调用。
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)
当我运行上面的代码时，我的输出是：
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, ...]
我们可以使用 decorator.
装饰器确保在每次函数调用时检查条件计时。
Online Version of running 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)
输出
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