Today, my friend had attended his interview for a summer internship next year. When asked about how the interview went, he talked about what the question was and how he'd used memoisation to bring the average time to O(n), but the interviewer wanted O(n) no matter what.
I remarked that I don't know what Memoisation is, and I realised it was perfect for me to learn about.
Memoisation is a technique used to speed up programs by storing results of expensive function calls and returning the cached result when the same inputs occur again. This allows for reducing the time spent recalculating the same values, especially when it takes way too long to calculate.
It is, in its purest form, caching. It works terrificly well when there are Overlapping Subproblems - a problem can be broken down into smaller subproblems, and the solution to these subproblems can be reused. In fact, memoisation is a part of dynamic programming, where we make tradeoffs between space and time to achieve the balance we'd like. However, unlike most dynamic programming approaches, memoisation optimises during runtime over compile time. More importantly, it is also more machine independent beacuse it stores values in memory, unlike some time-space tradeoffs which replace exensive operations with a higher number of simpler operations (e.g. multiplications with additions). It's important to note that memoisation only works with pure functions, which return the same value every time the same inputs are given.
Compilers also use memoisation, especially in languages that support the functional programming paradigm, especially the ones that use call by name evaluation.
What is call-by-name? It's a semantics for function calls where the argument expression is not evaluated before the function is called. Instead, it is evaluated each time it is used inside the function.
To avoid the massive overhead this can cause, the compliers use use auxilary functions called "thunks"* to compute the argument values, and memoise these functions instead. Some examples of such compilers would be the Glasgow Haskell Compiler (GHC) (which compiles Haskell) and the Clean Compiler (compiles Clean).
- Thunks - a thunk is a subroutine used to inject a calculation into another subroutine, usually at the start or the end of the subroutine.