java – 如何提高递归方法的性能？

我正在学习数据结构和算法,这是一个我坚持的问题.

我必须通过将值存储到内存中来提高递归调用的性能.

但问题是非改进版本似乎比这更快.

有人可以帮我吗？

Syracuse数字是由以下规则定义的正整数序列：

syra(1)≡1

syra(n)≡nsyra(n / 2),如果n mod 2 == 0

syra(n)≡nsyra((n * 3)1),否则

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

}

解决方法

private Map<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的维基百科文章.

另外,我认为你误用了计数器变量,你在第一次计算值时增加它(),但是当你在地图中找到一个值时,你会累积它(=).这对我来说似乎不对,我怀疑它是否给出了预期的结果.

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!