如何清理我的代码

Question

作为新手,我真的想学习如何尽可能简单地保持代码,同时完成应有的工作.

我说,我所做的问题来自项目欧拉

Fibonacci序列中的每个新术语都是通过添加前两个术语生成的.从1和2开始,前10个术语将是:

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

找出序列中所有偶数值的总和,不超过四百万.

这是我的代码如下.我想知道简化这个的最佳方法是什么,开始删除所有的.get(list.length() - 1).....如果可能的话,这将是一个好的开始,但我不是真的知道怎么？

谢谢

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

其他响应者都给出了很好的答案.我想向您展示重构是如何运作的,不仅仅是针对这个特定的问题,了解有关斐波那契数字的事情,而是作为一个迭代过程,小心地将代码简化为最低限度.重构让我们从工作但复杂的代码开始,一步一步地逐步削减它.让我向您展示在完成最终解决方案的过程中您可以采取的所有步骤.

注意:我已经将您的初始起始值更改为1和1而不是1和2.严格来说,Fibonacci序列以两个1开头,如1,1,2,3,5 ......

第1步 - 反转列表

对于初学者来说,要摆脱重复的list.size() - x表达式,你可以按相反的顺序添加数字.然后找到两个最近的数字更简单.

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;
}

第2步 - 切换到链接列表

我们切换ArrayList到a LinkedList.在数组的开头插入是低效的,而在链表上快速操作.

沿着这些方向,我们需要摆脱get()第二个循环中的调用.使用链接列表按索引查找条目很慢.为此,我已经更改了第二个循环以使用for (variable: container)语法.

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;
}

第3步 - 结合循环

下一个优化是组合两个循环.您可以在生成偶数时检查偶数,而不是先生成所有数字,然后再检查偶数.

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;
}

第4步 - 删除列表

现在您可能会注意到,您从未参考索引1之外的数字.位置2及以后的数字永远不会再次使用.这暗示您甚至不需要再保留所有数字的列表.由于您在生成偶数时会检查它们,因此现在可以丢弃除最近两个数字之外的所有数字.

另外,作为一个小细节,让我们重命名value为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's even.
        if (c % 2 == 0) {
            total += c;
        }

        // Shift the values.
        a = b;
        b = c;
    }     

    return total;
}

Answer 2

您不需要列表,只需要最后两个项目.这是一些伪代码,我会把它翻译成你的语言给你.

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
}

接下来,您可以观察到数字始终是顺序的:

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

如果需要,进一步优化