如何提高递归方法的性能？ [英] How to improve the performance of the recursive method?
问题描述
我正在学习数据结构和算法，这是一个我坚持的问题。
I'm learning data structures and algorithms, and here is a question that I'm stuck with.
我必须提高递归调用的性能将值存储到内存中。
I have to improve the performance of the recursive call by storing the value into memory.
但问题是非改进版本似乎比这更快。
But the problem is that the non-improved version seems faster than this.
有人可以帮帮我吗？
Syracuse数字是由以下规则定义的正整数序列：
syra（1）≡ 1
syra(1) ≡ 1
syra（ n ）≡ n + syra（ n / 2），如果 n mod 2 == 0
syra(n) ≡ n + syra(n/2), if n mod 2 == 0
syra（ n ）≡ n + syra（（ n * 3）+1），否则
syra(n) ≡ n + syra((n*3)+1), otherwise
import java.util.HashMap;
import java.util.Map;
public class SyraLengthsEfficient {
int counter = 0;
public int syraLength(long n) {
if (n < 1) {
throw new IllegalArgumentException();
}
if (n < 500 && map.containsKey(n)) {
counter += map.get(n);
return map.get(n);
} else if (n == 1) {
counter++;
return 1;
} else if (n % 2 == 0) {
counter++;
return syraLength(n / 2);
} else {
counter++;
return syraLength(n * 3 + 1);
}
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
public int lengths(int n) {
if (n < 1) {
throw new IllegalArgumentException();
}
for (int i = 1; i <= n; i++) {
syraLength(i);
if (i < 500 && !map.containsKey(i)) {
map.put(i, counter);
}
}
return counter;
}
public static void main(String[] args) {
System.out.println(new SyraLengthsEfficient().lengths(5000000));
}
}
这是我写的正常版本：
public class SyraLengths{
int total=1;
public int syraLength(long n) {
if (n < 1)
throw new IllegalArgumentException();
if (n == 1) {
int temp=total;
total=1;
return temp;
}
else if (n % 2 == 0) {
total++;
return syraLength(n / 2);
}
else {
total++;
return syraLength(n * 3 + 1);
}
}
public int lengths(int n){
if(n<1){
throw new IllegalArgumentException();
}
int total=0;
for(int i=1;i<=n;i++){
total+=syraLength(i);
}
return total;
}
public static void main(String[] args){
System.out.println(new SyraLengths().lengths(5000000));
}
}
编辑
它比非增强版本慢。
import java.util.HashMap;
import java.util.Map;
public class SyraLengthsEfficient {
private Map<Long, Long> map = new HashMap<Long, Long>();
public long syraLength(long n, long count) {
if (n < 1)
throw new IllegalArgumentException();
if (!map.containsKey(n)) {
if (n == 1) {
count++;
map.put(n, count);
} else if (n % 2 == 0) {
count++;
map.put(n, count + syraLength(n / 2, 0));
} else {
count++;
map.put(n, count + syraLength(3 * n + 1, 0));
}
}
return map.get(n);
}
public int lengths(int n) {
if (n < 1) {
throw new IllegalArgumentException();
}
int total = 0;
for (int i = 1; i <= n; i++) {
// long temp = syraLength(i, 0);
// System.out.println(i + " : " + temp);
total += syraLength(i, 0);
}
return total;
}
public static void main(String[] args) {
System.out.println(new SyraLengthsEfficient().lengths(50000000));
}
}
最终解决方案（学校标记为正确）自动标记系统）
public class SyraLengthsEfficient {
private int[] values = new int[10 * 1024 * 1024];
public int syraLength(long n, int count) {
if (n <= values.length && values[(int) (n - 1)] != 0) {
return count + values[(int) (n - 1)];
} else if (n == 1) {
count++;
values[(int) (n - 1)] = 1;
return count;
} else if (n % 2 == 0) {
count++;
if (n <= values.length) {
values[(int) (n - 1)] = count + syraLength(n / 2, 0);
return values[(int) (n - 1)];
} else {
return count + syraLength(n / 2, 0);
}
} else {
count++;
if (n <= values.length) {
values[(int) (n - 1)] = count + syraLength(n * 3 + 1, 0);
return values[(int) (n - 1)];
} else {
return count + syraLength(n * 3 + 1, 0);
}
}
}
public int lengths(int n) {
if (n < 1) {
throw new IllegalArgumentException();
}
int total = 0;
for (int i = 1; i <= n; i++) {
total += syraLength(i, 0);
}
return total;
}
public static void main(String[] args) {
SyraLengthsEfficient s = new SyraLengthsEfficient();
System.out.println(s.lengths(50000000));
}
}
推荐答案
忘记由于使用 Map 而导致代码效率低下的答案，这不是它变慢的原因 - 这是因为你将计算出的数字的缓存限制在 n< 500 。一旦你删除了这个限制，事情开始变得非常快;这里是您填写详细信息的概念证明：
Forget about the answers that say that your code is inefficient because of the use of a Map, that's not the reason why it's going slow - it's the fact that you're limiting the cache of calculated numbers to n < 500. Once you remove that restriction, things start to work pretty fast; here's a proof of concept for you to fill-in the details:
private Map<Long, Long> map = new HashMap<Long, Long>();
public long syraLength(long n) {
if (!map.containsKey(n)) {
if (n == 1)
map.put(n, 1L);
else if (n % 2 == 0)
map.put(n, n + syraLength(n/2));
else
map.put(n, n + syraLength(3*n+1));
}
return map.get(n);
}
如果您想了解更多有关计划中发生的事情的信息为什么这么快，请看一下这篇关于 Memoization 的维基百科文章。
If you want to read more about what's happening in the program and why is so fast, take a look at this wikipedia article about Memoization.
另外，我认为你滥用计数器变量，你增加它（ ++ ）当第一次计算一个值，但是当在地图中找到一个值时，你会累积它（ + = ）。这对我来说似乎不对，我怀疑它是否给出了预期的结果。
Also, I think you're misusing the counter variable, you increment it (++) when a value is calculated the first time, but you accumulate over it (+=) when a value is found in the map. That doesn't seem right to me, and I doubt that it gives the expected result.
这篇关于如何提高递归方法的性能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
