📝# [Swift] What I learned about Memoization

Created

2021/5/27 20:16

Tags

Recently, I go to the college for studying programming again. At first, I imagined it is boring because I knew everything.

Although, 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.

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.

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) }`

Swift

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 }`

Swift

This example code is quiet manual but very useful.

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`

Swift

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

This is the reason why we should implement the algorithm.