Re: Performance problem with Clone Method

[Jenda]

I may be missing something, but isn't this exactly what PDL was created for?

[BrowserUk]

Problem: How do you access/manipulate the current value of a single number (the value stored at a single indexed position) in a piddle?

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

[dcmertens]

BrowserUK, you don't think this is actually a problem, do you? PDL is a very mature Perl extension that handles high dimensional data sets very nicely. In fact (surprise!) there's more than one way to do it. At the moment, I believe the best documentation for beginners is the Matlab or Scilab migration guides. They say that PDL::QuickStart is a better place to start, but I humbly disagree. See http://pdl.perl.org/?docs=Tutorials&title=PDL::Tutorials for the (short) list of tutorials available.

To answer your specific question, suppose you have a 2x4 piddle, perhaps created with the sequence command. A snippet of your code might look like this:

my $pdl = sequence(2,4);

If you wanted to modify the (0,3) element of the array (first column, last row), you would use NiceSlice and the .= notation like so:

$pdl(0,3) .= -4;

A full working example would look like this:

use strict;
use warnings;
use PDL;
use PDL::NiceSlice;

my $pdl = sequence(2,4);
print "$pdl\n";
$pdl(0,3) .= -4;
print "$pdl\n";

The output looks like this:

[
 [0 1]
 [2 3]
 [4 5]
 [6 7]
]


[
 [ 0  1]
 [ 2  3]
 [ 4  5]
 [-4  7]
]

Edit: revised the opening paragraph to be more useful

Edit2: re-revised the opening paragraph to be even more useful

Edit3: used code tags instead of pre tags for example code and ouput

[BrowserUk]

I think that if an algorithm requires access to individual elements of the piddles, rather than being able to apply single operations to whole piddles at a time, there is little to be gained. What you might gain from more efficient duplication, you lose by having to call one or two functions per element during calculation or conditional testing.

From my very limited understanding of the OPs problem, much of the effort involved in the algorithm involves:

• interchanging whole rows & whole columns in 2D arrays.

  I don't think that PDL is particularly efficient at performing these operations, especially the latter.

• performing "bit-wise" boolean operations and 'counting-the-set-bits', on pairs of rows of zeros and ones.

  If the rows of 0s and 1s were encoded as simple bit-vectors, then not only can standard Perl can perform both these operations more efficiently than PDL, the storage requirements are 8x less.

I'd be very happy to be wrong here, but I just don't think PDL suits these particular types of operations.

[dwm042]

PDL(i,j) manipulation:

Look at the get and set functions in PDL::Func.

To note, the difference between column and row operations are the difference between 0 transpose operations and 2 of them. That said, between PDL::Slices and PDL::NiceSlice there are so many ways to skin this cat I'm surprised people worry about the issue of column/row operations in PDL.



#! /usr/bin/perl

use PDL;

my $M = sequence(10,10);
print $M;
my $row = $M->slice(':,3');
my $col = $M->slice('4,:');
my $col2 = $M->slice('5,:');
my $deep_col = $col->copy;
$col .= $col2;
$col2 .= $deep_col;
print $M;



See also reorder, dice, range etc. Update:original code example broken.

If you're doing lots of row or column manipulations, perhaps better to keep a 1d piddle of index values and manipulate those.

[BrowserUk]

there are so many ways to skin this cat I'm surprised people worry about the issue of column/row operations in PDL.

The problem is not "can it be done with PDL", more "do you gain anything by using PDL to do it"? Ie. Is it more efficient?

This iterates through all the row and column permutations of a 10x10 matrix in 82 seconds:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];
use Time::HiRes qw[ time ]; #$Data::Dump::WIDTH = 1000;
use Algorithm::Combinatorics qw[ permutations ];

my @a = map[ 10 *$_ .. 10 *$_ + 9 ], 0 .. 9;

## rows
my $start = time;

my $perms = permutations( [ 0 .. 9 ] );
while( my $p = $perms->next ) {
    my @perm = @a[ @$p ];
}

printf "All row permutations took %f seconds\n", time - $start;

## cols
$start = time;

$perms = permutations( [ 0 .. 9 ] );
while( my $p = $perms->next ) {
    my @perm = map[ @{$_}[ @$p ] ], @a;
}

printf "All column permutations took %f seconds\n", time - $start;

__END__
C:\test>PermsMatrix.pl
All row permutations took 17.198000 seconds
All column permutations took 65.284842 seconds

The OP mentioned matrices of "hundreds x hundreds".

As I understand the brute force algorithm for the Subgraph Isomorphism Problem, it requires performing all the row permutations for all the column permutations of the smaller of the two adjacency matrix graphs for every equal sized subgraph of the larger adjacency matrix. Ullmann trims the tree somewhat, but essentially still requires many of the iterations and all the transformations to be performed.

I've no doubts that this can be done with PDL; I just wonder if you gain much performance?