Оптимизация вызова хвоста для функции Фибоначчи в Java - PullRequest
Новая
       51

Оптимизация вызова хвоста для функции Фибоначчи в Java

10 голосов
/ 28 марта 2011

Я изучал рекурсию Tail call и наткнулся на документацию, в которой упоминалось.Sun Java не реализует оптимизацию хвостовых вызовов.Я написал следующий код для вычисления числа Фибоначчи тремя различными способами: 1. Итеративный 2. Рекурсивный в голову 3. Рекурсивный хвост 

public class Fibonacci {
    public static void main(String[] args) throws InterruptedException {
        int n = Integer.parseInt(args[0]);
        System.out.println("\n Value of n : " + n);
        System.out.println("\n Using Iteration : ");
        long l1 = System.nanoTime();
        fibonacciIterative(n);
        long l2 = System.nanoTime();
        System.out.println("iterative time = " + (l2 - l1));
        System.out.println(fibonacciIterative(n));

        System.out.println("\n Using Tail recursion : ");
        long l3 = System.nanoTime();
        fibonacciTail(n);
        long l4 = System.nanoTime();
        System.out.println("Tail recursive time = " + (l4 - l3));
        System.out.println(fibonacciTail(n));

        System.out.println("\n Using Recursion : ");
        long l5 = System.nanoTime();
        fibonacciRecursive(n);
        long l6 = System.nanoTime();
        System.out.println("Head recursive time = " + (l6 - l5));
    }

    private static long fibonacciRecursive(int num) {
        if (num == 0) {
            return 0L;
        }
        if (num == 1) {
            return 1L;
        }
        return fibonacciRecursive(num - 1) + fibonacciRecursive(num - 2);
    }

    private static long fibonacciIterative(int n) throws InterruptedException {
        long[] arr = new long[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            // Thread.sleep(1);
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

    private static long fibonacciTail(int n) {
        if (n == 0)
            return 0;
        return fibHelper(n, 1, 0, 1);
    }

    private static long fibHelper(int n, int m, long fibM_minus_one, long fibM) {
        if (n == m)
            return fibM;
        return fibHelper(n, m + 1, fibM, fibM_minus_one + fibM);
    }
}

При запуске этой программы я нарисовал некоторые результаты:

  1. Головной рекурсивный метод не заканчивается при n> 50.Программа выглядела как зависшая.Любая идея, почему это могло произойти?
  2. Хвостовой рекурсивный метод занял значительно меньше времени по сравнению с рекурсией головы. Иногда занимал даже меньше времени, чем итерационный метод .Означает ли это, что Java выполняет внутреннюю оптимизацию вызовов Tail?И если да, то почему я дал StackOverflowError при n> 5000?

Технические характеристики системы:

Процессор Intel Core 5,

Windows XP,

32-битная Java 1.6

Размер стека по умолчанию для JVM.

Ответы [ 4 ]

12 голосов
/ 28 марта 2011

Означает ли это, что Java выполняет внутреннюю оптимизацию вызовов Tail?

Нет, это не так. JIT-компиляторы HotSpot не реализуют оптимизацию хвостового вызова.

Результаты, которые вы наблюдаете, типичны для аномалий, которые вы видите в бенчмарке Java, который не учитывает разогрев JVM. Например, «первые несколько раз» метод вызывается, он будет выполняться интерпретатором. Затем JIT-компилятор скомпилирует метод ... и он станет быстрее.

Чтобы получить значимые результаты, обведите весь участок и запускайте его несколько раз, пока время не стабилизируется. Затем отбросьте результаты ранних итераций.

... почему я дал StackOverflowError при n> 5000?

Это просто доказательство того, что не происходит никакой оптимизации хвостового вызова.

3 голосов
/ 28 марта 2011

По первому вопросу, что такое 2 ^ 50 (или что-то близкое)?Каждое число N в рекурсивной функции Fib вызывает его дважды (ранее 2).Каждый из них вызывает 2 предыдущие итерации и т. Д., Поэтому он увеличивается до 2 ^ (Nk) рекурсии (k, вероятно, равно 2 или 3).

Второй вопрос заключается в том, что второй является прямой N-рекурсией.Вместо того, чтобы идти двуглавым (N-1),(N-2), он просто складывается из M = 1, M = 2 ... M = N.На каждом этапе пути значение N-1 сохраняется для добавления.Поскольку это операция O (N), она сравнима с итерационным методом, единственное отличие состоит в том, как JIT-компилятор оптимизирует его.Однако проблема с рекурсией заключается в том, что для каждого уровня, который вы укладываете на фрейм, требуется огромный объем памяти - вам не хватает памяти или стекового пространства на некотором пределе. Обычно он должен быть медленнее, чем итерационный метод.

2 голосов
/ 04 декабря 2011

Вы можете использовать Memoization , чтобы избежать рекурсии головы.

Я протестировал следующий код, когда N <= 40, этот подход плох, потому что у Map есть компромисс. </p> 

private static final Map<Integer,Long> map = new HashMap<Integer,Long>();

private static long fibonacciRecursiveMemoization(int num) {
    if (num == 0) {
        return 0L;
    }
    if (num == 1) {
        return 1L;
    }

    int num1 = num - 1;
    int num2 = num - 2;

    long numResult1 = 0;
    long numResult2 = 0;

    if(map.containsKey(num1)){
        numResult1 = map.get(num1);
    }else{
        numResult1 = fibonacciRecursiveMemoization(num1);
        map.put(num1, numResult1);
    }

    if(map.containsKey(num2)){
        numResult2 = map.get(num2);
    }else{
        numResult2 = fibonacciRecursiveMemoization(num2);
        map.put(num2, numResult2);
    }

    return numResult1 + numResult2;
}

при значении n: 44

Использование итерации: время итерации = 6984

Использование рекурсии хвоста: рекурсивное время хвоста = 8940

Использование мемоизацииРекурсия: рекурсивное время запоминания = 1799949

Использование рекурсии: рекурсивное время головы = 12697568825

1 голос
/ 28 марта 2011

Относительно пункта 1: Рекурсивное вычисление чисел Фибоначчи без запоминания приводит к времени выполнения, которое экспоненциально в n. Это относится к любому языку программирования, который не запоминает автоматически результаты функций (например, большинство основных нефункциональных языков, например, Java, C #, C ++, ...). Причина в том, что одни и те же функции будут вызываться снова и снова, например f(8) будет звонить f(7) и f(6); f(7) вызовет f(6) и f(5), так что f(6) будет вызван дважды. Этот эффект распространяется и вызывает экспоненциальный рост числа вызовов функций. Вот визуализация того, какие функции вызываются: 

f(8)
 f(7)
  f(6)
   f(5)
    f(4)
     ...
    f(3)
     ...
   f(4)
    ...
  f(5)
   f(4)
    ...
   f(3)
    ...
 f(6)
  f(5)
   ...
  f(4)
   ...
...