Perlで早いプログラムを作りたい

質問

perlの初心者です。
一つの配列の構成要素が１００～１０００のものが１０００個ほどあります。
ある配列の一つの要素が他の配列に何個づつあるかを調べています。
作ったプログラムは次の三つですがとても遅く、もっと早い方法があれば
教えてください。
１．foreach $a(@hairetsu1){
　　　　$n=0;
　　　　foreach $b(@hairetsu2){
　　　　　　$n++ if $a =~ $b;
　　　　}
　　}
2. foreach $a(@hairetsu1){
　　　　$n=grep(/$a/,@hairetsu2);
　}
3. for($i=0;$i<length(@hairetsu1);$i++){
　　　$n=0;
　　　for($j=0;$j<length(@hairetsu2);$j++)
　　　　　$n++ if $hairetsu1($i) =~ $hairetsu2($j);
　　　}
　}
上が一番早く下に行くほど遅いですがあまり違いはありません。
よろしくお願いします。

回答No.2

nipotan · ベストアンサー

#1 の nipotan です。

> 「=~」「==」「eq」いずれも同じと思っていました。

これらの違いを正確に理解しないと、根本的に手を加えるたびに脳内に未曾有の混乱を招くだけです。
=~ は左辺スカラーを対象にパターンマッチングや置換に使う (正規表現)
== は左右の値が数値的に等しいかを比較する比較演算子 * (01 == 1) は True *
eq は左右の値が文字列的に等しいかを比較する比較演算子 * ("01" eq "1") は False *
基本なので「はじめての～」系の本をお読みになって理解を深めたほうがいいと思います。

