How to clear code

Question

Being new to this, I'm really trying to learn how to keep the code as simple as possible by completing the task that it was supposed to do.

The question I did is Project Euler , he says

Each new term in the Fibonacci sequence is generated by adding the previous two conditions. Starting from 1 and 2, the first 10 members will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 

Find the sum of all even-valued members in a sequence that do not exceed four million.

Here is my code below. I was wondering what the best way to simplify this would be to start deleting everything .get (list.length () - 1) ..... the material would be a good start, if possible, but I really don't know how?

thanks

 public long fibb() { ArrayList<Integer> list = new ArrayList<Integer>(); list.add(1); list.add(2); while((list.get(list.size() - 1) + (list.get(list.size() - 2)) < 4000000)){ list.add((list.get(list.size()-1)) + (list.get(list.size() - 2))); } long value = 0; for(int i = 0; i < list.size(); i++){ if(list.get(i) % 2 == 0){ value += list.get(i); } } return value; } 

Answer 1

Other respondents gave excellent answers. I want to show you how refactoring works in action, not just for this particular problem, knowing things about Fibonacci numbers, but as an iterative process that carefully reduces code to a minimum. Refactoring allows us to start with work, but the complex code and steadily fend off it one step at a time. Let me show you all the intermediate steps that you could take while making your way to the final decision.

Note. I changed the initial starting values ​​to 1 and 1 instead of 1 and 2. Strictly speaking, the Fibonacci sequence starts with two 1s, as in 1, 1, 2, 3, 5 ...

Step 1 - Reverse List

