Re^3: Performance problem with Clone Method

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

[dcmertens]

Unfortunately I don't know anything about the OP's problem and an internet search has not proved forthcoming with a simple explanation, in matrix terms, of the Ullmann algorithm. If Commandosupremo could spell out his implementation of the algorithm, giving a list of the operations needed, I could say PDL is the right tool or not. As to your specific points, PDL may be able to handle the operations you pose, depending on what you mean.

PDL supports a whole slew of operations including bitwise boolean operations, as mentioned here: http://pdl.perl.org/?docs=Ops&title=PDL::Ops. For counting the set bits, that's just a sum; you can perform that and many other row or whole-piddle operations as discussed here: http://pdl.perl.org/?docs=Ufunc&title=PDL::Ufunc. The implementations of the Ufuncs use simple accumulators, which loses precision when you're summing over thousands or millions of floating-point values, but will work just fine if you're summing a few hundred integers, as is the case (I believe) of the OP.

I am note very experienced at exchanging whole rows or columns using PDL, though I know it is something that PDL manages to do with data flow. In other words, when you generate piddle $b from piddle $a with a row exchanged, you can modify piddle $a and it'll show up in piddle $b, and vice versa. Put differently, exchanges lead to different 'views' of the same data. This can be very powerful, but for the OP it may simply lead to inefficiencies in the back-end.

I will pose posed this question to the PDL mailing list shortly to see if anybody can help. It would be much more useful if Commandosupremo could post the actual algorithm. At any rate, interchanging whole rows in 2D arrays, and whole columns in 2D arrays, is more difficult than I had expected, and there might be more efficient ways to do it using PDL.To exchange rows or columns, you can use the dice_axis function, like so:

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

# Here is my matrix:
my $data = sequence(5,5);

print "Original:\n$data\n";

# In order to permute columns, I need a *column* vector with the
# column numbers that I want. (You'd think a *row* vector would be
# more appropriate, but that's not how it works. Alas.)
my $indices = sequence(5);

# Set up to exchange the second and the third column:
#$indices(1:2) .= $indices(2:1);    ### should work but doesn't for me
$indices(1:2) .= $indices(pdl [2,1]);

# Perform the exchange:
my $rearranged = $data->dice_axis(0, $indices);

print "Column swap:\n$rearranged\n";

# Start over and exchange the fourth and fifth rows:
$indices = sequence(5);
$indices(3:4) .= $indices(pdl[4,3]);
my $further_rearranged = $rearranged->dice_axis(1, $indices);

print "Column and row swap:\n$further_rearranged\n";

The output I get from that looks like this:

Original:

[
 [ 0  1  2  3  4]
 [ 5  6  7  8  9]
 [10 11 12 13 14]
 [15 16 17 18 19]
 [20 21 22 23 24]
]

Column swap:

[
 [ 0  2  1  3  4]
 [ 5  7  6  8  9]
 [10 12 11 13 14]
 [15 17 16 18 19]
 [20 22 21 23 24]
]

Column and row swap:

[
 [ 0  2  1  3  4]
 [ 5  7  6  8  9]
 [10 12 11 13 14]
 [20 22 21 23 24]
 [15 17 16 18 19]
]

Edit: updated to use dice_axis

[BrowserUk]

Please see Re^4: Performance problem with Clone Method.