7

私はデータ構造とアルゴリズムを学んでいますが、これが私が立ち往生している質問です。

値をメモリに保存して、再帰呼び出しのパフォーマンスを改善する必要があります。

しかし問題は、改善されていないバージョンがこれよりも高速に見えることです。

誰かが私を助けることができますか？

シラキュース数は、次の規則によって定義される一連の正の整数です。

シラ(1) ≡ 1

syra( n ) ≡ n + syra( n /2)、n mod 2 == 0の場合

syra( n ) ≡ n + syra(( 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));
    }
}

FINAL SOLUTION (学校の自動採点システムで正しいと採点)

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

}

4

3 に答える 3

2

a を使用しているためにコードが非効率的であるという回答は忘れてください。Mapそれが遅くなる理由ではありません。計算された数値のキャッシュを に制限しているという事実ですn < 500。その制限を取り除くと、物事は非常に速く機能し始めます。詳細を記入するための概念実証は次のとおりです。

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

}

プログラムで何が起こっているのか、なぜそんなに速いのかについてもっと知りたい場合は、メモ化に関するこのウィキペディアの記事をご覧ください。

counterまた、変数を誤用していると思います。最初に値を計算するときに変数を増やしますが ( )、マップで値が見つかったときに++累積します ( )。+=それは私には正しくないように思われ、期待した結果が得られるとは思えません。

于 2012-06-04T21:21:13.727 に答える
-1

もちろん、うまくいきません。map.put と map.get の呼び出し (ハッシュ、バケットの作成など) に多くのオーバーヘッドが追加されます。さらに、オートボクシングを行っているため、オブジェクト作成の混乱が生じます。私の推測では、マップのオーバーヘッドがメリットをはるかに上回っています。

代わりに 2 つの配列を使用してみてください。1 つは値を保持し、値が設定されているかどうかを示すフラグを保持します。

int [] syr = new int[Integer.MAX_VALUE];
boolean [] syrcomputed = new boolean[Integer.MAX_VALUE];

マップの代わりにそれらを使用します。

if (syrcomputed[n]) {
   return syr[n];
}
else {
    syrcomputed[n] = true;
    syr[n] = ....;
}

また、ここで大きな数値でオーバーフローが発生する可能性があると思います (syr が MAX_INT/3 に近づくと、2 で割り切れない場合は間違いなくこれが表示されます)。

そのため、おそらくすべての計算にも long 型を使用する必要があります。

PS: 目的が本当に再帰を理解することである場合は、値をインスタンス変数として格納するのではなく、アキュムレータとして渡す必要があります。

public int syr(int n) {
  return syr(n, new int[Integer.MAX_VALUE], new boolean[Integer.MAX_VALUE]);
}

private int syr(int n, int[] syr, boolean[] syrcomputed) {
   if (syrcomputed[n]) {
     return syr[n];
   }
   else {
     s = [ block for recursive computation ]
     syrcomputed[n] = true;
     syr = s;
   }
}

一部の関数型言語 (scheme、erlang など...) では、これは実際にはテール コールとしてアンロールされます (スタックの作成を回避します)。ホットスポット jvm はこれを行いませんが (少なくとも私の知る限り)、それでも重要な概念です。

于 2012-06-04T17:44:40.373 に答える
-1

マップを使用しないでください。一時的な結果をフィールド (アキュムレータと呼ばれます) に格納し、n = 1 になるまでループで反復を実行します。各ループの後、アキュムレータは n ずつ大きくなります。各ループで、n は 3 倍 + 1 倍になるか、2 倍減少します。宿題を解決するのに役立つことを願っています

于 2012-06-04T16:21:08.823 に答える