How to measure running time of algorithms in python

In Python, there are several common methods to calculate algorithm runtime:

1. Using the time module

The most basic method is to use the built-in time module. You can capture timestamps before and after the algorithm execution, then subtract them to obtain the runtime.

python
import time

start_time = time.time()  # Capture the start time

# Algorithm code
for i in range(1000000):
    pass

end_time = time.time()  # Capture the end time
elapsed_time = end_time - start_time  # Calculate runtime
print(f"Runtime: {elapsed_time} seconds")

2. Using the timeit module

For scenarios requiring more precise timing or automating repeated runs to obtain more stable results, you can use the timeit module. This module is specifically designed for timing small code snippets.

python
import timeit

code_to_test = """
a = [1, 2, 3, 4, 5]
b = [x + 1 for x in a]
"""

# timeit.repeat automatically runs the code multiple times and returns a list of times
elapsed_time = min(timeit.repeat(stmt=code_to_test, repeat=3, number=1000))
print(f"Runtime: {elapsed_time} seconds")

3. Using the datetime module

This method is similar to using the time module, but using the datetime module provides more options for date and time formatting.

python
from datetime import datetime

start_time = datetime.now()

# Algorithm code
for i in range(1000000):
    pass

end_time = datetime.now()
elapsed_time = end_time - start_time
print(f"Runtime: {elapsed_time}")

Practical Application Example

Assume we need to measure the performance of a sorting algorithm (e.g., quick sort):

python
import time

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# Test data
data = [3, 6, 8, 10, 1, 2, 1]

start_time = time.time()
sorted_data = quick_sort(data)
end_time = time.time()

print(f"Sorted data: {sorted_data}")
print(f"Quick sort runtime: {end_time - start_time} seconds")

By this approach, not only can we understand the actual runtime of the algorithm, but we can also explore its performance further by adjusting the size and complexity of the input data.