Maintaining the Single Responsibility Principle with Project Euler #2

Question

This is my solution to Project Euler problem 2:

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

The class fibonacci_Even_Sum_Calculator does two things:

1. calculate the sum of the even-valued Fibonacci numbers
2. cache the results in a dictionary

Is this a sign that this code violates the Single Responsibility Principle?

class fibonacci_Even_Sum_Calculator:

        def __init__(self):
                self.cached_result = dict()

        def F(self, n):

                if n == 0: 
                        return 0
                elif n == 1: 
                        return 1
                else:
                        if(self.cached_result.has_key(n)):
                                return self.cached_result[n]
                        else:
                                result = self.F(n-1) + self.F(n-2)
                                self.cached_result[n] = result 
                                return result

        def is_even(self, number):
                return number % 2 == 0

        def get_result(self,limit_value):

                sequence = 2
                sum = 0

                while True:

                        result = self.F(sequence)

                        if result > limit_value:
                                break

                        if self.is_even(result) :
                                sum = sum + result

                        sequence = sequence + 1

                return sum

fibonacci_calculator = fibonacci_Even_Sum_Calculator() 
result = fibonacci_calculator.get_result(4000000)
print result

Answer 1

I think you are violating SRP, but not for the reason you think you are. Memoization is fine, it's definitely one approach to calculating the fibonacci values, but you have one class that is doing BOTH calculating the Fibonacci values AND summing the even ones.

If you are really worried about SRP, I would have a generator to calculate the Fibonacci numbers, and then an external function to sum them:

def sum_evens(limit):
    sum = 0
    for f in fibonacci_numbers(): # left as an exercise
        if f > limit: 
            break
        elif f % 2 == 0:
            sum += f
    return sum

Otherwise, minor notes, your class is named fibonacci_Even_Sum_Calculator. The most accepted convention for class names is CamelCase, so FibonacciEvenSumCalculator is strongly preferred. Similarly, function names should be lowercase, and f is an insufficient name for code that is "get the nth Fibonacci number".

Answer 2

TL;DR

yes, you are probably violating the SRP but in this case I wouldn't care.

I think this is a hard one.

First I tend towards Barry's point of view:

You are really doing "two things" in your class. So, if you take the dictum of "reasons" to change to the letter, you are violating the SRP.

But on the other hand: I think breaking this up into a fibonacci-series-producing class and another summing-class is nonsensical.

My personal interpretation of the Single Responsibility Principle is: "dealing with one topic". And when objects tend to grow too much, I have to decide, which functions are off-topic and need to be refactored in some way. If you want: I am advocating a more pragmatically - perhaps not really orthodox position.

In your case that means, if I say "dealing with fibonacci numbers" is our topic and the resulting class results in two "subtopics" generating and summing that is a possible code smell, but more in the future than now.

Don't forget: Those principles weren't developed for their own sake, they were developed with some purposes. And one of those purposes is maintainability. And as far as you code goes, I tend to say, it is still maintainable.

One last word: If you really want to improve your code - get rid of the class at all. I see no reason, why one should write for such a job a class at all - except, perhaps, you are on the one hand obsessed with classes or on the other hand, for educational purposes.

Two simple functions were sufficient.

Python is a decent objectoriented language though, but sometimes it is overhead to write a class for everything. Python is not Java, where it is necessary to write explicit classes for everything. Python is not forcing you to do that.

First take care of writing clean code. Later take care of your overall design. Start with naming. Barry pointed out, that you should name your functions more pythonic. Another point worth mentioning is your function naming in general. Function names should reveal their intention. So what is the intention of fibonacci_calculator.get_result? Reading this, withouht investigating your code, my answer is: I don't have any clue. I know there are fibonacci numbers involved and somehow there is a result. How it is claculated: the heck, I do not know. On the other hand: fibonacci.sum_evens_up_to() clearly says, what it does: it sums up the fibonacci evens up to a paramter given.

Answer 3

1. Comments on your code

1. There are no docstrings. How are we supposed to know what this code does and how to call it?

2. There are no test cases. This kind of code is an ideal opportunity to use doctests.

3. To memoize a function, the most convenient way to do it is to use a decorator. This keeps the memoization logic separate from the code being memoized, and also makes the memoization re-usable for other functions. Using functools.lru_cache you could write:

   from functools import lru_cache
   
   @lru_cache(maxsize=None)
   def F(n):
       """Return the 'n'th Fibonacci number.
   
       >>> [F(i) for i in range(10)]
       [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
   
       """
       if n <= 2:
           return (0, 1, 1)[n]
       else:
           return F(n - 1) + F(n - 2)
   

4. Once you split the memoization into its own function or class, there will no longer be any persistent state in your program (the only use of self at present is self.cached_result). So there is no need to use a class here.

   Even in its current state, the method is_even does not refer to self and so does not need to be a method.

5. You start your summation loop with sequence = 2. But this means that someone who wants to check that your code is correct would have to go through a complicated analysis: "why start at \$2\$? ... er ... Oh, I see, \$F(0)=0\$ which doesn't contribute anything to the sum, and \$F(1)=1\$ which is odd. But \$F(2)=1\$ too so why not start at \$3\$?"

   I would recommend making it easy for someone to read the program, by starting with sequence = 0. The efficiency gain of avoiding two calls to F is negligible.

6. Your loop looks like this:

   sequence = 2
   while True:
        # ...
        sequence += 1
   

   It would simplify your loop if you used itertools.count:

   from itertools import count
   for sequence in count(2):
   

   but as discussed above, it would be better to start from 0:

   for sequence in count():
   

7. Your method is_even is just one line long, and called from just one place. It hardly seems worth making it into a separate function.

2. A simpler approach

This is the kind of problem that can be solved very simply. No need for classes, memoization, or multiple functions; all that's needed is a simple loop:

def sum_even_fibonacci(limit):
    """Return the sum of the even Fibonacci numbers up to 'limit'.

   >>> # See <http://oeis.org/A099919>
   >>> [sum_even_fibonacci(4 ** i) for i in range(1, 11)]
   [2, 10, 44, 188, 798, 3382, 14328, 60696, 257114, 1089154]

    """
    total = 0
    # a = F(2) and b = F(3), so b is first nonzero even Fibonacci number.
    a, b = 1, 2
    while b <= limit:
        total += b
        a, b = a + 2*b, 2*a + 3*b
    return total

This works because every third Fibonacci number is even, so we skip directly from \$F(3n)\$ to \$F(3n+3)\$, the next even value. If we have $$\eqalign{a &= F(3n-1) \\ b &= F(3n)}$$ then $$\eqalign{F(3n+1) &= a+b \\ F(3n+2) &= a+2b \\ F(3n+3) &= 2a+3b}$$