0

私は、数のリストが与えられた場合、データリストで確立された三角形の数と数が持つ隣接の最小数との比率によって与えられる係数を計算しなければならないアルゴリズムを研究しようとしています。たとえば、ファイルの最初の2行が与えられた場合：

1 2 3 4 5 6 9
2 1 3
...
  1. 行の最初の要素が他の行に表示され、後続の行の最初の要素が試験で取得された行に表示される場合、リンクが見つかりました。
  2. 「リンク」が存在する場合は、試験で取得した行の他の要素がリンクが存在する行に表示される回数を数え、「z個の三角形が見つかりました」と出力します。

たとえば、この場合、プログラムが最初の行と2番目の行を比較し、「リンク1 2」が存在し、頂点1、2、3によって作成された三角形が1つあることを確認します。アルゴリズムでは、三角形の数+1を各行の要素の最小数-2で割る必要があります（この場合、最小数は2行目からのもので、値は3-2 = 1です）。私が探している係数は、（1 + 1）/ 1=2です。

出力ファイルは次のように書き込まれます。

1 2 1

最初の2列にはリンクを作成する要素があり、3列目には係数の値があります。

これまでに書いたコードは次のとおりです。

use strict;
use warnings;
use 5.010;
use List::Util;

my $filename = "data";
open my $fh, '<', $filename or die "Cannot open $filename: $!";

my $output_file = "output_example";
open my $fi, ">", $output_file or die "Error during $output_file opening: $!";

my %vector;
while (<$fh>) {
    my @fields = split;
    my $root = shift @fields;
    $vector{$root} = { map { $_ => 1} @fields };
}

my @roots = sort { $a <=> $b } keys %vector;
for my $i (0 .. $#roots) {
    my $aa = $roots[$i];
    my $n_element_a = scalar (keys %{$vector{$aa}})-1;

    for my $j ($i+1 .. $#roots) {
        my $minimum;
        my $bb = $roots[$j];
        my $n_element_b = scalar (keys %{$vector{$bb}})-1;
        next unless $vector{$aa}{$bb} and $vector{$bb}{$aa};
        if ($n_element_a < $n_element_b){
            $minimum = $n_element_a;
        }else {
            $minimum = $n_element_b;
        }

        my $triangles = 0;
        for my $cc ( keys %{$vector{$aa}} ) {
            next if $cc == $aa or $cc == $bb;
            if ($vector{$bb}{$cc}) {
                $triangles++;
            }
        }

        my $coeff;
        my @minimum_list;           
        if ($minimum == 0){
            $coeff = ($triangles +1)/($minimum+0.00000000001);
        } else {
            $coeff = ($triangles +1)/($minimum);
        }
        say $fi "$aa $bb $coeff";
    }
}
__DATA__
1 2 3 4 5 6 9
2 1 3
3 1 2
4 1 5
5 1 4
6 1 7 8
8 6 7
9 1 10 11
10 9 11 12 14
11 9 10 12 13
12 10 13 14
13 11 12
14 10 12 15
15 14

データセット全体を最後に配置します。出力ファイルは次のようになります。

__OUTPUT__
1 2 2
1 3 2
1 4 2
1 5 2
1 6 0.5
1 9 0.5
2 3 2
4 5 2
6 8 2
9 10 1
9 11 1
10 11 1
10 12 1
10 14 1
11 13 2
12 13 1
12 14 1
14 15 100000000000

ここで、係数の最小値を見つけ、この低い値を示すリンクを特定し、元のデータセットのこの要素を消去して、「新しい」データセットで同じプログラムを繰り返します。

たとえば、この場合、最小値を示すリンクは1 6、1 9係数が。のとです0.5。したがって、プログラムはファイルデータ内で「1」で始まる行の要素「6」を削除する必要があります。その逆も同様です。したがって、「新しい」データセットは次のようになります。

1 2 3 4 5
2 1 3
3 1 2
4 1 5
5 1 4
6 7 8
8 6 7
9 10 11
10 9 11 12 14
11 9 10 12 13
12 10 13 14
13 11 12
14 10 12 15
15 14

私が探しているのは：

  1. ファイルに含まれているデータセットから最小係数の値を示す要素を消去するにはどうすればよいdataですか？

  2. プロセスをN回繰り返すにはどうすればよいですか？

出力ファイルから最小値を見つけるために、プログラムの最後に次の行を追加しようと思いました。

my $file1 = "output_example";
open my $fg,  "<", $file1 or die "Error during $file1 opening: $!";

my @minimum_vector;
while (<$fg>) {
    push @minimum_vector, [ split ];
}

my $minima=$minimum_vector[0][2];
for my $i (0 .. $#minimum_vector){
    if($minima >= $minimum_vector[$i][2] ){
        $minima=$minimum_vector[$i][2];
    }
}
say $minima;
close $file1;

$minimaただし、作成したばかりの同じファイル（この場合はoutput_exampleファイル）から読み取ることができないと思うため、エラーが発生します。別のプログラムでコンパイルすると実行されます。

4

1 に答える 1

0

反復する最善の方法は、おそらくコードをサブルーチンに分割することです。これは、コードを明確にし、問題が発生している場所を正確に追跡するのにも役立ちます。

use strict;
use warnings;
use 5.010;
use List::Utils qw/min/;

sub load_initial_data {
    # open and read file, load it into an arrayref and return it.
}

sub find_coefficients {
    my $data = shift;
    my @results;
    foreach my $row (@$data) {
        # do stuff to calculate $aa, $bb, $coeff
        push @results, [$aa, $bb, $coeff];
    }
    return \@results;
}

sub filter_data {
    my $data = shift;
    my $coefficients = shift;
    my $min = min map { $_->[2] } @$coefficients;
    my @deletions = grep { $min == $_->[2] } @$coefficients;
    foreach my $del (@deletions) {
        delete( $data->{$del->[0]}{$del->[1]} );
    }
}

# doing the actual work:
my $data = load_initial_data(); 
my $coeffs;
foreach my $pass (0 .. $N) {
    $coeffs = find_coefficients( $data );
    $data = filter_data( $data, $coeffs );
    # You could write $data and/or $coeffs out to a file here
    # if you need to keep the intermediate stages
}
于 2013-03-11T16:48:20.473 に答える