To get started, to get rid of the duplicate expressions list.size() - x , you can add the numbers in reverse order. Then finding the last two numbers is easier.

 public long fibb() { ArrayList<Integer> list = new ArrayList<Integer>(); list.add(1); list.add(1); while (list.get(0) + list.get(1) < 4000000) { // Use list.add(0, ...) to add entries to the *front*. list.add(0, list.get(0) + list.get(1)); } long value = 0; for (int i = 0; i < list.size(); i++) { if (list.get(i) % 2 == 0) { value += list.get(i); } } return value; } 

Step 2 - Switch to the linked list

Switch ArrayList to LinkedList . Inserting at the beginning of an array is inefficient, while its quick operation is in a linked list.

Along these lines, we need to get rid of the get() calls in the second loop. Searching for links by index is slow using linked lists. To do this, I modified the second loop to use the for (variable: container) syntax.

 public long fibb() { // Changed to use a linked list for faster insertions. List<Integer> list = new LinkedList<Integer>(); list.add(1); list.add(1); // Using get() is normally a bad idea on linked lists, but we can get away // with get(0) and get(1) since those indexes are small. while (list.get(0) + list.get(1) < 4000000) { list.add(0, list.get(0) + list.get(1)); } long value = 0; // Altered loop to avoid expensive get(i) calls. for (Integer n: list) { if (n % 2 == 0) { value += n; } } return value; } 

Step 3 - Combine Loops

The next optimization is to combine the two cycles. Instead of generating all the numbers first and then checking the even numbers, you can check the even numbers as you create them.

 public long fibb() { List<Integer> list = new LinkedList<Integer>(); long value = 0; list.add(1); list.add(1); while (list.get(0) + list.get(1) < 4000000) { int next = list.get(0) + list.get(1); list.add(0, next); if (next % 2 == 0) { value += next; } } return value; } 

Step 4 - Eliminate the List

Now you may notice that you never refer to numbers outside of index 1. The numbers in positions 2 and onwards are never used again. This means that you don’t even need to keep a list of all the numbers. Since you check even numbers as they are created, now you can throw away everything except the last two numbers.

Also, as a minor detail, rename value to total .

 public long fibb() { int a = 1, b = 1; long total = 0; while (a + b < 4000000) { // Calculate the next number. int c = a + b; // Check if it even. if (c % 2 == 0) { total += c; } // Shift the values. a = b; b = c; } return total; } 

Answer 2

You do not need a list, you only need the last two elements. Here is some kind of pseudo code, I leave the translation in your language to you.

 f0=1 #pre-last number f1=1 #last number while(...) { t = f0 + f1 if (t%2 == 0) # replaces your second loop sum += t f0 = f1 f1 = t } 

You can then notice that the numbers are always in sequence:

 odd, odd, even, odd, odd, even [...] 

and optimize if you need

Answer 3

You can completely get rid of the List. Just save the last two fibonacci numbers in two variables and calculate the next in a loop (like your first loop).

Then save the total number of all numbers that match the condition (i.e. even and less than a million) in one cycle.

Answer 4

First of all, before trying to rewrite any code, it is useful to have a unit test. Even the most obvious changes can break something unexpected.

Secondly, it is important to be very careful. You often see in the code that X-calls to the same functions can be replaced with one call, assigning a variable and using this variable.

However, you must be careful. For example, in your current code, you cannot really replace list.size (), because the size changes all the time between calls at the same iteration.

What basically makes code difficult to understand is that you reference list indexes when updating lists. You need to store indexes in variables, split across multiple lines, and possibly add comments to make them more readable.

Answer 5

I would drop the list. Here you do two iterations when all you really need to do is iterate over the sequence and save the tally variable during your work.

• So, iterating over the Fibonacci sequence using some kind of for / while loop.
• Add it to the tally variable if it is even.

To perform a simple iteration over a sequence, you only need to write down the last two values ​​(f (n) and f (n-1)) and (depending on your language) a temporary variable when you update these values. Usually something similar:

 temp = current; current = current + previous; // temp holds old value of current so the next line works. previous = temp; 

A simple approach is basic to the cycle. Or you can flip your own class that implements the Iterator<E> interface if you want all this to be OO. Then your code can be as simple as:

 Fib fib = new Fib(); for(long n : fib) { if(n % 2 == 0) t += n; } 

This reminds me that I must return to Euler again.

Answer 6

Everything looks prettier in Python!

 def fibb(): ret = 2 # to take into account the first 2 fib = [1, 2] while True: latest = fib[-1] + fib[-2] if latest >= 4000000: return ret fib.append(latest) if latest % 2 == 0: ret += latest 

Note. It was more of a programming exercise than anything else. I understand that it is probably not practical to switch to Python.

Edit, here is more memory efficient, without a list:

 def fibb(): ret = 0 f0, f1 = (1, 1) while True: f0, f1 = (f1, f0 + f1) if f1 >= 4000000: return ret if f1 % 2 == 0: ret += f1 

Answer 7

My advice would be like this (I'm not going to give an answer, since it is always better to come to conclusions myself)

Try to understand why you need to save sequence values? Your program will store 4,000,000 integers in a large array, is it really necessary? You could just use 2 elements and zip through (using the Fibonacci calculation) by adding even numbers to the Total variable.

Answer 8

You would greatly simplify it if all the values ​​in the list were not saved. You can check if they are even on the go

eg:

 int old, current; old = 1; current = 1; long value = 0; while(current < 4000000) { if(current % 2 == 0) value += current; int tmp = old + current; old = current; current = tmp; } return value; 

Answer 9

Well, firstly, a member of the Fibonacci sequence is generated by the two previous values ​​in front of it. Why not just store two numbers in the buffer and check if the number is even. If it is flat, add it to your amount and stop when you reach four million.

the code:

 public int fibEvenSum(int a, int b) { int sum = 0; int c = a + b; while (c <= 4000000) { if (c % 2 == 0) { sum += c; } //Shift the sequence by 1 a = b; b = c; c = a + b; } //repeat return sum; } 

Answer 10

As a solution @John Kugelman, but more efficient. This will depend only 1/3 of the time, and each cycle will be shorter with fewer branches and does not even require verification. This exploits the fact that every third fib value is equal and simply calculates the values ​​between reset a and b.

 public static long fibb() { int a = 1, b = 1; long total = 0; while (true) { int c = a + b; if (c >= 4000000) return total; total += c; a = b + c; b = c + a; } }