Przejdź do głównej zawartości

SuperFib - an example of using lexical closure in Python

This story begins with simple implementation of a function that calculates Fibonacci numbers.

def fib(n):
    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.

def fib():
    _dict = dict()
    def inner(n):

        nonlocal _dict
        if n == 1 or n == 2:
            return 1
                return _dict[n]
            except KeyError:
                _dict[n] = inner(n-1) + inner(n-2)
                return _dict[n]
    return inner

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.


Popularne posty z tego bloga

Unit Testing code with IO file operations (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 like file writing and reading, which makes it more difficult to Unit Test it when we are trying to refactor and modify. Let's suppose the code in question looks like this:

def writeInitialsToFile(filename, name, surname):
    initials = name[0] + '.' + surname[0] + '.'
    with open(filename, 'w') as file:

def readInitials(filename):
    initials = None
    with open(filename, 'r') as file:
        initials = file.readline()
    return initials

A straightforward and bad idea would be to write a couple of Unit Tests that make use of a real file and simply test the reading and writing. Is therea a better way to test this code?

First of all, we need a way to replace the real file with something else. For both reading and writing we will now have a couple of functions, one that expects a stream fo…

Piotr's Less Obvious Advice on Google Mock: State maintenance

Google Mock provides several ways to maintain state inside mock objects. One way of implementing state maintenance is with SaveArg. Consider the following example.

We have a class Configurator, which allows a caller to set and get values of a parameter:

class Configurator

    virtual ~Configurator() {}

    virtual void setParamX(int n) = 0;
    virtual int getParamX() = 0;

And we have a class Client that calls Configurator's methods and it also has a method incParamXBy, that can be used to increase the current value of paramX by a certain value.

class Client

    Client(Configurator & cfg);
    virtual ~Client() {}

    void setParamX(int n);
    void incParamXBy(int n);
    int getParamX();


    Configurator & _cfg;

incParamXBy internally calls setParamX and getParamX on Configurator:

void Client::incParamXBy(int n)
    _cfg.setParamX(_cfg.getParamX() + n);

Let's assume that the initial value of paramX is A and that we want to increase paramX by…

Piotr's Less Obvious Advice on Google Mock: Returning new objects from a mock

Google Mock provides a way to return newly created objects from a mock method. Suppose we have a  Generator class that is supposed to generate new objects when createNewRecord method is called:

class Generator
    virtual ~Generator() {}
    virtual Record * createNewRecord() = 0;

...and suppose we want to mock this class:

class MockGenerator : public Generator
    MOCK_METHOD0(createNewRecord, Record * ());

Suppose the caller class Client has run method defined as follows:

void Client::run()
    for(int i = 0; i < 3; i++)
        rec_tab[i] = gen.createNewRecord();

We want the mock to return a pointer to a new object each time createNewRecord is called. This is how we can express this in the test code:

TEST(ClientTest, CanRun)
    MockGenerator gen;
    Client c(gen);

    EXPECT_CALL(gen, createNewRecord())
                 //this is equivalent of returning new Record(1,2,3)