2

下面是一个什么都不做的递归函数。真正的函数做了一些检查，实际上可以删除一些递归调用，但这只是简化问题的一个例子。

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

        }
    }
}

在我的 HTC Flyer android 平板电脑上，使用包含“srrieca*”的数组调用 speedtest 最多需要 5 秒。在这个极端的例子中，该函数被调用了 1 274 928 次，但仍然如此。

我很确定有一些事情可以提高这个例子的速度。

4

3 回答 3

1

一种可能性涉及通过使用某种缓存来存储可以重复使用的结果而不是递归来减少递归调用的数量。尽管在您人为的示例中，尚不清楚那将是什么。

于 2013-09-23T22:20:37.743 回答
1

tmp您可以通过池化数组来减少垃圾收集器的开销。当然，在您检查这是否是您的情况的瓶颈之后。

于 2013-09-23T22:10:51.213 回答
1

内存分配是一项昂贵的操作。你的速度被那new句话降低了。尝试为工作区域分配一个大块并保持在其中。

此外，您将经常触发垃圾收集器，这是一个更大的减速带。

于 2013-09-23T22:04:30.813 回答