> やっていることは@hairetsu1(asd,dfg,zxc・・・・これが100～1000続く）の配列
> が1000配列程度あって、たとえば@hairetsu1の要素dfgが@hairetsu2にあるかあれ
> ばいくつあるかということを調べたいのです。中身は数字ではありません。

あ、そういう事だったんですね。根本的に勘違いしていました。
ただ「あれば」というのを先に調べる為に、結局は配列要素全体から対象の存在をさらって調べることになるので、「あるというのがわかってるんだから端っからカウントを始めたほうが早い」と考えられます。

> ＞# 重複チェック用テンポラリハッシュを生成
>
> というのが使えそうですがよく理解できません。
> なぜハッシュを使うのかよくわかりませんが
>
> next if exists $tmp{$a};
>
> の$tmp{$a}は$aがあったら数えないで次にいくということですか
>
> $tmp{$a} = 1;
>
> これはなにをしているのですか。本からの理解ではkey　$a　の値は１
> となってしまいますが・・・・

これは、「チェックしたか否か」を見るためのフラグ (Flag) です。あるかないかのブール値 (Boolean) なので、値はなんでもいいです。一応ワタシの作ったのはフラグなので実際にカウントした数値 ($n) は入りません。別に入れてもいいんですが、質問文にある 1. 2. 3. は、それぞれ $n の値を全て上位のループのたびに Flush ($n = 0 したり $n に新規代入したり) しているので、「恐らくループ内で画面なりファイルなりに出力している部分があって、それを省略している」んだろうと思ってましたから、単純にワタシはフラグをつけていっただけです。別に 1 じゃなくても $n でも undef でもいいんです。exists を使ってるので「かつて、そのハッシュの key は定義されたことがあるか」というのをチェックしているだけです。ハッシュを使わないと (例えば配列を使ったりすると) 今まで定義したリストを総ざらいしてチェックさせないといけないので、ループの後半に行けば行くほど異様に時間がかかります。

例えば極端な例を挙げると、以下の配列で、

my @a = ('教えて！', '教えて！', '教えて！', '教えて！', '教えて！', 'goo');
my @b = ('教えて！', 'goo', 'OK', 'web', 'hello', 'world', 'good', 'morning');

@a と @b の要素をチェックするのに、上記のように @a に重複項目が沢山あった場合があったとして、

foreach my $a(@a){
:
:
foreach my $b(@b){ ... }
:
:
}

というループ構造を作ったとします。foreach my $a(@a){ ... } (以下、"外のループ" とする) のループブロック ( { と } とで囲まれた範囲をブロックといいます) が一度実行されるたびに、foreach my $b(@b){ ... } (以下、"内のループ" とする) のループ (ブロック内を 8 回ループする) が行われるのはわかりますよね。
外のループのブロック一度目に '教えて！' が比較対照となり、内のループのブロックが 8 回ループされます。外のループが二度目のループに入った時、比較対照が再度 '教えて！' なので、もう @b に何個あるのかの答え (1 個) はわかってるのにも関わらず、内のループが 8 回ループします。外のループのループが 6 回行われるので、内のループのブロック内部は、48 回実行されます。
あえて「既にチェックしたかどうか」を調べて、チェック済みなら内のループのブロックを通過させず、外のループを次に進めること…

# 重複チェック用テンポラリハッシュを生成
my %tmp = ();

# 外のループ (6 回実行される)
foreach my $a(@a){
# チェック済みかどうかの判別
next if exists $tmp{$a};

# どうせこれからチェックするのは確実なので、
# チェック済みをあらわすフラグ値を設定
# (別にチェック後でもいいが。。。)
$tmp{$a} = 1;

# 内のループ (8 回実行される)
foreach my $b(@b){ ... }
}

によって、内のループのブロック内部をトータルで 16 回しか実行されずに済みます。
なので重複がある場合は、こういう手段を使えば、内のループの処理回数や処理速度を節約できます。

ワタシが質問の意味を根本的に誤って解釈していたので、「重複がいくつかある可能性が高い」という場合に、こういう方策が使えますが、逆に「重複が殆どない可能性が高い」場合には、こういう方法もネックになる可能性もありますから、それは実データがどうなっているのかを理解されている場合に使われるといいと思います。

で、長々と説明してしまったので結論にいきますがこういったケース (文字列の数を配列内部からチェックする場合) には、配列を一旦ソートして、どっちの文字が文字 (コード) 的に上位 (例えば昇順ソートなら A は B より下) なのかを見たほうが早いです。なぜかというと、ソートした配列同士を比較する際、外のループが "XYZ" なのに、内のループでの比較対照が "ABC" であれば、違うのは当然の事、「かけ離れてすぎて比較する事自体が無駄」です。配列がソートされているので、内のループの先頭要素が "ABC" だったとして、次の要素が "DDD" だったとしたら、"XYZ" と比較させるには "DDD" から調べていったほうが上記無駄を省いているぶん、「まだ処理は早い」でしょう。
仮に内のループの配列要素の末尾から 3 番目ぐらいの要素が "XXX" だった場合 (比較対照が近似値だった場合)、ソートされている事を考えると、次の要素が "XYZ" かもしれないという期待が持てます。なら、末尾 3 番目から末尾 "XYZ" を超えない範囲を調べる (超えたら調べ終わる) という方法を取り、内のループを「最小のループ回数」で調べるという方法を使えば、格段に処理が早くなります。
これを一般的に「近似アルゴリズム」と呼びます。

---
# 両配列をソートする
@hairetsu1 = sort @hairetsu1;
@hairetsu2 = sort @hairetsu2;

# 外のループの前回合計値を求めた比較対照文字列を格納する変数を宣言
my $last;

# 合計値を格納する変数
my $n = 0;

# 前回合計値を格納する変数
my $lastn = 0;

# 外と内のループを複合する (外のループ用添字 $i, 内のループ用添字 $j)
# ブロック終了後の実行式はあえて書かない
for(my $i = 0, my $j = 0; $i < @hairetsu1; ){

# 今回の比較値が前回の比較値と同じだったら、調べる必要がないので
# 画面に出力後、次の比較値を取り出す
if($hairetsu1[$i] eq $last){
output($last, $lastn);
$i++;
next;
}

# 比較対照同士を、文字列的にどちらが上位かを調べる
# 同じなら 0、左辺が大きければ +1、右辺が大きければ -1 になる
my $diff = $hairetsu1[$i] cmp $hairetsu2[$j];

unless($diff){
# 同じだった場合の処理

# 合計値に加算
$n++;

# 添字加算し、内のループを次の比較値に移す
$j++;

# この時、内のループの要素数を超えた場合はこれ以上比較する対象がないので
# 画面に出力後、全ての比較処理を終了
# (外のループがまだ残ってる可能性があるので、画面出力用変数代入をして続ける)
if($j >= @hairetsu2){

# 今回の結果をひとまず出力
output($hairetsu1[$i], $n);

# 次のチェック値は今後チェックしないので、出力用に代入

# 現在の結果
$lastn = $n;

# 現在のチェック文字列
$last = $hairetsu1[$i];
}
}elsif($diff == 1){
# 左辺が大きかった場合の処理 (内のループが次に進みます)

# 右辺 (内のループ) は次の要素を比較するように内のループを次に進める
$j++;
}else{
# 右辺が大きかった場合の処理 (外のループが次に進みます)

# 右辺が大きくなったという事は、内のループを進める必要がないので、
# これ以上の合計加算処理がない。なので画面に出力
output($hairetsu1[$i], $n);

# 次のチェック値が今回と同じだった場合用に、"前回合計値" として、
# 現在の結果を $lastn に代入
$lastn = $n;

# 次のチェック値の合計をリセット
$n = 0;

# 次のチェック値と同じかを調べる為に、"前回対象文字列" を代入
$last = $hairetsu1[$i];

# 外のループを次に進める
$i++;
}
}

# (文字列, 合計数) を受けて画面上に出力するサブルーチン
sub output{
my($val, $sum) = @_;

# 別にファイルに出力しようが画面上に出そうがは自由なので、とりあえず
# 画面に出してみてます。
print $val.' は '.$sum.' 個ありました'."\n";
}
---

…ちょっとサンプリングしてみましたが、"仕様先行型" じゃなくて、"発展型" でコーディングしてその後コメントをつけたので、完全動作かどうかのテストはしてません。でもじっくりコードを追ってもらえればわかると思いますが、比較回数は「必要最小限」に抑えられているので、無駄なループ、無駄な比較が行われないようになってます。コメントを参考にしてこのコードを追ってみて、「近似アルゴリズム」の原理を研究して、お手元の環境に一番適した方法にカスタマイズし、動作確認してみてください。原理研究には十分役立つサンプルに仕上げられたかなと思います。

ちなみに、配列の順序通りに合計個数を表示したかったら、sort の際に配列のソートした後の順をインデックスとして別配列に順番で並べ、出力はバッファリング (他の配列に蓄えるとか) してインデックスに合わせて並べ替えて出力するようにすればいいと思います。上記 output サブルーチンをカスタマイズするとか、sort をカスタマイズ (自分で、数あるソートアルゴリズムのどれかを用いて、sort 結果と順番のインデックスを出す関数を作ったほうがいいと思います) すれば、そういう事も容易に行えます。

また、比較させるための配列が数多いとの事ですが (1000 配列もあるなら、何時間もかかってませんか？) その配列全体を、ループさせるためのループ構造を上記のチェック機構の上位につくらなければいけません。
それを実現するために、@hairetsu1 とか @hairetsu2 とかの変数を新たに作るのではなく、リファレンス (ハードリファレンス) や無名配列を用いる方法を知っておいたほうがいいかもしれません。

---
@hairetsu = (
['I', 'am', 'a', 'Japanese', 'Programmer'],
['You', 'are', 'an', 'American', 'Programmer'],
['He', 'is', 'a', 'Korean', 'Programmer']
);

print $hairetsu[2][3]; # 結果は Korean
---
@tmpA = ('I', 'am', 'a', 'Japanese', 'Programmer');
@tmpB = ('You', 'are', 'an', 'American', 'Programmer');
@tmpC = ('He', 'is', 'a', 'Korean', 'Programmer');
@hairetsu = (\@tmpA, \@tmpB, \@tmpC);

print $hairetsu[1][2]; # 結果は an
---

このような方法を用いれば

@allArray = (\@hairetsu1, \@hairetsu2, \@hairetsu3, .... \@hairetsu1000);
for(my $subscript = 0; $subscript < @allArray; $subscript++){ ... }

で、for ブロック内で一回目は、$allArray[$subscript] が @hairetsu1 の実体を指し、$allArray[$subscript + 1] が @hairetsu2 の実体を指します。
この方法は中級者レベルだと思うので、「はじめての～」系には載ってないかも知れませんが、知っておいて損は絶対にないです。

以上、超長くなりましたが、回答とアドバイス、ご理解いただけましたでしょうか。
# 自己最長回答間違いなし。

回答No.1

nipotan

根本的におかしいのは、
1. と 3. の数値比較が =~ である点、
2. は正規表現なので、$a が 100 の時、1000 もカウントに入れてしまうという点。
あと、3. ですが、$hairetsu1($i) のように、添字 (Subscript) は () で括らず、[] で括らないといけない (VB とは違うんで…)

なので、一応、一番まともな 1. なら
$n++ if $a == $b;
としたら、全然早さが違うと思います。

それと
> 一つの配列の構成要素が１００～１０００のものが１０００個ほどあります。
って事は、「100 ～ 1000 の数値が入った要素 1000 個が一つの配列」と考えればいいんでしょうか。もしそうなら、配列の中に、同じ数がいくつか重複しますよね。重複するって事は、二回目に「かつて個数を調べたやつをもう一度調べないといけない」って事になるので、その分処理が余計になります。

---
# 重複チェック用テンポラリハッシュを生成
my %tmp = ();
foreach my $a(@hairetsu1){
# 既にチェック済みなら次の要素へ
next if exists $tmp{$a};

$tmp{$a} = 1;
my $n = 0;
foreach my $b(@hairetsu2){
$n++ if $a == $b;
}
}
---
こうすることで、ある程度は早くなるはずです。

お礼

nipotan 様

懇切丁寧な且つ長文のご回答ありがとうございました。

ご教示いただいた方法「近似アルゴリズム」はすごいアイデア
と思います。これをまだよく理解できていませんが、理解すべく
苦戦中です。
まだまだ時間がかかりそうなので、とりあえず締め切って
どうしてもわからないところを質問しますのでよろしく
お願いします。

補足

早速のご回答ありがとうございました。
「=~」「==」「eq」いずれも同じと思っていました。再度やって見ると
「=~」では動かないようで、前にやったのは「==」を使用したようです。
（何遍も書き換えているのでよく覚えていない）
ただこれよりも早くしたいのですが・・・・

やっていることは@hairetsu1(asd,dfg,zxc・・・・これが100～1000続く）の配列
が1000配列程度あって、たとえば@hairetsu1の要素dfgが@hairetsu2にあるかあれ
ばいくつあるかということを調べたいのです。中身は数字ではありません。

@hairetsu1と@hairetsu2,@hairetsu3・・・@hairetsu1000で調べ次に@hairetsu2と@hairetsu3・・・@hairetsu1000、最後は@hairetsu999と@hairetsu1000を比較するということをしたいので、

＞# 重複チェック用テンポラリハッシュを生成

というのが使えそうですがよく理解できません。
なぜハッシュを使うのかよくわかりませんが

next if exists $tmp{$a};

の$tmp{$a}は$aがあったら数えないで次にいくということですか

$tmp{$a} = 1;

これはなにをしているのですか。本からの理解ではkey　$a　の値は１
となってしまいますが・・・・

わからないことが多くて恐縮ですがよろしくお願いします。