Of course I could have picked other languages, be it human, like Xhosa or programming, like Java, C++ etc, but why I mainly opted for Golang is a story for another day.
From that nasty experience (that I will write about in the near future), the one thing that came out of that experience, especially as a self-taught developer, is the need to understand data structures and algorithms. And that is why I am writing this article, and a few more later on, to make this series on data structure and algorithms.
Fibonacci sequence, one of the most common mathematical formulas out there, refers to a sequence of numbers in which each number is a sum of its two preceding numbers.
The implementation of this algorithm with Go can be achieved with the code:
Give it a try on Go Playground
Fibonacci sequence and generation of the sequence numbers is a recursive exercise. Using the code sample above, as n increases, there is a significantly higher cost, in terms of time and space, required to run to completion this algorithm. This time and space complexity jargon used to measure efficiency in running of an algorithm is referred to as the Big O notation. Discussion on the Big O notation is beyond the scope of this article.
Question is, how do we optimize our script for faster compute times and reduced memory resource usage?
This is a concept in computer science used to optimize and speed up expensive or costly processes by cache of results.
With regards to generation of Fibonacci sequence of numbers and the recursive nature of the algorithm, caching of outcome with every iteration helps speed up execution.
Using the figure above, the recursive nature of the algorithm can be represented as below (see what I did there? :-) ):
Fib(0) = 0
Fib(1) = 1
Fib(2) = Fib(1) + Fib(0)
Fib(3) = Fib(2) +Fib(1)
Fib(5) = Fib(4) + Fib(3)
The computation of the 5th Fibonacci sequence number can be significantly made faster if the results of the 3rd and 4th terms were cached. Now imagine how much faster the 50th sequence number can be generated, considering all the previously stored/cached sequence values. Its as fast as retrieving the values from storage and summing them up.
Here is the implementation with memoization…
Don’t take my word for it as regards how blazing fast the execution is. Give it a try.
There is no quicker, fun and better optimized method for learning a new language, than trying the syntax out with data structures and algorithms exercises. In addition to improved retention of the language syntax, it also helps one develop applications that are rather time and memory efficient.
In the example above, through memoization, we have managed to significantly speed up the computation of the algorithm. This definitely leaves the processing compute not exhausted (lol) but with more memory available to undertake other jobs ;-)
PS: — Though I’m a newbie, I’d greatly appreciate feedback. Thanks