帰ってきたネコブログ

次は、2つの方式の速度比較。

use strict;
use warnings;
use v5.10;
use Benchmark qw/cmpthese/;

die 'Usage: perl aaa.pl <integer>' if scalar(@ARGV) == 0;

my $max_num = $ARGV[0];
cmpthese( 10, {
    'calc1' => sub {
        my @prime = calc_prime1( $max_num );
    },
    'calc2' => sub {
        my @prime = calc_prime2( $max_num );
    }
} );

sub calc_prime1 {
    my $n = shift;

    my @ret = ();
    if ( $n < 2 ) {
        return @ret;
    }

    my @wk = 0..$n;
    $wk[0] = -1;
    $wk[1] = -1;

    for (my $i=0; $i<=$n; $i++) {
        next if $wk[$i] < 0;

        my $prime = $wk[$i];
        for (my $j=$i+1; $j<=$n; $j++) {
            next if $wk[$j] < 0;
            if ( ($wk[$j] % $prime) == 0 ) {
                $wk[$j] = -1;
            }
        }
    }

    return grep { $_ != -1; } @wk;
}

sub calc_prime2 {
    my $n = shift;

    my @ret = ();
    if ( $n < 2 ) {
        return @ret;
    }

    my @wk = 0..$n;
    $wk[0] = -1;
    $wk[1] = -1;

    for (my $i=0; $i<=$n; $i++) {
        next if $wk[$i] < 0;

        for (my $j=($i+$i); $j<=$n; $j+=$i) {
            $wk[$j] = -1;
        }
    }

    return grep { $_ != -1; } @wk;
}

実行結果はこんな感じ。

$ perl aaa.pl 10000
            (warning: too few iterations for a reliable count)
        s/iter  calc1  calc2
calc1     1.89     --   -99%
calc2 1.00e-02 18760%     --

分かってはいたんですけどね、体感で違い過ぎたので。
ただ、添え字でどうこうするのは、
大きな素数を計算するのには向かない気がするので、
その場合は時間が掛かってでも、
すでに見つかった素数で余りを計算する方が現実的な気がします。
でも、そこはSSDを使えば、もっと早く計算できたりするんですかね。

という訳で、素数の計算はここまで。

おしまい。

カテゴリー: Perl, コンピューター by ネコ on 2013年09月17日 | タグ: アルゴリズム > メモ > 素数