Захват ненулевых элементов, счетчиков и индексов разреженной матрицы

Question

У меня следующая разреженная матрица А.

   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];

Поскольку фактическая матрица А потенциально очень велика, есть ли эффективный способ в Perl, который может захватить эти элементы? Особенно без прихлебывания всей матрицы А в оперативную память.

Я застрял со следующим кодом. Который не дает то, что я хочу.

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

Обновлено на основании комментария 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]

Answer 2

Обычная стратегия хранения разреженных данных - отбрасывать значения, которые вам не нужны (нули), и сохранять индексы строк и столбцов с каждым значением, которое вас волнует, сохраняя, таким образом, их позиционную информацию:

[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

Answer 3

Это то, что вы ищете, я думаю:

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

Код, который вы указали, работает построчно. Чтобы получить результаты последовательно по столбцам, вы должны накапливать свои значения в отдельных массивах, по одному для каждого столбца:

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

См. Также Список :: Flatten .

Answer 5

Ap легко: просто начните с нуля и увеличивайте значение каждый раз, когда вы встречаете ненулевое число. Я не вижу, что вы пытаетесь что-то написать в @Ap, поэтому неудивительно, что все не закончится так, как вы хотите.

Ai и Axe хитрее: вы хотите упорядочить по столбцам, а сканируете по рядам. Вы не сможете сделать что-либо на месте, так как вы еще не знаете, сколько элементов будут давать столбцы, поэтому вы не можете заранее знать положение элементов.

Очевидно, было бы чертовски легче, если бы вы могли просто изменить требование, чтобы вместо этого был порядок в ряду. Если это не удастся, вы можете получить комплекс и собрать (i, j, x) триплеты. Во время сбора они, естественно, будут заказываться (i, j). После сбора вы просто хотите отсортировать их по (j, i).