Timing the Functions

Benchmarking a program means measuring how long it takes to run. The timing is fundamental to the theoretical study of algorithms. It is also important from a pragmatic perspective: fast programs are more useful than slow ones.

This section introduces one method for measuring the time it takes for code to run. You’ll see how to run the three functions you developed to find the two lowest values in a list of 1,400 monthly air pressure readings in Darwin, Australia, from 1882 to 1998.

The module time contains functions related to time. One of these functions is perf_counter, which returns a time in seconds. You can call it before and after the code you want to time and take the difference to find out how many seconds elapsed. Multiply by 1000 to convert from seconds to milliseconds:

​	​import​ ​time​
​
​	t1 = time.perf_counter()
​
​	​# Code to time goes here​
​
​	t2 = time.perf_counter()
​	​print​(f​'The code took {(t2 - t1) * 1000:.2f}ms.'​)

Let’s time all three of your find_two_smallest functions. Rather than copying and pasting the timing code three times, let’s write a function that takes another function as a parameter, as well as the list to search in. Use the type annotation typing.Callable from module typing for this parameter:

​	Callable[list[parameter types], ​return​ type]

Since you’re not interested in what this function parameter returns, use typing.Any as the return type (it matches any specific type). This timing function will return how many milliseconds it takes to execute a call on the function. After the timing function is the main program that reads the file of sea level pressures and then calls the timing function with each of the find_two_smallest functions:

​	​import​ ​time​
​	​import​ ​find_remove_find5​
​	​import​ ​sort_then_find3​
​	​import​ ​walk_through7​
​
​	​from​ ​typing​ ​import​ Callable, Any
​
​	​def​ ​time_find_two_smallest​(find_func: Callable[list[list[float]], Any],
​	lst: list[float]) -> float:
​	​"""Return how many seconds find_func(lst) took to execute.​
​	​ """​
​
​	t1 = time.perf_counter()
​	find_func(lst)
​	t2 = time.perf_counter()
​	​return​ (t2 - t1) * 1000.0
​
​	​if​ __name__ == ​'__main__'​:
​	​# Gather the sea level pressures​
​	sea_levels = []
​	​with​ open(​'sea_levels.txt'​, ​'r'​) ​as​ sea_levels_file:
​	​for​ line ​in​ sea_levels_file:
​	sea_levels.append(float(line))
​
​	​# Time each of the approaches​
​	find_remove_find_time = time_find_two_smallest(
​	find_remove_find5.find_two_smallest, sea_levels)
​
​	sort_get_minimums_time = time_find_two_smallest(
​	sort_then_find3.find_two_smallest, sea_levels)
​
​	walk_through_time = time_find_two_smallest(
​	walk_through7.find_two_smallest, sea_levels)
​
​	​print​(f​'"Find, remove, find" took {find_remove_find_time:.2f}ms.'​)
​	​print​(f​'"Sort, get minimums" took {sort_get_minimums_time:.2f}ms.'​)
​	​print​(f​'"Walk through the list" took {walk_through_time:.2f}ms.'​)

The execution times were as follows (note that they may vary depending on the computer; you’ll probably see different times):

Algorithm	Running Time (ms)
Find, remove, find	0.05ms
Sort, identify, index	0.12ms
Walk through the list	0.07ms

Notice how small these times are. No human being can notice the difference between values that are less than a millisecond. If this code never has to process lists with more than 1,400 values, you would be justified in choosing an implementation based on simplicity or clarity rather than on speed.

But what if you wanted to process millions of values? Find-remove-find outperforms the other two algorithms on 1,400 values, but how much does that tell you about how each will perform on data sets that are a thousand times larger? That will be covered in Chapter 13, .

Отправить