行単位のデータ比較とカウントアップ方法について

質問

皆様のお知恵を拝借したく投稿しました。
よろしくお願いします。

perlでのデータ処理で２つの入力ファイルがあります

list1 list2
----------------- ------------------
start end start end
1 10 6 8
12 16 7 14
20 30 35 39
34 42 41 47
80 89
110 130
----------------- ------------------

この2つのファイルを比較して以下の処理を行ないます
(1)list1から見たlist2の1行目を比較し、領域の重複が見られたら両方にフラグを立てる
→この場合領域6 - 8で重複が見られる
(2)両方の終点を比較し、終点値の小さい方をカウントアップ（次の行へ進む）
→1行目の場合、list2の終点が小さいのでlist2の行を進める
(3)list1の1行目とlist2の2行目を比較する
(4)終点を比較して終点の小さい方の行をカウントアップする
→以下(1)～(4)の行程を繰り返す。
(5)上例を比較の流れは以下のとおりになります
list1 1-10 , list2 6-8
list1 1-10 , list2 7-14
list1 12-16 , list2 7-14
list1 12-16 , list2 35-39
list1 20-30 , list2 35-39
list1 34-42 , list2 35-39
list1 34-42 , list2 41-47
list1 80-89 , list2 41-47
list1 110-130 , list2 41-47（行数が足りなくなったらlist2の最後の行と比較する）

最終的にlist1,list2の重複のあるフラグ数をカウント、出力する
と言うアルゴリズムです

コーディングの流れとしては
(1)双方の二次元配列をループで回す
(2)始点に注目して重複がないか比較する
(3)終点を比較して該当するリストの行数のカウントアップをする
というふうになると思うのですが、

(3)のやり方と、最後の片方のリストの行数が足りなくなったときの
比較とカウントアップのやり方がよく実装できません

これをperlでコーディングしたいのですが
どのようにしたらよいのでしょうか？

ご助言いただけますと幸いです

回答No.3

kumoz · ベストアンサー

質問者が考えられているプログラムには、無理があると思います。

my @list1 = ([1,6],[2,5],[3,4],[5,14],[20,25]);
my @list2 = ([2,3],[5,8],[12,20],[16,28]);

while($i < @list1){
while($n < @list2){
.....
#終点の比較
if($list1[$i]->[1] < $list2[$n]->[1]){
$i++;
}
elsif($list2[$n]->[1] < $list1[$i]->[1]){
$n++;
}
}
}

上のプログラムでは、次のように進みます。
1) 1 - 6 と 2 - 3 を比較する
2) 1 - 6 と 5 - 8 を比較する
3) 2 - 5 と 5 - 8 を比較する
この時点で、list2 の 2 - 3 の比較は終了していて、本来比較しなければならない list1
の 2 - 5 と 3 - 4 とは行われないままになってしまいます。これを行うように while ル
ープに組み込むのは、至難の技のように思います。

次の条件式 (elsif の条件式も含めて) には誤りがあります。1 - 6 と 12 - 20 を比較した
場合を考えてみてください。重複がないのに条件式は真となってしまいます。

