Understanding Python decorators optimizing a recursive Fibonacci implementation

A decorator is a Python function that takes a function object as an argument and returns a function as a value. Here is an example of decorator definition:

To apply a decorator to an existing function, you just need to put @decorator_name in the line before its definition, like this example:

This decorator doesn’t do anything, so let’s think about a more concrete problem we could solve using decorators.

Fibonacci sequence

By definition, the first two numbers in the Fibonacci sequence are either 1 and 1 or 0 and 1. All the other numbers are the sum of the previous two numbers of the sequence. Example:

  1. 0, 1: the third number is 1
  2. 0, 1, 1: the fourth number is 2
  3. 0, 1, 1, 2: the fifth number is 3
  4. 0, 1, 1, 2, 3: the sixth number is 5
  5. etc…

If we wanted to give a math definition of the sequence, we could describe it in this way:

  • F(0): 0
  • F(1): 1
  • F(n): F(n-1) + F(n-2)

In Python we could have a recursive function like the following one:

What’s the problem with this implementation? The code works as expected, but it’s very inefficient. The next picture will explain what happens when we will try, for example, to calculate the 5th number of the sequence:

fibo

 

Fib(5) is Fib(4) + Fib(3), but Fib(4) itself is Fib(3) + Fib(2), and… the picture just tell us that we have calculated Fib(3) 2 times, Fib(2) 3 times, Fib(1) 5 times! Why are we repeating the same operation every time if we already calculated the result?

Memoization

In computing, 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.

We need to store values of the sequence we have already calculated and get them later when we need them. Let’s implement a simple memoization decorator:

The decorator defines a dict at the beginning that is used as a cache. When we want to find the n number of the sequence, it first checks if the value was already calculated and that value is returned instead of being calculated again. If the value is not found, then the original function is being called and then the value is store in the cache, then returned to the caller.

Using the memoize decorator

How much this decorator can speed up our fib method? Let’s try to benchmark the execution using Python timeit module.

The required time to calculate the 35th number of the Fibonacci sequence on my laptop is: 4.73480010033

The required time to calculate the 35th number of the Fibonacci sequence on my laptop is: 0.000133037567139

Quite faster, don’t you think? I will let you try how long does it take to calculate the 60th number of the sequence with and without using the decorator. Hint: grab a cup of coffee before beginning!

Django Notes: read values from settings in a safe way

Working on Django projects I find very often that many developers access the values that are defined in settings in this way

What happens if MY_SETTING has not been defined in settings.py? The code will raise an error and crash, of course. How can we make the code more reliable? We could try/except the code block that tries to read the value and maybe set a value if we get an exception, but this would not be a clean way to do this job.

A cleaner way to do it is to use getattr in this way:

getattr will try to read MY_SETTING value from settings.py, if the value doesn’t exist my_value will be assigned with my-default-value.

How to write a custom Django Middleware

To understand how a Django Middleware works we need to remember that the basic architecture of Django is composed by a request and a response. A middleware is something that stays in the middle. Let’s give a look to the next diagram, taken from official Django documentation:

middleware

 

Important things to know

There are four important things to know about middlewares:

  • You need to write a class that just inherit from object
  • The order where you place your middleware in settings.py is important: middlewares are processed from top to bottom during a request and from bottom to top during a response.
  • You don’t need to implement all the available methods of a middleware. For example you can just implement process_request and process_template_response
  • If you implement process_request and you decide to return an HttpResponse, all the other middlewares, views etc… will be ignored and only your response will be returned

Writing a middleware

In my example I wanted to implement a feature that saves the time when a request is made and the time when a request has been processed, then calculates the time delta and exposes this value in the context so that is accessible from our templates. How to implement a similar feature using a middleware? Here is my example:

Please don’t care about how I calculated the time. I’m aware that there are better ways to do it, but I just wanted to keep it simple and show how to implement a simple middleware.

If you want to see a complete example of a project that includes and uses this middleware, here you can find the complete source code: https://github.com/andreagrandi/benchmark-middleware-example

References

Why I completely switched this website to HTTPS (and why you should do the same)

I must admit it, there was a time when I was not using HTTPS, not even to protect the admin section of the website. This means that anyone could have intercepted the password and published (or deleted) things in my name. Since a couple of years ago I started protecting my admin sectio using an SSL certificate.  I haven’t done it before for a couple of reason: my hosting was on a provider that required a lot of money (something like 100$/year) to enable SSL support, plus an SSL certificated costed at least 100-120$/year.

When I migrated my website on my own VPS on DigitalOcean I finally discovered that StartSSL was giving free class 1 certificates and I immediately got one. I made the mistake to just serve the admin pages using HTTPS, not all the website. I regretted about this decision after readin a couple of articles that were explaining how some internet providers where changing served HTTP pages injecting their own ads or banner. That was unacceptable to me and I swicthed the whole website to HTTPS.

Basically, if you don’t serve even your personal website using HTTPS, someone could change the page while it’s being transfered to the requester. Imagine if you have (like me) a page on your blog that let people download your public PGP key. Users could be served with a different key, so someone else would be able to decrypt a message intended for you only. Scary, isn’t it?

If you need more informations about how to request a StartSSL certificate and how to install it on Nginx/Apache, I can suggest this nice tutorial: https://konklone.com/post/switch-to-https-now-for-free

If you need to serve a WordPress website, that configuration is not enough. In that case you may want to have a look at my own Nginx configuration, available at this address: https://gist.github.com/andreagrandi/5de9dc9c4eb7e732764c

p.s: if you are you curious to try how Digital Ocean VPS works and fancy 10$ credit (enough for 2 months if you choose the basic droplet) for free, use this link and enjoy it https://www.digitalocean.com/?refcode=cc8349e328a5

Django Notes: tests, setUp method and db data

This won’t be a full post, but just a quick note (probably the first one of a serie) about development with Django.

When we write a TestCase test, if we have defined a setUp method, it will be called before the execution of each test. One could think that the database is completely reset after each test, but this is not true (not like I was thinking). After each test, whatever we wrote on the database is rolled back. If we create a “Client” row (assuming we have a model called Clients) in our setUp, when we call it the second time the ID won’t be 1 as someone (me included) could expect. It will be 2 instead, because the database has not completely deleted and created from scratch.

This means that we can’t assume that our Client ID will always be 1 for each test and we should rather reference to it in a dinamic way like: self.client.id

This could be a trivial thing for many people but I was not 100% sure about this so I asked for a confirmation on #django IRC room and people (expecially apollo13) was kind enough to explain me how it works.