このJavaスニペットをより効率的にするにはどうすればよいですか？

Question

コンピュータコンテストでは、入力データを操作しなければならないという問題が発生しました。入力は、data（0）が繰り返しの数である配列にsplit（）されています。最大10^18回の繰り返しがあります。私のプログラムはException in thread "main" java.lang.OutOfMemoryError: Java heap spaceを返し、私はコンテストに失敗しました。ここで

は、メモリとCPUを食べている私のコードの一部です：私のプログラムはたったの約7または8桁まで働くことができる

980046644627629799 9 123456 18 10000000 831918484 451864686 840000324 650000765 
972766173386786486 123 1 10000000 10000000 590000001 680000000 610000001 970000002 
299896237124947938 681206 164538 2280874 981991 416793690 904023823 813682336 774801135 

：

long product[][]=new long[data[0]][2]; 
product[0][0]=data[1]; 
product[0][1]=data[2]; 
for(int a=1;a<data[0];a++){ 
    product[a][0]=((data[5]*product[a-1][0] + data[6]) % data[3]) + 1; // Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N) 
    product[a][1]=((data[7]*product[a-1][1] + data[8]) % data[4]) + 1; // Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N) 
} 

は、ここで入力されたデータの一部です実行するには数分かかります。 18桁の数字で、Eclipseで「Run」をクリックするとすぐにクラッシュしました。

通常のコンピュータでそのように多くのデータを操作することが可能なのかどうか不思議です。私の質問が不明であるか、より多くの情報が必要な場合はお知らせください。ありがとう！

Answer 1

このような巨大な長さの配列を持つことはできません。直近の2つの値をトラッキングするだけです。たとえば、商品1と商品2があります。

また、いずれかの数値が各反復後にNaNであるかどうかを調べることを検討してください。その場合は、例外をスローして反復番号を与えます。 NaNを取得すると、すべてNaNになります。あなたが長いことを使用していることを除いて、それを傷つける。 "気にしないで"。 :-)

Answer 2

long product[][]=new long[data[0]][2]; 

これは、メモリを割り当てるコードの唯一の行です。長さがdata[0]の配列を割り当てます。データが大きくなると、配列も大きくなります。ここで適用しようとしている式は何ですか？

あなたが提供する最初の入力データ：

980046644627629799 

はすでにさえの配列を宣言するには大きすぎます。それを長さにして1次元の配列を作成し、何が起こるかを見てみてください。

あなたが累積する1×2の行列は欲しいのですか？あなたの意図したアルゴリズムを明確に説明し、より最適なソリューションをお手伝いします。

Answer 3

数字を見てみましょう。

メモリ：1つのlongは8バイトかかります。 10 longs take 16,000,000テラバイト。あまりにも多く。

時間：10,000,000回≈1秒。 10 ステップ≈30世紀。あまりにも多くの方法です。

はあなたが唯一の任意の時点での最新の値を必要とすることを実現することにより、メモリの問題を解決することができ、全体のアレイは冗長であること：

long currentP = data[1]; 
long currentW = data[2]; 
for (int a = 1; a < data[0]; a++) 
{ 
    currentP = ((data[5] * currentP + data[6]) % data[3]) + 1; 
    currentW = ((data[7] * currentW + data[8]) % data[4]) + 1; 
} 

時間の問題が解決することは少しトリッキーです。モジュラスが使用されているので、数値はある時点でサイクルに入る必要があることがわかります。サイクルを見つけたら、各反復を手動で行う必要なしに、n回の反復後に値がどのようになるかを予測できます。

サイクルを見つける最も簡単な方法は、各要素を訪問したかどうかを追跡し、以前に見た要素に遭遇するまで続きます。この場合、必要なメモリ量はMとK（データ[3]とデータ[4]）に比例します。それらが大きすぎる場合は、よりスペース効率のよいサイクル検出アルゴリズムを使用する必要があります。ここで

は、Pの値を見つける例です。

public static void main(String[] args) 
{ 
    // value = (A * prevValue + B) % M + 1 

    final long NOT_SEEN = -1; // the code used for values not visited before 

    long[] data = { 980046644627629799L, 9, 123456, 18, 10000000, 831918484, 451864686, 840000324, 650000765 }; 
    long N = data[0]; // the number of iterations 
    long S = data[1]; // the initial value of the sequence 
    long M = data[3]; // the modulus divisor 
    long A = data[5]; // muliply by this 
    long B = data[6]; // add this 
    int max = (int) Math.max(M, S);  // all the numbers (except first) must be less than or equal to M 
    long[] seenTime = new long[max + 1]; // whether or not a value was seen and how many iterations it took 

    // initialize the values of 'seenTime' to 'not seen' 
    for (int i = 0; i < seenTime.length; i++) 
    { 
     seenTime[i] = NOT_SEEN; 
    } 

    // find the cycle 
    long count = 0; 
    long cycleValue = S; // the current value in the series 
    while (seenTime[(int)cycleValue] == NOT_SEEN) 
    { 
     seenTime[(int)cycleValue] = count; 
     cycleValue = (A * cycleValue + B) % M + 1; 
     count++; 
    } 

    long cycleLength = count - seenTime[(int)cycleValue]; 
    long cycleOffset = seenTime[(int)cycleValue]; 

    long result; 

    if (N < cycleOffset) 
    { 
     // Special case: requested iteration occurs before the cycle starts 
     // Straightforward simulation 
     long value = S; 
     for (long i = 0; i < N; i++) 
     { 
      value = (A * value + B) % M + 1; 
     } 
     result = value; 
    } 
    else 
    { 
     // Normal case: requested iteration occurs inside the cycle 
     // Simulate just the relevant part of one cycle 
     long positionInCycle = (N - cycleOffset) % cycleLength; 
     long value = cycleValue; 
     for (long i = 0; i < positionInCycle; i++) 
     { 
      value = (A * value + B) % M + 1; 
     } 
     result = value; 
    } 

    System.out.println(result); 
} 

コンテストが終わったように見えるので、私は唯一のあなたに解決策を与えています。このことから学ぶ重要な教訓は、コーディングを開始する前に、ソリューションが実用的であるかどうかを常に確認することです。