获取稀疏矩阵的非零元素、计数和指数

Question

我有以下稀疏矩阵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. 非零矩阵项，因为矩阵是按列扫描的.屈服： Ax = 2，3，3，-1，4，4，-3，1，2，2，6，1；

由于实际的矩阵A是潜在的very2大的，在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");

Answer 1

存储稀疏数据的一种常见策略是删除您不关心的值(零)，并用您关心的每个值存储行和列索引，从而保留它们的位置信息：

[VALUE, ROW, 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

Answer 2

这就是你要找的，我猜：

#!/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;

Answer 3

Ap很简单:每次遇到非零数字时，只需从零开始并递增。我不认为你试图在@Ap中写任何东西，所以这并不奇怪，它不会像你想的那样结束。

Ai和Ax比较棘手:当你扫描行的时候，你想要一个按列排列的顺序。您将无法就地执行任何操作，因为您还不知道列将产生多少个元素，因此您无法预先知道元素的位置。

显然，如果您只需更改按行排序的要求，就会容易得多。否则，您可能会变得复杂，并收集(i，j，x)三胞胎。在收集时，它们自然是由(i，j)命令的。收集后，你只想按(j，i)对它们排序。