【perlメモ】配列の処理を改善したら処理がずいぶん早くなった件

Posted by kumacchi on 2010年10月4日 , No comment

下のような配列の処理をしてたプログラムを前に適当に書いたんですが

@list1 親配列

@list2 子配列

親配列のループで親の配列からキーを取り出して、子の配列のループで親のキーと子のキーが一致したら子のデータを連結していくというありがちな2重ループです。

これだと子の配列のデータがが多いととっても遅いんですね、親のループの回数分、子の配列のループを繰り返すわけですから、毎回子の配列を全部ナメるわけです。かなり無駄な処理が有ります。実際ほんとに遅かったんです。数分掛かるくらいに。

my $STR = ”;
foreach my $line1 (sort rank @list1){
my($key,$num) = split(/\t/,$line1);
$STR .= "$key\n";

    foreach my $line2(sort rank @list2){
        my($key2,$num2,$key3,$key4) = split(/\t/,$line2);
        next if($key ne $key2);
        $STR .= "$key3,$key4\n";
    }
}

sub rank{
my(undef,$n1) = split(/\t/,$a);
my(undef,$n2) = split(/\t/,$b);

    if($n1 > $n2){
        -1;
    }elsif($n1 < $n2){
        1;
    }else{
        0;
    }
}

自分なりに試行錯誤して下のように改善してみました。

あらかじめ子の配列(@list2)をキーごとに分類して、配列のハッシュにしてみたら分類の前処理は増えるけど後のループで全く無駄なループがなくなるのでほぼ一瞬で終わるようになった。

my %keyh =();
foreach my $list2 (@list2){
my($key2) = split(/\t/,$list2);
push(@{$keyh{"$key2"}},$list2);
}

my $STR = ”;
foreach my $list1 (sort rank @list1){
my($key,$num) = split(/\t/,$list1);

next unless(defined($keyh{"$key"}));

    foreach my $line2(sort rank @{$keyh{"$key2"}}){
        my($key2,$num2,$key3,$key4) = split(/\t/,$list2);
        next if($key ne $key2);
        $STR .= "$key3,$key4\n";
    }
}

sub rank{
my(undef,$n1) = split(/\t/,$a);
my(undef,$n2) = split(/\t/,$b);

    if($n1 > $n2){
        -1;
    }elsif($n1 < $n2){
        1;
    }else{
        0;
    }
}

元々の処理がアレだと言われるとそうなんですが、こうやって試行錯誤してちょっとした改善で処理が高速化するとうれしいしおもしろいですね。プログラミングの醍醐味というかたのしみというか。専門用語でリファクタリングと言うそうです。

(Visited 578 times, 1 visits today)

タグ : perl, perlメモ