This story begins with simple implementation of a function that calculates Fibonacci numbers.
return 1 if n == 1 or n == 2 else fib(n-1) + fib(n-2)
Assuming that we are using 1-based indices, we can run a couple of tests and see that it works. Of course, fib(35) takes some time to calculate - about 15 seconds on my laptop.
Now, if you don't know what lexical closure is, I recommend reading about it on Wikipedia) before going further. Let's try to cache the results, but also be better than using conventional memoization - not only will we cache the final result of each call, but also intermediate results.
_dict = dict()
if n == 1 or n == 2:
_dict[n] = inner(n-1) + inner(n-2)
f = fib()
f(1000) returns instantly, with:
However, if I call f(1500) without calling f(1000) first, the calculation will not finish and my interpreter will crash or at least restart because of stack evaluation overflow.
But if I ran f(1000) and then f(1500) and then f(2000) and so on and so forth, advancing by 500 each time, I can very quickly get to quite far elements of Fibonacci sequence. Calculating 10 000th element is quick and easy, compared to conventional approach. We can quickly get to the point where printing the numbers to the console takes more time than actually calculating them.
I have had the rare opportunity of watching and being part of the change that the software industry has gone through throughout over 20 last years. This blog is a collection of my reflections on pursuing agility path. It includes observations and advice regarding development teams and notes on useful engineering practices. Enjoy! Piotr Górak.
Tuesday, March 26, 2013
SuperFib - an example of using lexical closure in Python
We may often come across a piece of code that was written without Unit Tests at all. In addition, the piece of code may be dealing with IO l...
Google Mock provides several ways to maintain state inside mock objects. One way of implementing state maintenance is with SaveArg . Consid...
Google Mock provides a way to return newly created objects from a mock method. Suppose we have a Generator class that is supposed to ...
Can we verify that a mock object is properly destroyed? Of course! There is a couple of subtle differences between mocking regular func...
Requirements have a long history in software industry. We all have heard or read terms like: requirements definition, requirements managemen...