perl - 捕获稀疏矩阵的非零元素、计数和索引

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. 非零矩阵条目，因为矩阵是按列扫描的。 产量:

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

由于实际矩阵 A 可能非常大，有什么有效的方法 在 Perl 中可以捕获那些元素？特别是在不吸食所有矩阵 A 的情况下 进入内存。

我被下面的代码困住了。这并没有给出我想要的。

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]

就您而言，您可以进一步节省成本，因为通过逐列处理数据可以满足您的所有需求，这意味着我们不必为每个值重复 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