4

私はここ数日間 (数学的な観点よりもアルゴリズム的な観点から)、与えられた数のヘイルストーン シーケンス (コラッツ予想) の長さを調査することに特に興味を持っていました。再帰アルゴリズムを実装することは、おそらく長さを計算する最も簡単な方法ですが、計算時間を不必要に浪費しているように思えました。多くのシーケンスが重複しています。たとえば、3 の Hailstone シーケンスを考えてみましょう:

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

これは長さ 7 です。より具体的には、1 に到達するのに 7 回の操作が必要です。次に 6 回かかる場合:

6 -> 3 -> ...

これはすでに計算済みであることがすぐにわかります。そのため、これらすべての数値を再度実行する代わりに、シーケンス長 3 を追加するだけで、各数値のシーケンス長を計算するために必要な操作の数が大幅に削減されます。

HashMap を使用して Java でこれを実装しようとしました (O(1) の確率的な get/put の複雑さを考えると適切なようです)。

import java.util.HashMap;

/* NOTE: cache.put(1,0); is called in main to act as the
 * 'base case' of sorts. 
 */

private static HashMap<Long, Long> cache = new HashMap<>();

/* Returns length of sequence, pulling prerecorded value from
 * from cache whenever possible, and saving unrecorded values
 * to the cache.
 */
static long seqLen(long n) {
    long count = 0, m = n;
    while (true) {
        if (cache.containsKey(n)) {
            count += cache.get(n);
            cache.put(m, count);
            return count;
        }
        else if (n % 2 == 0) {
            n /= 2;
        }
        else {
            n = 3*n + 1;
        }
        count++;
    }
}

基本的に行うことseqLenは、指定された数値で開始し、その数値の Hailstone シーケンスを に既にある数値に遭遇するまで処理することcacheです。その場合、その数値を の現在の値に追加しcount、値と関連するシーケンスをログに記録します。(key,val)ペアとしての HashMap の長さ。

比較のために、次のかなり標準的な再帰アルゴリズムも用意しました。

static long recSeqLen(long n) {
    if (n == 1) {
        return 0;
    }
    else if (n % 2 == 0) {
        return 1 + recSeqLen(n / 2);
    }
    else return 1 + recSeqLen(3*n + 1);
}

ロギング アルゴリズムは、単純な再帰的方法よりもかなり高速に実行されるはずです。ただし、ほとんどの場合、それほど速くは実行されず、入力が大きい場合は実際には遅くなります。n次のコードを実行すると、変更のサイズに応じて大幅に異なる時間が得られます。

long n = ... // However many numbers I want to calculate sequence
             // lengths for.

long st = System.nanoTime();
// Iterative logging algorithm
for (long i = 2; i < n; i++) {
    seqLen(i);
}
long et = System.nanoTime();
System.out.printf("HashMap algorithm: %d ms\n", (et - st) / 1000000);

st = System.nanoTime();
// Using recursion without logging values:
for (long i = 2; i < n; i++) {
    recSeqLen(i);
}
et = System.nanoTime();
System.out.printf("Recusive non-logging algorithm: %d ms\n",
                    (et - st) / 1000000);
  • n = 1,000: 両方のアルゴリズムで ~2ms
  • n = 100,000: 反復ロギングの場合は最大 65 ミリ秒、再帰的非ロギングの場合は最大 75 ミリ秒
  • n = 1,000,000: ~500ms および ~900ms
  • n = 10,000,000: ~14,000ms および ~10,000ms

値を大きくするとメモリ エラーが発生するため、パターンが継続しているかどうかを確認できません。

私の質問は、n の値が大きい場合に、ロギング アルゴリズムが単純な再帰アルゴリズムよりも突然時間がかかり始めるのはなぜですか?

編集：

HashMap を完全に破棄し、単純な配列構造を選択すると (値が配列内にあるかどうかをチェックするオーバーヘッドの一部を削除するだけでなく)、目的の効率が得られます。

private static final int CACHE_SIZE = 80000000;
private static long[] cache = new long[CACHE_SIZE];

static long seqLen(long n) {
    int count = 0;
    long m = n;

    do {
        if (n % 2 == 0) {
            n /= 2;
        }
        else {
            n = 3*n + 1;
        }
        count++;
    } while (n > m);

    count += cache[(int)n];
    cache[(int)m] = count;
    return count;
}

再帰アルゴリズムを使用すると 93 秒かかるのに対し、キャッシュ サイズ全体 (8000 万) の反復処理はわずか 3 秒で完了します。HashMap アルゴリズムはメモリ エラーをスローするため、比較することもできませんが、より低い値での動作を考えると、うまく比較できないと感じています。

4

1 に答える 1

1

簡単に言うと、ハッシュ マップの再割り当てに多くの時間を費やしていると思います。空から始めて、何かを追加し続けているようです。つまり、サイズが大きくなると、データを格納するために大きなメモリ チャンクを割り当て、すべての要素のハッシュ (O(N)) を再計算する必要があります。そこに入れると予想されるサイズに事前に割り当ててみてください。詳細については、 https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.htmlを参照してください。

于 2015-10-29T02:35:35.653 に答える