在 Java 中优化递归函数

Question

我在优化函数 AltOper 时遇到问题。在集合 {a, b, c} 中，存在不遵循结合律的给定乘法（或二项式运算，无论如何）。 AltOper 获取由 a、b、c 组成的字符串，例如 "abbac"，并计算操作的任何可能答案，例如 ((ab)b)(ac) = c, (a(b(ba))) c = a。 AltOper 将每个以 a、b、c 和 return 结尾的操作（不重复）计算为一个三元组。

虽然此代码对于小输入运行良好，但对于有点笨重的输入却需要太多时间。我尝试对一些小的进行记忆，但显然这还不够。折腾了几个小时，终于想通了，它的时间复杂度基本上太大了。但是我找不到更好的算法来计算这个。任何人都可以提出增强（显着）或重建代码的想法吗？无需具体，但只是模糊的想法也会有所帮助。

public long[] AltOper(String str){
    long[] triTuple = new long[3]; // result: {number-of-a, number-of-b, number-of-c}

    if (str.length() == 1){ // Ending recursion condition
        if (str.equals("a")) triTuple[0]++;
        else if (str.equals("b")) triTuple[1]++;
        else triTuple[2]++;
        return triTuple;
    }

    String left = "";
    String right = str;

    while (right.length() > 1){ 
        // splitting string into two, by one character each
        left = left + right.substring(0, 1);
        right = right.substring(1, right.length());
        long[] ltemp = AltOper(left);
        long[] rtemp = AltOper(right);

        // calculating possible answers from left/right split strings
        triTuple[0] += ((ltemp[0] + ltemp[1]) * rtemp[2] + ltemp[2] * rtemp[0]);
        triTuple[1] += (ltemp[0] * rtemp[0] + (ltemp[0] + ltemp[1]) * rtemp[1]);
        triTuple[2] += (ltemp[1] * rtemp[0] + ltemp[2] * (rtemp[1] + rtemp[2]));
    }
    return triTuple;
}

Answer 1

提前评论：我会修改签名以允许二进制字符串操作，这样您就可以轻松修改您的"input operation"。

java public long[] AltOper(BiFunction<long[], long[], long[]> op, String str) {

我建议对您已经回答的子部分使用某种查找 table。你暗示你已经试过了：

I tried memoization for some small ones, but apparently it's not enough

我想知道出了什么问题，因为这是个好主意，尤其是因为您的输入是字符串，它们可以快速散列和比较，所以将它们放在地图中很便宜。您只需要确保地图不会阻塞整个内存，方法是确保删除旧的、未使用的条目。类似缓存的地图可以做到这一点。我留给你找到一个适合你个人喜好的。

从那里，我会运行通过缓存检查进行任何递归，以在地图中找到预先计算的结果。然后会快速查找通常会被疯狂计算的小子串，这会大大降低您的算法的成本。

我稍微重写了您的代码，以允许各种输入（包括不同的操作）：

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.BiFunction;

import org.junit.jupiter.api.Test;

public class StringOpExplorer {

    @Test
    public void test() {
        BiFunction<long[], long[], long[]> op = (left, right) -> {
            long[] r = new long[3];
            r[0] += ((left[0] + left[1]) * right[2] + left[2] * right[0]);
            r[1] += (left[0] * right[0] + (left[0] + left[1]) * right[1]);
            r[2] += (left[1] * right[0] + left[2] * (right[1] + right[2]));
            return r;
        };
        long[] result = new StringOpExplorer().opExplore(op, "abcacbabc");
        System.out.println(Arrays.toString(result));
    }

    @SuppressWarnings("serial")
    final LinkedHashMap<String, long[]> cache = new LinkedHashMap<String, long[]>() {
        @Override
        protected boolean removeEldestEntry(final Map.Entry<String, long[]> eldest) {
            return size() > 1_000_000;
        }
    };

    public long[] opExplore(BiFunction<long[], long[], long[]> op, String input) {
        // if the input is length 1, we return.
        int length = input.length();
        if (length == 1) {
            long[] result = new long[3];
            if (input.equals("a")) {
                ++result[0];
            } else if (input.equals("b")) {
                ++result[1];
            } else if (input.equals("c")) {
                ++result[2];
            }
            return result;
        }

        // This will check, if the result is already known.
        long[] result = cache.get(input);
        if (result == null) {
            // This will calculate the result, if it is not yet known.
            result = applyOp(op, input);
            cache.put(input, result);
        }
        return result;
    }

    public long[] applyOp(BiFunction<long[], long[], long[]> op, String input) {
        long[] result = new long[3];
        int length = input.length();
        for (int i = 1; i < length; ++i) {
            // This might be easier to read...
            String left = input.substring(0, i);
            String right = input.substring(i, length);

            // Subcalculation.
            long[] leftResult = opExplore(op, left);
            long[] rightResult = opExplore(op, right);

            // apply operation and add result.
            long[] operationResult = op.apply(leftResult, rightResult);
            for (int d = 0; d < 3; ++d) {
                result[d] += operationResult[d];
            }
        }
        return result;
    }
}

重写的想法是引入缓存并将操作与探索隔离开来。毕竟你的算法本身就是一个运算，而不是'operation under test'。所以现在你可以（理论上）通过更改 BiFunction 参数来测试任何操作。

这个结果非常快，虽然我真的很怀疑适用性...

在 Java 中优化递归函数

Optimizing Recursive Function in Java

java

recursion

optimization

time-complexity

associativity