Using the recurrence relation $\binom n m = \binom {n - 1} {m - 1} + \binom {n - 1} m$, we develop a dynamic programming algorithm to calculate the binomial coefficient. I am aware that better algorithms exist.

Cache-aware programming can make a huge performance difference, especially when writing code in C++ or Rust. Python is a much more high-level language, and doesn't give us that level of control over memory layout of our data structures. So does this mean that CPU caching effects aren't relevant in Python?

In this post, we'll conduct some basic experiments to answer this question, by accessing list element either in sequental order or in a random order.

Results indicate that randomized access is consistently slower in Python. Especially as soon as problem sizes outgrow the CPU cache sizes, random access is multiple times slower. Thus, some degree of cache-aware programming may be relevant in interpreted environments like CPython 3.12 as well.

A few days ago, I was trying to split a data set into various files according to their type, but it was terribly slow. I saved an hour by taking a step back and thinking about my algorithms. Because algorithms matter. But not terribly much.