[Swift] What I learned about Memoization

This post is originally created on May and published on my personal blog.
However, I changed my mind. I noticed that publishing it on the platform is better than on mine because someone can reach out whenever.

---

The terminology of 'memoization' is very impressive and motivated me to learn new things. Today, I want to share a good effect and show an example. I learned by Javascript in the class so I will try use Swift.

What is Memoization

According to Wikipedia, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing.

Sometimes, we use the recursive function to simplify the complicated algorithm.

However, it may become the reason to slow down. Then, you need to change the algorithm or use memoization.

Example

For example, there is one of the famous algorithms 'fibonacci sequence'. You'll see the simple code below.

func fibonacci(_ n: Int) -> Int {
  n < 2 ? n : fibonacci(n-1) + fibonacci(n-2)
}

This is the most simple solution. If given number is more than 2, calculate the sum of the last two number.

If you are interested in more details about fibonacci, please search yourself.

On the other hand, let's code with memoization.

var cache = [Int: Int]()
func cachedFibonacci(_ n: Int) -> Int {
  if let v = cache[n] {
    return v
  }

  let newValue = n < 2 ? n : cachedFibonacci(n-1) + cachedFibonacci(n-2)
  cache[n] = newValue
  return newValue
}

This example code is quiet manual but very useful.

Comparing methods

we can measure time since Jan, 1, 2001 to use CFAbsoluteTimeGetCurrent in Xcode playground.

At this time, it is enable to get the difference to call this function with calling fibonacci function before and after, and calculate the gap of them.

let start1 = CFAbsoluteTimeGetCurrent()
fibonacci(15)
let diff1 = CFAbsoluteTimeGetCurrent() - start1
print(diff1)

// 0.05279099941253662

let start2 = CFAbsoluteTimeGetCurrent()
cachedFibonacci(15)
let diff2 = CFAbsoluteTimeGetCurrent() - start2
print(diff2)

// 0.00033092498779296875

Obviously, time with memoization is 100 times faster than the one without memoization.

This is the reason why we should implement the algorithm.

Conclusion

Today, I introduced about memoization with using fibonacci sequence.

Actually when measured the time gap, you can see the necessarily.

If you faced to the issue like slow functions, I hope you recall this article.

Thank you! Enjoy your coding.

References

Memoization - Wikipedia

Using memoization to speed up slow functions

Measuring execution speed using CFAbsoluteTimeGetCurrent()

Comments

[Rost]

Hi.
I saw your post and wondered why.
Look, I don't know why you used recursion, but even a simple chatgpt poll gave the following answers:
"- The iterative method has time complexity O(n) and is very fast. Even for large values ​​of n, this method works efficiently.

• The recursive method has exponential complexity O(2^n). This leads to the fact that the execution time increases sharply with increasing n." Your solution is interesting, but it will probably also slow down due to the caching operation. Yes, the dictionary gives some advantage, but only while working with a small range of numbers. If you work with large numbers in large volumes that arrive very quickly with a difference of 2-3 seconds, for example, currency quotes over a socket, then the performance drop will be sharply noticeable. Thank you for your work and article.