Saturday, March 19, 2016

Generic Programming and POP with Swift – Iterative approach to Algorithms

After I released my Protocol OrientedProgramming with Swift book, I had an e-mail conversation with Dave Abrahams about what exactly is protocol oriented programming.  If you are not familiar with who Dave Abrahams is, take a look at this video from the 2015 WWDC When the conversation started I did not realize the person I was talking to was the person that introduced Protocol Oriented Programming to the world even though I probably watched the video at least fifteen times while I was writing my book.  It is a very good presentation and a must see for anyone interested in Protocol Oriented Programming.

One of the things that Dave recommended to me was to focus on Generic Programming.  Well in my mind I knew what generic programming was.  It was about using Generics, right?  Wrong.  I could tell that Dave was getting frustrated with me and he ended up recommending that I check out the From Mathematicsto Generic Programming book.  I was very interested in what Dave was trying to explain so I started reading the book. 

I will say that the book is very interesting and I have enjoyed reading it so far.  I have not finished it yet but I did want to start sharing some of my initial thoughts.  First off, as the title would indicate, the book is not for those intimidated by mathematics.  I graduated from college and have not taken a course on mathematics since before my favorite young baseball player, Mookie Betts,  was born (I’m showing my age here) so I really had to shake some of those math cobwebs out of my head but it is worth it.   If you are intimidated by mathematics, you can read a more general overview here:  The author Douglas Gregor has not updated the site since 2013 but it does appear to have some good information from what I have seen so far.

I do not want to spend the time writing a review of the book, instead, over the next few posts, I want to discuss some of the ideas behind Generic programming as I understand them.  I am learning what generic programming is as I write these posts so please leave comments with suggestions or any corrections if I get something wrong.

This book does start off by covering a lot of basic concepts that all advanced developers show know but sometimes we forget or ignore during our day to day work especially with the deadlines that we are always on.  Sometimes we need to be reminded of these concepts to make sure we are creating the best applications that we can.  This post will cover one of these concepts.

The second chapter of this book looks at the iterative approach to programming where we should be constantly improving our code.  At the end of the chapter the authors says that “No one writes good code the first time' it takes many iterations to find the most efficient or general way to do something.  No programmer should have a single pass mindset.  While most experience programmers realize this, a lot of times we are pressured with deadlines to just get the coding done.  This creates a lot of technical debt for our company and we should really take the time to make sure we find the most efficient way to do something.

To illustrate this iterative approach the authors’ shows how the algorithm for multiplication improved over time starting with how the ancient Egyptians did multiplication.  To me, an example that is presented in chapter 7 also does an excellent job showing this concept.  This example also demonstrates the concept that it is sometimes better to do more work rather than less.  The example that I am talking about shows how we would compute the nth Fibonacci number.  Since this blog is about programming in Swift, I would like to walk through this iterative process with examples in Swift. 

The Fibonacci sequence is a series of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89….

Where each number in the sequence is the sum of the previous two numbers in the sequence.  For example, 2+3 = 5 therefore 5 is the next number in the sequence after 3.  Also 3+5 = 8 therefore 8 is the next number in the sequence after 5.

Any entry-level developer could easily write a function to calculate the nth Fibonacci number using recursion like this:

func fibonacciRecursive(num: Int) -> Int {
    if num == 0 { return 0}
    if num == 1 { return 1}
    return fibonacciRecursive(num - 1) + fibonacciRecursive(num - 2)

This seems to work very well and we could call the function like this:


Everything is good, right?  Wrong.  Lets try to make this call:

let start = NSDate()
let end = NSDate()
let timeInterval: Double = end.timeIntervalSinceDate(start)

On my MacBook Pro this call takes almost 4 seconds.  This would indicate that we might have a problem.  Let's see what happens with this call:

let start = NSDate()
let end = NSDate()
let timeInterval: Double = end.timeIntervalSinceDate(start)

This takes 492 seconds WOW.  If you try to find the 33rd Fibonacci number you might as well take a quick nap because it took 2295 seconds on my MacBook Pro.  Yes I would say that we have a problem here. To solve this problem we need to figure out why we have it. 

The best way to figure out what is wrong with an algorithm like this is to manually walk though it.  Let's go ahead and do this as if we were figuring out the 5th Fibonacci number. The fifth Fibonacci number would be the sum of the forth and third Fibonacci numbers and we would write the formula like this:  F5 = F4+F3.  With this format we would figure out the fifth Fibonacci number like this

     F5 = (F4)                            + (F3)
        = (F3 + F2)                       + (F2 + F1)
        = ((F2 + F1) + (F1 + F0))         + ((F1 + F0) + F1)
        = (((F1 + F0) + F1) + ( F1 + F0)) + ((F1 + F0) + F1)

As we can see, just to calculate the fifth Fibonacci number this code performs seven additions and also calculates F1 + F0 three times.  So how can we eliminate this duplicated work?  One way we could do this is to do our calculations going up the chain, rather than down and to pass the Fibonacci pair into the function.

func fibonacciRecursive2(count: Int, fPair: (Int, Int) = (0,1)) -> Int {
     let newCount = count - 1
     if newCount == 0 { return fPair.1 }
     let newFPair = (fPair.1, fPair.0 + fPair.1)
     return fibonacciRecursive2(newCount, fPair: newFPair)

This new function allows us to calculate the fifth Fibonacci number with five additions.  While there may not be that noticeable of a time distance when we are calculating the lower Fibonacci numbers once we get to the higher ones (like 30) there are some drastic time differences.  I am talking about the difference between 492 seconds and 0.0223 seconds.

Is this the best algorithm for us to calculate a Fibonacci number?  Probably not.  It does take a certain amount of time to call functions therefore using a recursive function does add additional time.  Let's see how we would take the recursion out but still keep the logic.

func fibonacciIterative(num: Int) -> Int {
     if num == 0 { return 0 }
     var values = (0,1)
     for _ in 1..<num {

          values = (values.1, values.0 + values.1)
     return values.1

Now I think we have a great algorithm to compute a Fibonacci number.  To calculate the 70th Fibonacci number with the fibonacciRecursive2() function it takes 0.0472 seconds.  With the fibonacciIterative() function it takes 0.0235 seconds.

This example showed how we could improve an algorithm by taking an iterative approach where we improved the algorithm’s perform each time we rewrote the function.  On thing to keep in mind is the iterative approach can be used not only with mathematical algorithms as we just showed but also in our day-to-day development.  We should always be thinking about how we can improve our code to not only make it faster but also safer and more generic (we will be discussing this a lot more in future posts).  This post also showed that by doing more work in the function itself, rather than using a recursive function we ended up creating an algorithm that is faster and more efficent.  Another bonus is it really shows off how valuable Tuples can be when used correctly.

Over the next few posts I will write more about what I am reading.  Some of the posts will be like this one where we are reminded about some basic concepts like taking an iterative approach to our code while others will be about the concepts of Generic Programming. 

I made a separate post that contains links to all of the articles in this series.  The post is located here:

No comments:

Post a Comment