Python - test algorithm performance
In this article, we would like to show how to test algorithms' performance in Python.
Usually, when we compare algorithms that execution times are short, we repeat computations multiple times to get precise results. The number of repeats is selected empirically. The source code that is not an algorithm part shouldn't be measured.
Main concept:
xxxxxxxxxximport timedef get_time(): return round(1000 * time.time())def test_function(repeats, description, function): t1 = get_time() i = 0 while i < repeats: function() i += 1 t2 = get_time() dt = t2 - t1 print(description, ': total time is ', dt, ' ms')# Usage example:def case_1(): # source code case 1 return 0def case_2(): # source code case 2 return 0def case_3(): # source code case 3 return 0repeats = 1000 # set number of repeats depending on cases complexitytest_function(repeats, 'case 1', case_1)test_function(repeats, 'case 2', case_2)test_function(repeats, 'case 3', case_3)# add more cases here ...Hint: presented concept describes only a simple way how to test performance - in practice tests made by benchmarks are more complex.
In the below example we compare algorithms that computes Fibonacci sequence values.
In the test, we made 1000 repeats on Fibonacci algorithms using Ryzen 9 x5900 processor and Python 3.10 (CPyhyon) under Windows 11 x64.
Test result:
xxxxxxxxxxIterative algorithm : total time is 121 msBinet's formula : total time is 12 msConclusion: iterative algorithm is 10 times slower in the tested cases.
Test source code:
xxxxxxxxxximport timeimport mathdef get_time(): return round(1000 * time.time())def test_function(repeats, description, function): t1 = get_time() i = 0 while i < repeats: function() i += 1 t2 = get_time() dt = t2 - t1 print(description, ': total time is', dt, 'ms')# Tested algorithms:def fibonacci_1(input): if input < 1: return 0; if input < 2: return 1; return fibonacci_1(input - 2) + fibonacci_1(input - 1);def fibonacci_2(input): a = math.pow(1 + 2.23606797749979, input); b = math.pow(1 - 2.23606797749979, input); c = 2.23606797749979 * math.pow(2, input); return round((a - b) / c);# Performance tests:def case_1(): i = 1 while i < 10: fibonacci_1(i) i += 1def case_2(): i = 1 while i < 10: fibonacci_2(i) i += 1repeats = 1000 # set number of repeats depending on cases complexitytest_function(repeats, 'Iterative algorithm', case_1)test_function(repeats, 'Binet\'s formula', case_2)
