Capturing ненулевых элементы, Графы и индексы разреженных матриц

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

Поскольку фактическая матрица А является потенциально very2 большой, есть ли эффективный способ в 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 

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

Обновлено основано на комментарий главы МИД. Если вы не хотите сохранить какие-либо из исходных данных:

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