下面是一个不执行任何操作的递归函数。真正的函数会做一些检查,实际上可以删除一些递归调用,但它只是简化问题的一个例子。
public void speedtest2(char[] s) {
int a, c;
int l, lmax;
int arrlength = Array.getLength(s);
for (a = 0; a < arrlength; a++) {
if ((a == 0) || (s[a]) != s[a - 1]) {
if (s[a] == '*') {
lmax = 26;
} else {
lmax = 1;
};
for (l = 1; l <= lmax; l++) {
tot++;
char[] tmp = new char[arrlength - 1];
int p = 0;
for (c = 0; c < arrlength; c++) {
if (c != a) {
tmp[p++] = s[c];
};
};
speedtest2(tmp);
}
}
}
}
使用包含"srrieca*"的数组调用速度测试将在我低级的HTC Flyer Android平板电脑上最多需要5秒。在这个极端的例子中,该函数被调用了 1 274 928 次,但仍然如此。
我很确定有一些事情可以提高这个例子的速度。
可以通过池化tmp
数组来减少垃圾回收器开销。当然,在您检查了这是您案例中的瓶颈之后。
一种可能性是通过使用某种缓存来存储可以重用的结果,而不是递归,从而减少递归调用的数量。尽管在您的人为示例中,尚不清楚那会是什么。
内存分配是一项昂贵的操作。你的速度被这句new
话拉低了。尝试为工作区分配一个大块并保持在该区域内。
此外,您将经常触发垃圾收集器,这是一个更大的减速带。