这样实现Fibonacci最快最简单！

大家都知道Fibonacci数列（一般译为斐波那契数列），比如：0, 1, 1, 2, 3, 5, 8, 13, 21...这是一个通过重复计算生成数列的好例子：f(n) = f(n-2) + f(n-1)。我们可以写一个计算第n个（从0开始）Fibonacci数的简单代码：

public class Fibonacci {

    public int fib(int n) {
        if (n == 0 || n == 1) return n;

        System.out.println("calculating fib(" + n + ")");
        return fib(n - 2) + fib(n - 1);
    }

}

 

让我们打印下计算第7个Fibonacci数的：

public class Main {

    public static void main(String[] args) {
        System.out.println("fib(7) = " + new Fibonacci().fib(7));
    }

}

 

结果如下：

calculating fib(7)
calculating fib(5)
calculating fib(3)
calculating fib(2)
calculating fib(4)
calculating fib(2)
calculating fib(3)
calculating fib(2)
calculating fib(6)
calculating fib(4)
calculating fib(2)
calculating fib(3)
calculating fib(2)
calculating fib(5)
calculating fib(3)
calculating fib(2)
calculating fib(4)
calculating fib(2)
calculating fib(3)
calculating fib(2)
fib(7) = 13

 

发现没，这样计算的步骤太多太复杂了！上面代码里有着严重的性能问题：fib(n)的调用次数随着n的增长呈指数级增长。

我们可以用一个加缓存的方法来优化，当然这个缓存是要线程安全的：

public class Fibonacci {

    private Map cache = new ConcurrentHashMap<>();

    public int fib(int n) {
        if (n == 0 || n == 1) return n;

        Integer result = cache.get(n);

        if (result == null) {
            synchronized (cache) {
                result = cache.get(n);

                if (result == null) {
                    System.out.println("calculating fib(" + n + ")");
                    result = fib(n - 2) + fib(n - 1);
                    cache.put(n, result);
                }
            }
        }

        return result;
    }

}

 

计算过程和结果如下：

calculating fib(7)
calculating fib(5)
calculating fib(3)
calculating fib(2)
calculating fib(4)
calculating fib(6)
fib(7) = 13

 

上面代码会先检查下缓存里的结果。如果这步调用还没有结果的，就计算出来并且把结果放进缓存。为了更好的性能，用了一个双重检查锁定（译者注：其实这里可以展开讨论下，为什么要加锁，如果不加锁会怎么样），可惜的是代码变复杂了。

 

Java8来拯救小伙伴们了！

 

让我们看下ConcurrentHashMap在Java8里一个新方法：

public V computeIfAbsent(K key, Function mappingFunction)

 

这个ConcurrentHashMap.computeIfAbsent有什么用呢？如果在map里没找到给定的key值所对应的entry，它会调用mappingFunction(key)来计算出哈希值，然后执行put(key,value)操作，整个过程都是保证原子性的。实际上它就是替我们完成了一堆在Java8版本前我们要自己写的脏活累活。这样现在的代码就非常简单了（当然还要感谢Java8里的新特性lambda）：

public class Fibonacci {

    private Map cache = new ConcurrentHashMap<>();

    public int fib(int n) {
        if (n == 0 || n == 1) return n;

        return cache.computeIfAbsent(n, (key) -> {
            System.out.println("calculating fib(" + n + ")");
            return fib(n - 2) + fib(n - 1);
        });
    }

}

 

当然，打印语句那里，还可以通过lambda继续简化：

public class Fibonacci {

    private Map cache = new ConcurrentHashMap<>();

    public int fib(int n) {
        if (n == 0 || n == 1) return n;

        return cache.computeIfAbsent(n, (key) -> fib(n - 2) + fib(n - 1));
    }

}

 

本文只是写了Java8里通过ConcurrentHashMap的一个新方法，简化了代码的小例子，其实Java8里让人点赞的新特性还有很多...

(英文原文出自这里)

本文同时发表在本人博客：www.newhottopic.com  ，并非转载。

评论

1 楼 Grumpy 2014-03-13  

递归的精髓在于其想法，你把Fibonacci写的也太复杂了吧
    public static int getFibocacci(int index) {
        int b = 0, n = 1;
        for (int i = 2; i <= index; i++) {
            if (i % 2 == 0) {
                b += n;
            } else {
                n += b;
            }
        }
        return index < 2 ? index : (b > n ? b : n);
    }