12.6. Summary¶
The Python standard library comes with two modules for profiling: timeit and cProfile . The timeit.timeit() function is useful for running small snip- pets of code to compare the speed difference between them. The cProfile. run() function compiles a detailed report on larger functions and can point out any bottlenecks.
It’s important to measure the performance of your code rather than make assumptions about it. Clever tricks to speed up your program might actually slow it down. Or you might spend lots of time optimizing what turns out to be an insignificant aspect of your program. Amdahl’s Law captures this mathematically. The formula describes how a speed-up to one compo- nent affects the speed-up of the overall program. Big O is the most widely used practical concept in computer science for programmers. It requires a bit of math to understand, but the underlying concept of figuring out how code slows as data grows can describe algo- rithms without requiring significant number crunching.
There are seven common orders of big O notation: O(1), or constant time, describes code that doesn’t change as the size of the data n grows; O(log n), or logarithmic time, describes code that increases by one step as the n data doubles in size; O(n), or linear time, describes code that slows in proportion to the n data’s growth; O(n log n), or n-log-n time, describes code that is a bit slower than O(n), and many sorting algorithms have this order.
The higher orders are slower, because their runtime grows much faster than the size of their input data: O(n 2 ), or polynomial time, describes code whose runtime increases by the square of the n input; O(2 n ), or exponen- tial time, and O(n!), or factorial time, orders are uncommon, but come up when combinations or permutations are involved, respectively.
Keep in mind that although big O is a helpful analysis tool, it isn’t a substitute for running your code under a profiler to find out where any bottlenecks are. But an awareness of big O notation and how code slows as data grows can help you avoid writing code that is orders slower than it needs to be.