0

プロジェクト オイラーの問題 14 に取り組んでいますが、何が問題なのかわかりません。プログラムを約 8 秒間実行した後も実行時エラーが発生し続けます。おそらく ArrayList が大きくなりすぎているのでしょうが、これを回避するにはどうすればよいですか?

import java.util.ArrayList;

public class Problem14 
{
    public static void main(String[] args) 
    {

        ArrayList<ArrayList<Long>>listOfLists=new ArrayList<ArrayList<Long>>();

        for (long c=2; c<1000000; c++)
        {
            ArrayList<Long>tempList=new ArrayList<Long>();
            long h=c;
            while (h!=1)
            {
                tempList.add(h);
                if (h%2==0)
                    h/=2;
                else
                    h=((3*h)+1);
            }
            tempList.add(1l);
            listOfLists.add(tempList);
        }

        long maxLength=0;
        long maxPos=0;

        for (int currList=0; currList<listOfLists.size(); currList++)
        {
            long currLength=(listOfLists.get(currList).size());
            if(currLength>maxLength)
            {
                maxLength=currLength;
                maxPos=currList+1;
            }
        }
        System.out.println("The longest sequence is "+maxLength+" numbers
                long. Its position is "+maxPos);
    }
}
4

5 に答える 5

4

使用可能なヒープ メモリを使い切って JVM を実行しました。問題の行は

ArrayList<Long>tempList=new ArrayList<Long>();

これは、100 万回実行されて保持されるループの内部にあるため、100 万個の配列リストを作成したことになります。-Xmx を使用する場合は、データ構造を改善するか、メモリを増やす必要があります。

Euler プロジェクトの精神では、リストのリストを回避する方法を探す必要があります。

于 2012-12-19T18:49:52.033 に答える
1

リストのリストは必要ありません。リストすら必要ありません。

内部リストを見ると、すべての値を追加してから、使用するのは size() だけです。これは、ループが繰り返された回数、つまりカウンターで本当に必要なすべてを意味します。これをリストとして保存できますが..

すべての長さが決定されたら、リストで行うことは、最大のものを見つけることだけです。長さをリストに保存する代わりに、最大のものだけを記録することができます。

これは、List Of Long オブジェクトの List を使用する代わりに、必要なのはこれまでの反復の最大数と開始値であったことを意味します。

これらの変更を行ったら、コードをさらに最適化できます。

于 2012-12-19T20:02:57.563 に答える
0

-Xmx パラメータを使用して JVM メモリを増やします。

于 2012-12-19T18:48:19.737 に答える
0

問題定義によるいくつかの考え:

まず第一に、番号のすべてのチェーンを保存する必要はありません。つまり、リストのリストはまったく必要ありません。それが生成する数とチェーンの長さを保存するだけです。最大のために。大量のリストではなく、2 つの整数だけです。

ちなみに、すでに計算されたシーケンスの長さを節約するためにキャッシュを追加できます。たとえば、 Map は生成されるチェーンの数と長さで構成されます。そのため、アルゴリズムを書き換えて、1 つの数値のチェーンの長さを計算する前に、そのキャッシュが存在するかどうかを確認します。それは多くの時間を節約します。

于 2012-12-19T18:59:06.990 に答える
-1

コマンドラインでコーディングしていないことを前提としています。単純に -Xmx パラメーター (および数値) を使用している場合は機能します... そうでない場合は、Eclipse でそのような引数を追加できます。プロジェクトを実行するクラスを右クリックし、「run as」に移動してから「run configuration」に移動します

そこに「arguments」タグが表示されます...そこに-Xmxタグを数字で追加します

-Xmx 2048

うまくいくかもしれません...頑張ってください

于 2012-12-19T19:34:46.927 に答える