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: generic-programming.org. 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:
fibonacciRecursive(5)
Everything is good, right? Wrong.
Lets try to make this call:
let start =
NSDate()
fibonacciRecursive(20)
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()
fibonacciRecursive(30)
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