#重複か否かの比較
if($list1[$i]->[0] < $list2[$n]->[0] && $list1[$i]->[1] < $list2[$n]->[1] ){

重複の判断は、どちらかの最小値 (または最大値) が他方の範囲内にあることを確認すること
でできます。

if ($list1[$i]->[0] >= $list2[$n]->[0] && $list1[$i]->[0] <= $list2[$n]->[1]
or $list1[$n]->[0] >= $list2[$i]->[0] && $list1[$n]->[0] <= $list2[$i]->[1]) {

もう少し単純なプログラムを考えてはどうでしょうか。次のような foreach の２段重ねる
方法でも十分ではないでしょうか。

my @list1 = ([1,6],[2,5],[3,4],[5,14],[20,25]);
my @list2 = ([2,3],[5,8],[12,20],[16,28]);
my $flag1 = 0;
my $flag2 = 0;

foreach my $list1_ref (@list1) {
foreach my $list2_ref (@list2) {
if ($list1_ref->[0] >= $list2_ref->[0] && $list1_ref->[0] <= $list2_ref->[1]
or $list2_ref->[0] >= $list1_ref->[0] && $list2_ref->[0] <= $list1_ref->[1]) {
$flag1++;
$flag2++;
}
}
}

print "list1 : $flag1\n";
print "list2 : $flag2\n";

お礼

ありがとうございます。
ソースが出来ましたので報告します。
下記は配列からそれぞれの配列データの比較の順番を
リストアップしたものを作成します。

その後、リストアップしたファイルを重複判断&フラグ付けする
プログラムに入力し、最終的にlist1,list2の重複のあるフラグ数をカウント、出力させます。

my $i = 0;
my $s = 0;
my @s_index;
my @i_index;
my @oList1 = ([1,6],[2,5],[3,4],[5,14],[20,25]);
my @oList2 = ([2,3],[5,8],[12,20],[16,28]);

while(($i < $#oList1 || $s <= $#oList2)&&($i <= $#oList1 || $s < $#oList2)){
my $ra1 = $oList1[$i]->[0];
my $ra2 = $oList1[$i]->[1];
my $ra3 = $oList2[$s]->[0];
my $ra4 = $oList2[$s]->[1];

### 片方の行が終わって、片方の行が残っている場合、リストの最後の行と残りの行で比較を行う
if($i == $#oList1)
{
if($s <= $#oList1 && $#oList1 <= $#oList2){
$s++;
}
elsif($s >= $#oList1 && $s <= $#oList2){
$s++;
}
elsif($s <= $#oList1 && $#oList2 <= $#oList1){
$s++;
}
else{
exit;
}
}
elsif($s == $#oList2)
{
　　上と同じ処理
}
else{
if($ra2 < $ra4)
{
### 終点同士を比較して、終点の値が小さい方の行をカウントアップ
$i++;
}
elsif($ra2 > $ra4)
{
　　　　上と同じ処理
}
}
}

回答No.2

kumoz

質問の意味がもう１つはっきりしないので、具体的な出力例を示してもらわないと回答するのが難しいと思います。

> (1)双方の二次元配列をループで回す
のように書かれていますが、ケースによってはうまく行かないように思います。

list1　　list2
1 - 10　 6 - 8
8 - 16　 7 - 14
...

仮にリストが上のようになっている場合、双方の２番目が他方の１、２番目と重複しているので順番に進めるのは
不可能になってしまいます。

補足

スケルトンコードです。
ループ内はまだ実装できていません。
すみません。

#list1の配列
my @list1 = ([1,6],[2,5],[3,4],[5,14],[20,25]);

#list2の配列
my @list2 = ([2,3],[5,8],[12,20],[16,28]);

#各リストの重複した場合のフラグ
my $flag1 = 0;
my $flag2 = 0;

#ループ
#各listの行
my $i = 0;
my $n = 0;

while($i < @list1){
while($n < @list2){
#重複か否かの比較
if($list1[$i]->[0] < $list2[$n]->[0] && $list1[$i]->[1] < $list2[$n]->[1] ){
$flag1++;
$flag2++;
}
elsif($list2[$n]->[0] < $list1[$i]->[0] && $list2[$n]->[1] < $list1[$i]->[1] ){
$flag1++;
$flag2++;
}
elsif($list1[$i]->[0] < $list2[$n]->[0] && $list2[$n]->[1] < $list1[$i]->[1]){
$flag1++;
$flag2++;
}
elsif($list2[$n]->[0] < $list1[$i]->[0] && $list1[$i]->[1] < $list2[$n]->[1]){
$flag1++;
$flag2
}
:
:
#終点の比較
if($list1[$i]->[1] < $list2[$n]->[1]){
$i++;
}
elsif($list2[$n]->[1] < $list1[$i]->[1]){
$n++;
}

#以下上記の処理を繰り返す？

}
}

print "list1 : $flag1\n";
print "list2 : $flag2\n";

申し訳ございません。
よろしくお願いします

回答No.1

sakusaker7

前回の補足要求には答えてもらえずじまいでしたけど、相変わらずですね。
ここまで作ったけどうまくいかないスクリプトを提示する位しても罰は当たらないんじゃないですか?
#出せるならという話ですけどね :)

今回も

Perl | 質問トピック (2)
http://mixi.jp/view_bbs.pl?id=11976536&comment_count=823&comm_id=836

で訊いたらどうですか?