Re^5: Performance problem with Clone Method

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