3

私はコラッツシーケンスに取り組んでいます。現在、forループがあります。

for my $num (1..1000000) {
    my $count = 1;
    for (my $i = $num; $i != 1; $count++) {
        $i = $i % 2 ? 3 * $i + 1 : $i / 2;
    }
}

そして、ループの回数 (理論を完成させるのに何回かかるか) を計算する簡単な方法があります。

if ($count > $max_length) {
    $max = $num;
    $max_length = $count;
}

簡単な理論を使って、コードをより速く作成できることを突き止めました。

n = 3 の場合、このシーケンスは {3,10,5,16,8,4,2,1} になります [8] n = 6 の場合、このシーケンスは {6,3,10,5,16 になります。 ,8,4,2,1} [9] n = 12 の場合、このシーケンスは {12,6,3,10,5,16,8,4,2,1} [10] になります。

したがって、3 の結果を保存し、カウントに 1 を追加するだけで 6 の結果を計算できるようにしたいと考えています。

私はこれに対処しようとしましたが、実際にはプログラムが完了するのに1分長くかかりました.以前の30秒ではなく1.49秒かかるプログラムがあります.

これは私がキャッシュを追加した方法です（おそらく間違っています）

以下はforループの外側です

my $cache = 0;
my $lengthcache = 0;

次に、for ループの $i 行の 4 行目の後にあるこのコードのビットがあります。

    $cache = $i;
    $lengthcache = $count;
    if  ($cache = $num*2) {
            $lengthcache++;
    }

コードを遅くすることなく正しくキャッシュする方法を理解する必要があるだけです。

4

3 に答える 3

1

アルゴリズムを変更して結果をキャッシュし、早期に発生できるようにします。

use strict;
use warnings;

my @steps = (0,0);
my $max_steps = 0;
my $max_num = 0;

for my $num (2..1_000_000) {
    my $count = 0;
    my $i = $num;
    while ($i >= $num) {
        $i = $i % 2 ? 3 * $i + 1 : $i / 2;
        $count++;
    }
    $count += $steps[$i];
    $steps[$num] = $count;

    if ($max_steps < $count) {
        $max_steps = $count;
        $max_num = $num;
    }
}

print "$max_num takes $max_steps steps\n";

処理時間が 37 秒から 2.5 秒に変わります。

2.5 秒で十分な改善が得られるのはなぜですか?

からまで@stepsのすべての整数の処理が配列のインデックスと簡単に一致するため、配列でのキャッシュを選択しました。これは、同じデータを保持するハッシュでvsのハッシュを使用するよりもメモリの利点も提供します。1N33M96M

指摘したようikegamiに、これは 100 万を超えるサイクルのすべての値をキャッシュできないことを意味します。たとえば、数704,511には までのサイクルがあります56,991,483,520。

最終的に、これは私の方法が特定のサイクルの一部を再計算することを意味しますが、すべてのステップでキャッシュをチェックする必要がないため、全体的には速度が向上します。これをサイクルごとにハッシュとキャッシュを使用するように変更すると、速度が に低下し9.2secsます。

my %steps = (1 => 0);

for my $num (2..1_000_000) {
    my @i = $num;
    while (! defined $steps{$i[-1]}) {
        push @i, $i[-1] % 2 ? 3 * $i[-1] + 1 : $i[-1] / 2;
    }
    my $count = $steps{pop @i};
    $steps{pop @i} = ++$count while (@i);
    #...

memoizeで示したように使用するOesorと、速度は23secsです。

于 2014-05-21T22:36:22.857 に答える
0

実装を再帰関数に変更する場合は、Memoize ( https://metacpan.org/pod/Memoize ) でラップして、計算済みの応答を高速化できます。

use strict;
use warnings;
use feature qw/say/;
use Data::Printer;

use Memoize;

memoize('collatz');

for my $num (qw/3 6 12 1/) {
    my @series = collatz($num);
    p(@series);
    say "$num : " . scalar @series;
}

sub collatz {
    my($i) = @_;

    return $i if $i == 1;
    return ($i, collatz( $i % 2 ? 3 * $i + 1 : $i / 2 ));
}

出力

[
    [0] 3,
    [1] 10,
    [2] 5,
    [3] 16,
    [4] 8,
    [5] 4,
    [6] 2,
    [7] 1
]
3 : 8
[
    [0] 6,
    [1] 3,
    [2] 10,
    [3] 5,
    [4] 16,
    [5] 8,
    [6] 4,
    [7] 2,
    [8] 1
]
6 : 9
[
    [0] 12,
    [1] 6,
    [2] 3,
    [3] 10,
    [4] 5,
    [5] 16,
    [6] 8,
    [7] 4,
    [8] 2,
    [9] 1
]
12 : 10
[
    [0] 1
]
1 : 1
于 2014-05-21T20:54:14.253 に答える