2

次の疎行列 A があります。

   2   3   0   0   0
   3   0   4   0   6
   0  -1  -3   2   0
   0   0   1   0   0
   0   4   2   0   1

次に、そこから次の情報を取得したいと思います。

  1. 行列が列方向にスキャンされるときのエントリの累積数。収量:

    Ap = [0, 2, 5, 9, 10, 12];

  2. 行列が列方向にスキャンされるため、エントリの行インデックス。収量:

    Ai = [0, 1, 0, 2, 4, 1, 2, 3, 4, 2, 1, 4];

  3. 行列が列方向にスキャンされるため、非ゼロの行列エントリ。収量:

    斧 = [2, 3, 3, -1, 4, 4, -3, 1, 2, 2, 6, 1];

実際の行列 A は非常に大きくなる可能性があるため、Perl でこれらの要素をキャプチャできる効率的な方法はありますか? 特に、すべての行列 A を RAM に丸呑みすることなく。

次のコードで立ち往生しています。それは私が望むものを与えません。

use strict;
use warnings;

my (@Ax, @Ai, @Ap) = ();
while (<>) {
    chomp;
    my @elements = split /\s+/;
    my $i = 0;
    my $new_line = 1;
    while (defined(my $element = shift @elements)) {
        $i++;
        if ($element) {
            push @Ax, 0 + $element;
            if ($new_line) {
                push @Ai, scalar @Ax;
                $new_line = 0;
            }

            push @Ap, $i;
        }
    }
}
push @Ai, 1 + @Ax;
print('@Ax  = [', join(" ", @Ax), "]\n");
print('@Ai = [', join(" ", @Ai), "]\n");
print('@Ap = [', join(" ", @Ap), "]\n");
4

5 に答える 5

1

FMのコメントに基づいて更新されました。元のデータを保存したくない場合:

#!/usr/bin/perl

use strict;
use warnings;

my %matrix_info;

while ( <DATA> ) {
    chomp;
    last unless /[0-9]/;
    my @v = map {0 + $_ } split;
    for (my $i = 0; $i < @v; ++$i) {
        if ( $v[$i] ) {
            push @{ $matrix_info{$i}->{indices} }, $. - 1;
            push @{ $matrix_info{$i}->{nonzero} }, $v[$i];
        }
    }
}

my @cum_count = (0);
my @row_indices;
my @nonzero;

for my $i ( sort {$a <=> $b } keys %matrix_info ) {
    my $mi = $matrix_info{$i};
    push @nonzero, @{ $mi->{nonzero} };

    my @i = @{ $mi->{indices} };

    push @cum_count, $cum_count[-1] + @i;
    push @row_indices, @i;
}

print(
    "\@Ap = [@cum_count]\n",
    "\@Ai = [@row_indices]\n",
    "\@Ax = [@nonzero]\n",
);

__DATA__
2   3   0   0   0
3   0   4   0   6
0  -1  -3   2   0
0   0   1   0   0
0   4   2   0   1

出力:

C:\Temp>m
@Ap = [0 2 5 9 10 12]
@Ai = [0 1 0 2 4 1 2 3 4 2 1 4]
@Ax = [2 3 3 -1 4 4 -3 1 2 2 6 1]
于 2009-08-25T14:22:41.153 に答える
1

これはあなたが探しているものです、私は推測します:

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper::Simple;

my @matrix;

# Populate @matrix
while (<>) {
    push @matrix, [ split /\s+/ ];
}

my $columns = @{ $matrix[0] };
my $rows    = @matrix;

my ( @Ap, @Ai, @Ax );
my $ap = 0;

for ( my $j = 0 ; $j <= $rows ; $j++ ) {
    for ( my $i = 0 ; $i <= $columns ; $i++ ) {
        if ( $matrix[$i]->[$j] ) {
            $ap++;
            push @Ai, $i;
            push @Ax, $matrix[$i]->[$j];
        }
    }
    push @Ap, $ap;
}

print Dumper @Ap;
print Dumper @Ai;
print Dumper @Ax;
于 2009-08-25T10:09:08.083 に答える
1

スパース データを格納するための一般的な戦略は、気にしない値 (ゼロ) を削除し、気にする各値と共に行インデックスと列インデックスを格納することです。これにより、それらの位置情報が保持されます。

[VALUE, ROW, COLUMN]

あなたの場合、データを列ごとに処理することですべてのニーズを満たすことができるため、さらに節約できます。つまり、値ごとに COLUMN を繰り返す必要はありません。

use strict;
use warnings;
use Data::Dumper;

my ($r, $c, @dataC, @Ap, @Ai, @Ax, $cumul);

# Read data row by row, storing non-zero values by column.
#    $dataC[COLUMN] = [
#        [VALUE, ROW],
#        [VALUE, ROW],
#        etc.
#    ]
$r = -1;
while (<DATA>) {
    chomp;
    $r ++;
    $c = -1;
    for my $v ( split '\s+', $_ ){
        $c ++;
        push @{$dataC[$c]}, [$v, $r] if $v;
    }
}

# Iterate through the data column by column
# to compute the three result arrays.
$cumul = 0;
@Ap = ($cumul);
$c = -1;
for my $column (@dataC){
    $c ++;
    $cumul += @$column;
    push @Ap, $cumul;
    for my $value (@$column){
        push @Ax, $value->[0];
        push @Ai, $value->[1];
    }
}

__DATA__
2   3   0   0   0
3   0   4   0   6
0  -1  -3   2   0
0   0   1   0   0
0   4   2   0   1
于 2009-08-25T13:00:48.383 に答える
0

Apは簡単です。ゼロから始めて、ゼロ以外の数値に出会うたびにインクリメントするだけです。@Apに何かを書き込もうとしているのは見当たらないので、思い通りに終わらないのは当然です。

AiとAxeは扱いにくいです。行方向にスキャンしているときに、列方向の順序が必要です。列が生成する要素の数がまだわからないため、インプレースで何も実行できません。そのため、要素の位置を事前に知ることはできません。

明らかに、代わりに行方向の順序を設定するように要件を変更できれば、はるかに簡単になります。それができないと、複雑になり、(i、j、x)トリプレットを収集する可能性があります。収集している間、それらは当然(i、j)によって順序付けられます。収集後は、(j、i)で並べ替えるだけです。

于 2009-08-25T09:38:20.843 に答える
0

あなたが提供したコードは、行ごとに機能します。列ごとに連続した結果を取得するには、列ごとに 1 つずつ、値を個別の配列に蓄積する必要があります。

# will look like ([], [], [] ...), one [] for each column.
my @columns;

while (<MATRIX>) {
    my @row = split qr'\s+';
    for (my $col = 0; $col < @row; $col++) {

        # push each non-zero value into its column
        push @{$columns[$col]}, $row[$col] if $row[$col] > 0;

    }
}

# now you only need to flatten it to get the desired kind of output:
use List::Flatten;
@non_zero = flat @columns;

List::Flattenも参照してください。

于 2009-08-25T09:50:47.323 に答える