帰ってきたネコブログ

という訳で、最初の実装を高速化してみた。

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, {
    'before' => sub {
        my @prime = calc_prime1( $max_num );
    },
    'after' => sub {
        my @prime = calc_prime2( $max_num );
    }
} );

sub calc_prime1 {
    my $n = shift;

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

    my @wk = 2..$n;
    while ( @wk ) {
        my $prime = shift @wk;
        @wk = grep { ($_ % $prime); } @wk;
        push @ret, $prime;
    }

    return @ret;
}

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;

        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;
}

実行結果はこんな感じ。

$ perl aaa.pl 10000
       s/iter  after before
after    1.82     --   -88%
before  0.218   733%     --

うーん、grepしまくりが良くなかったのかなー。
もしくは、pushとか、shiftとか。
ここは憶測で語っても仕方ないので、こんな感じで。

という訳で、これで余りを計算しない方式と比較する準備ができました。

続く。

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