Как я могу оптимизировать эти две взаимно рекурсивные функции в Java?

Question

Мне нужно написать методы, которые суммируют и предоставляют списки выходных данных этих составных взаимно рекурсивных функций, но их выполнение не зависит от времени моей текущей реализации:

public static long fAnn(long n) {
      if (n == 0) return 1;
      else return n - fJohn(fAnn(n-1));
    }

    public static long fJohn(long n) {
      if (n <= 0) return 0;
      else return n - fAnn(fJohn(n-1));
    }
public static List<Long> john(long n) {
    List<Long> res = new ArrayList<Long>();

    for (long i = 0; i < n; i++) {
      res.add(fJohn(i));
    }

    return res;       
}

public static long sumJohn(long n) {
    long sum = 0;
    for (long i = 0; i < n; i++) sum += fJohn(i);
    return sum;
}
public static long sumAnn(long n) {
    long sum = 0;
    for (long i = 0; i < n; i++) sum += fAnn(i);
    return sum;
}

Я думал о передаче последнего значения функции обратно в функцию, но я не совсем уверен, как я мог это сделать.

Answer 1

Я воспользовался советом @Tim Beigeleisen и решил узнать больше о динамическом программировании, чтобы улучшить наивный рекурсивный подход, который я использовал для этой функции вместо того, чтобы сначала искать ответы здесь.

Вот код, который я нашелс:

import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;


public class Johnann {
    private static Map<Long, Long> jMem;
    private static Map<Long, Long> aMem;


    public static long fAnn(long n) {
      if (n < 2) {
        aMem = new HashMap<Long, Long>();
        aMem.put(n, (long)1);
        return 1;
      }
      else if (aMem.keySet().contains(n)) {
        return aMem.get(n);
      }
      else {
        long res = n - fJohn(fAnn(n-1));
        aMem.put(n, res);
        return res;
      }
    }


    public static long fJohn(long n) {
      if (n < 2) {
        jMem = new HashMap<Long, Long>();
        jMem.put(n, (long)0);
        return 0;
      }
      else if (jMem.keySet().contains(n)) {
        return jMem.get(n);
      }
      else {
        long res = n - fAnn(fJohn(n-1));
        jMem.put(n, res);
        return res;
      }
    }

    public static List<Long> john(long n) {
        List<Long> res = new ArrayList<Long>();

        for (long i = 0; i < n; i++) {
          res.add(fJohn(i));
        }

        return res;
    }

    public static List<Long> ann(long n) {
        System.out.println(n);
        List<Long> res = new ArrayList<Long>();

        for (long i = 0; i < n; i++) {
          res.add(fAnn(i));
        }

        return res;
    }


    public static long sumJohn(long n) {
        if (n == 0) return 0;
        else if (n < 2) return 1;
        long sum = 0;
        for (long i = 0; i < n; i++) sum += fJohn(i);
        return sum;
    }
    public static long sumAnn(long n) {
        if (n == 0) return 0;
        else if (n < 2) return 1;
        long sum = 0;
        for (long i = 0; i < n; i++) sum += fAnn(i);
        return sum;
    }
}

Я видел другие, лучшие реализации, которые использовали ArrayList вместо карты, например:

import java.util.*;

public class Johnann {

    private enum Person {JOHN, ANN}

    private static List<Long> getListForName(Person person, long n) {
        List<Long> ann = new ArrayList<>(Arrays.asList(1L));
        List<Long> john = new ArrayList<>(Arrays.asList(0L));

        for (int dayAnn = 1, dayJohn = 1; dayAnn < n || dayJohn < n; ) {
            if (john.size() > ann.get(dayAnn - 1)) {
                ann.add(dayAnn - john.get(Math.toIntExact(ann.get(dayAnn - 1))));
                dayAnn++;
            }
            if (ann.size() > john.get(dayJohn - 1)) {
                john.add(dayJohn - ann.get(Math.toIntExact(john.get(dayJohn - 1))));
                dayJohn++;
            }
        }
        return (person == Person.JOHN ? john : ann).subList(0, Math.toIntExact(n));
    }

    public static List<Long> john(long n) {
        return getListForName(Person.JOHN, n);
    }

    public static List<Long> ann(long n) {
        return getListForName(Person.ANN, n);
    }

    public static long sumJohn(long n) {
        return john(n).stream().mapToLong(Long::longValue).sum();
    }

    public static long sumAnn(long n) {
        return ann(n).stream().mapToLong(Long::longValue).sum();
    }
}

Возможно, это было намного быстрее, но я просто счастливчто я много узнал о динамическом программировании и оптимизации рекурсивных вызовов с помощью этой проблемы.

Answer 2

Проблема с этим решением - многократное выполнение методов с одинаковыми аргументами. Вместо этого вы можете использовать метод оптимизации под названием memoization .

Из Википедии:

В вычислениях запоминание или запоминание - это метод оптимизации, который используется главным образом для ускорения работы компьютерных программ путем сохранения результатов дорогостоящих вызовов функций и возврата кешированного результата, когда одни и те же входные данные повторяются.

Реализация может выглядеть следующим образом. Обратите внимание, что на этот раз вам нужно будет создать экземпляр класса для использования методов, потому что они больше не являются статическими.

private Map<Long, Long> annCache = new HashMap<>();
private Map<Long, Long> johnCache = new HashMap<>();

long fAnn2(long n) {
    return annCache.computeIfAbsent(n, x -> {
        if (x == 0) return 1L;
        else return x - fJohn2(fAnn2(x - 1));
    });
}

long fJohn2(long n) {
    return johnCache.computeIfAbsent(n, x -> {
        if (x <= 0) return 0L;
        else return x - fAnn2(fJohn2(x - 1));
    });
}