Re: Perlの正規表現で文字列マッチを繰り返し判定する方法

Posted by
ぴろり
Posted at
2014/11/24 14:54
Trackbacks
関連記事 (0)
Post Comment
コメントできます
Category
開発メモ カテゴリ
カバーイメージ

$`$& の前方の文字列、$'$& の後方の文字列が保持される特殊変数です。よりエレガントな方法がありそうな気がしますがとりあえず。

 …ということで、連休中に少しコードを弄ってみた結果のまとめ。

この記事を Delicious に追加する   このエントリーをはてなブックマークに追加  

特定の回のみ置換する

#!/usr/bin/perl
use strict;
 
my $content = "123abc456abc789abc";
my $counter = 1;
while ( $content =~ /\d{3}/g ) {
    if ( $counter == 2 ) {
        $content =~ s/($`)$&($')/$1xyz$2/;
    }
    $counter++;
}
print $content;

 元のコード original.pl では、$`$' を用いて文字列全体に渡って置換が行われている( 8 行目)ため、動作パフォーマンスが気になるところ。そこで、e モディファイヤを利用したコードが sample.pl です。

#!/usr/bin/perl
use strict;

my $content = "123abc456abc789abc";
my $counter = 1;
$content =~ s/\d{3}/
    if( $counter++ == 2 ) {
        'xyz';
    } else {
        $&;
    }
/eg;
print $content;

 置換後の文字列を e モディファイヤを使用して、指定された回数目の置換処理( 7 行目)の時だけ、目的の文字列 xyz( 8 行目) を返しています。それ以外ではマッチした文字列($&)をそのまま返しており、マッチした部分がマッチした同じ文字列で置換されるため、結果、置換されていないように見えます。

動作パフォーマンスの計測

 対象の文字列長を変化させて動作パフォーマンスを計測してみました*1

#!/usr/bin/perl
use strict;
use Benchmark;

sub generate_content {
    join '', '123abc456abc789abc' x $_[0];
}

sub Original {
    my $content = generate_content( $_[0] );
    my $counter = 1;
    while ( $content =~ /\d{3}/g ) {
        if ( $counter++ % 2 ) {
            $content =~ s/($`)$&($')/$1xyz$2/;
        }
    }
}

sub MyCode {
    my $content = generate_content( $_[0] );
    my $counter = 1;
    $content =~ s/\d{3}/
        if ( $counter++ % 2 ) {
            'xyz';
        } else {
            $&;
        }
    /eg;
}

# http://search.cpan.org/~rjbs/perl-5.18.4/lib/Benchmark.pm
Benchmark::cmpthese( 100_000, {
    Original =>     sub { Original( 1 ); },
    MyCode =>       sub { MyCode( 1 ); },
});

Benchmark::cmpthese( 10000, {
    Original_10 =>  sub { Original( 10 ); },
    MyCode_10 =>    sub { MyCode( 10 ); },
});

Benchmark::cmpthese( 100, {
    Original_100 => sub { Original( 100 ); },
    MyCode_100 =>   sub { MyCode( 100 ); },
});

Benchmark::cmpthese( 100, {
    Original_50 =>  sub { Original( 50 ); },
    Original_100 => sub { Original( 100 ); },
    Original_500 => sub { Original( 500 ); },
});

Benchmark::cmpthese( 100, {
    MyCode_100 =>   sub { MyCode( 100 ); },
    MyCode_1K =>    sub { MyCode( 1_000 ); },
    MyCode_10K =>   sub { MyCode( 10_000 ); },
    MyCode_100K =>  sub { MyCode( 100_000 ); },
    MyCode_1M =>    sub { MyCode( 1_000_000 ); },
});

 元のコードから、奇数個目のマッチを置換する処理に置き換えました。それぞれの関数(OriginalMyCode)は、引数によって走査する文字列長さを違えることができます。文字列長さを変化させ、それぞれの置換処理に要する時間を計測した結果は次の通りです。


             Rate Original   MyCode
Original  42194/s       --     -78%
MyCode   188324/s     346%       --

               Rate Original_10   MyCode_10
Original_10  2195/s          --        -94%
MyCode_10   33784/s       1439%          --

               Rate Original_100   MyCode_100
Original_100 50.9/s           --         -99%
MyCode_100   6250/s       12187%           --

               Rate Original_500 Original_100  Original_50
Original_500 2.42/s           --         -95%         -99%
Original_100 51.3/s        2019%           --         -71%
Original_50   178/s        7253%         247%           --

               Rate   MyCode_1M MyCode_100K  MyCode_10K   MyCode_1K  MyCode_100
MyCode_1M   0.369/s          --        -90%        -99%       -100%       -100%
MyCode_100K  3.76/s        919%          --        -90%        -99%       -100%
MyCode_10K   38.2/s      10252%        916%          --        -90%        -99%
MyCode_1K     400/s     108427%      10552%        948%          --        -94%
MyCode_100   6250/s    1695631%     166338%      16281%       1463%          --
  • MyCode は、Original の 4 倍以上高速である。
  • MyCode は、文字列長さが n 倍になると、処理速度はほぼ n 倍悪化する。 ⇒ O(n)
  • Original は、文字列長さが n 倍になると、処理速度はほぼ n2 倍悪化する。 ⇒ O(n^2)
  • 走査する文字列長が長いほど、MyCode の方がより高速に動作する。
この記事を Delicious に追加する   このエントリーをはてなブックマークに追加  

  1. *1 環境は Core i7-860@2.80GHz + Windows 7 Ultimate 64bit + ActivePerl 5.16.3 32bit


関連記事/トラックバック

関連記事/トラックバックはまだありません

この記事にトラックバックを送るには?

コメントを投稿する

 
 (必須, 匿名可, 公開, トリップが使えます)
 (必須, 匿名可, 非公開, Gravatar に対応しています)
 (必須)
スパム コメント防止のため「投稿確認」欄に ランダムな数字 CAPTCHAについて を入力してから送信してください。お手数ですがご協力のほど宜しくお願いいたします。