优化 Java 中的递归函数

Question

我在优化函数 AltOper 时遇到问题。在集合{a，b，c}中，有一个给定的乘法(或二项式运算，无论如何(，它不遵循结合定律。AltOper 获取由 a、b、c 组成的字符串，例如 "abbac"，并计算操作的任何可能答案，例如 ((ab(b((ac( = c， (a(b(ba(((c = a。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) {

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

我尝试记住一些小的，但显然这还不够

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

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

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

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参数来测试任何操作。

这个结果非常快，虽然我真的很想知道它的适用性......