A Tale of Two Fibonacci Lambda Functions
So I was sitting at my stand up desk the other day contemplating how reality is really a propagation of complex amplitudes through configuration space when my boss burst in and exclaimed:
“Fibonacci!”
“For lunch? I don’t really do Italian,” I replied.
“No, it’s a sequence. Of numbers.”
“For what?”
“Predicting the growth of a population of rabbits.”
“So the sequence grows exponentially, then?”
“Pretty much.”
At this point I realized I didn’t know what the company I worked for actually did. Had I missed all the rodent breeding meetings? Was I living the corporate equivalent Of Mice and Men?
“So you want me to count rabbits? Please tell me there’s a room in this building full of cute little fluffy bunnies.”
“No. What school did you graduate from again? Nevermind. This assignment has nothing to do with rabbits. The CEO has a safe in his office. The code to unlock it is the hundredth number in the Fibonacci Sequence. He had it written on a Post-It note on the safe, but a custodian threw it away by mistake. So he needs you to calculate it. Oh, and you need to implement it as an AWS Lambda function.”
“Why a Lambda function?”
“He wants to be able to use it as an Alexa skill. He wants to be able to ask Alexa for the code to unlock his safe.”
“And where will the Alexa be?”
“On the safe. Anyway, I need this done by end of day.”
As my boss left the room I couldn’t help but envision her as the Energizer bunny, drum and all. Then I felt sad because I hadn’t seen the actual bunny in a while. Truth in advertising?
Cracking open the book of knowledge, also known as Wikipedia, I learned that the Fibonacci Sequence in a nutshell is:
“The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc.”
That seems easy enough. But how does one breed one rabbit to zero rabbits?
They’re even more fertile than I thought.
So I started coding, using rabbits’ mortal enemy: Python.
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n — 1) + fib(n — 2)
Ah, yes. Tending to those rabbits with a little recursion. Feeling extra pleased with myself, I immediately started work on the lambda function:
def handler(event, context):
return fib(100)
Who said programming was hard?
I saved my elegant code as fib.py and fired up Serverless framework:
$ npm install -g serverless
$ sls create -t aws-python3
And updated my newly created serverless.yml with the following:
functions:
lenny:
handler: fib.handler
And then fired it off into the sun, err, I mean AWS:
$ sls deploy
Now being an ardent pretender, err, practitioner of TDD, I decided to test my function before firing off the “You’re Welcome” email:
sls invoke -f lenny
And…
Drum roll please… Where’s that Energizer bunny?
Hmm. This shouldn’t be taking this long. I know Pythons are a tad lethargic, but this is ridiculous.
Then my function timed out. Awesome. Now what?
Luckily, I’d heard about this SaaS called IOpipe that was supposed to be good at this sort of thing. Let’s give that a try.
First, I went to IOpipe’s web site and created a free account and grabbed my token. Then I installed IOpipe into my project:
pip install iopipe -t .
And then wrapped my handler function with it:
from iopipe import IOpipe
from iopipe.contrib.profiler import ProfilerPlugin
iopipe = IOpipe(plugins=[ProfilerPlugin(enabled=True)])
@iopipe
def handler(event, context):
return fib(100)
And re-deployed:
sls deploy
Now I was expecting my function to time out again, since I hadn’t actually made any changes to my code. And sure enough, after running:
sls invoke -f lenny
It did.
But I had a new tool in my tool belt: IOpipe.
Moseying on over to my IOpipe dashboard, I saw the following:
And clicked the “Download” button to get a copy of my profiling report.
Then I fired up Python’s pstats interactive browser:
python -m pstats 2c26b46b68ffc68ff99b453c1d30413413422d706483bfa0f98a5e886266e7ae.cprofile
With the “.cprofile” file being the report I just downloaded from the IOpipe dashboard.
And that’s when I saw the problem. My Fibonacci function is O(N2) in time.
As “n” gets larger, the time it will take to calculate that number in the Fibonacci Sequence doubles.
To confirm this:
import time
for i in range(100):
t = time.time()
print(‘%d: %f’ % (fib(i), time.time() — t))
And the output:
0: 0.000006
1: 0.000003
1: 0.000002
2: 0.000001
3: 0.000002
5: 0.000004
8: 0.000005
13: 0.000008
21: 0.000013
34: 0.000021
…
See a pattern? Jumping to the 40th number in the sequence, I took a look at the stats in pstats’ interactive browser:
% sort ncalls
% stats
331160282 function calls (2 primitive calls) in 117.509 seconds
Ordered by: call count
ncalls tottime percall cumtime percall
331160281/1 117.509 0.000 117.509 117.509
filename:lineno(function)
/var/task/fib.py:4(fib)
And the 50th number in the sequence? I ain’t got time for that!
Darn those wascally wabbits. Recursion FTL.
There must be a better way.
Cracking open the highfalutin book of knowledge, also known as Wolfram Alpha, we find the following formula:
from math import sqrt
def fib(n):
return ((1 + sqrt(5)) ** n — (1 — sqrt(5)) ** n) / (2 ** n * sqrt(5))
Now while I wait for you to uncross your eyes, I’ll explain — some clever devil figured out that you can get at the fibonacci number in the sequence by using square roots and exponents. This version is blazingly fast, because math. It clocks in at O(log(n)).
So I drop this fib into my lambda function and voila, no more timeouts. Thanks IOpipe! (And that clever devil)
But of course translating formulas from Wolfram Alpha into Python feels like cheating. What’s another way to do it?
def fib():
a,b = 0,1
while True:
yield a
a, b = b, a + b
Arent’ generators neat?
218922995834555169026: 0.0007810592651367188
Yes, yes they are. This solution is O(n), but more readable, don’t you think?
You’re welcome.
