java - 优化 Java 中的递归函数

Question

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

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

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

提前评论:我会修改签名以允许二进制字符串操作，这样您就可以轻松修改“输入操作”。

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

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

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

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

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

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

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

重写的想法是引入缓存并将操作与探索隔离开来。毕竟，您的算法本身就是一种操作，而不是“被测操作”。所以现在你可以(理论上)通过更改 BiFunction 来测试任何操作。参数。

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