An alternative approach would be to use MCE, and in one "core" each, use a PDL builtin like avgover etc to do one of the various kinds of processing. The results could be melded together as the final step.

I’m not sure if I understand what you are trying to do, i.e. it makes no sense to me.

I don’t understand your reduction functions, see Reducing a matrix for how to reduce a matrix.

On the subject of transposing matrices books have been written. There are many algorithms around, also parallel algorithms exist. But why do you have to transpose the matrix?

What problem are you trying to solve, how do you end up with the matrix in the first place?

Update

Wiki is an excellent starter, it sort of reanimated my knowledge on the subject.

From your description what you need to do is:

  A1 = F1(a1, a2, a3, ...., an)
  B1 = F2(b1, b2, b3, ...., bn)
  C1 = F3(c1, c2, c3, ...., cn)

I assume the issue here is scale. But I regret this humble engineer is struggling to understand where to look for improvement. (Assuming a multi-core processor I can see that processing columns in parallel makes sense -- especially if the original matrix were in shared memory !) You don't say where the matrix comes from... I wonder if it's possible to transpose it as it's read in ?

So... can you post some code ? Preferrably reduced to show the key logic... and give some idea of the true scale ?

Of course, the general advice is to profile what you have, to identify where the time is really being spent.

Ah, sorry, you're right. It would be O(n*m) (where m is the number of reduction functions, and n is the number of records).

Indeed, the issue is scale. The original data comes in by sampling various parameters of numerous biological electronic sampling devices over time, and so each record keeps a timestamp. The "a" column would, in this case, be a timestamp, and the others would be, say, averages, maxes, minimums for that time window. This needs to be done for a huge number of devices in parallel, or at least in a linear fashion that won't introduce delays, as this has to happen inline with the sampling before it gets archived.

The reason for the transformation is for the purpose of re-scaling the granularity of the data.

A good example would be:

time+microseconds    AVGTEMP   MAXTEMP   MINTEMP   STARTTEMP   ENDTEMP

In order to rescale this type of data to a larger time granularity (say, 5 second chunks, 1 minute chunks, etc.), you need to perform the different functions on each column to make them reflect the proper averages, maximums, minimums, etc. for the new time window.

(I forgot to mention that I also considered RRD for this, but it doesn't have enough consolidation functions included, and adding new ones is far from trivial. Will update the original node).

Ok, that's all verbose. Here's a code sample, as simple as I can make it and still have it work:

Read more... (2 kB)

I am still not convinced you have to transpose the matrix but maybe I am having an off-day, i.e. to blind to see it;-) When I read to your post the first thing that jumps into mind is the use of a database., especially since your "reduce functions" are simple.

However, assuming you insist on transposing, you might be able to speed things up. The case N != M is more difficult then N = M. The approach you take right now is the straightforward approach but this can give poor performance (as you have probably noticed).

In general: depending on circumstances, things like how much storage you have available and more importantly how M relates to N (|N-M| small or gcd(N,M) is not small) you can improve by using a more refined algorithm. (This I have taken from the Wiki, already suggested in my earlier response.) You can find pointers there to articles on the subject of in-place matrix transposition. I don’t know of any Perl implementations but the pointers on the Wiki also contain source code so you should be able to rewrite that into Perl if needed.

HTH, dHarry

I used Devel::Profile and found that 84.74% of the running time is in the main::transpose function.

I don't know how the data in @records actually arrives there, but I would consider capturing it in an array of columns rather than an array of rows -- eliminating the transpose operation completely.

I tried replacing the downsample() function and the functions themselves, to operate directly on the columns. (The code for that is included below.) In order to get some timings I expanded the sample @records by the simple expedient of @records = (@records) x 100_000. On my machine, operating directly on the columns downsampled the records in 1.1s, where your code took 12.8s.

Mind you, I doubt whether you downsample this many samples at once, so these timings will overstate the impact of improving the inside of the downsample function.

Finally, depending on how the data is input, I would consider combining the downsampling with the input -- avoiding construction of the @records array altogether...

Read more... See the code (1463 Bytes)

If you can make all your consolidation functions able to work incrementally, you could process your data one row at a time. Even if you can't make the function work incrementally, you might be able to transform it such that you can use partial results and combine them at the end (last line of example before __DATA__ statement). Something like this:

#!/usr/bin/perl -w
#
# Sploink.pl
#
use strict;
use warnings;

sub make_summer {
        my $sum = 0;
        return sub { $sum += $_[0]; }
}

sub make_minner {
        my $min = 9.99e99;
        return sub {
                $min = $_[0] if $_[0] < $min;
                return $min;
        }
}

sub make_avger {
        my ($cnt, $sum) = (0, 0);
        return sub {
                $sum += $_[0];
                ++$cnt;
                return $sum/$cnt;
        }
}

sub make_counter {
        my $cnt = 0;
        return sub { ++$cnt }
}

my @funcs = (
        make_summer(),
        make_minner(),
        make_avger(),
        make_avger(),
        make_counter(),
);

my @results;
while (<DATA>) {
        chomp;
        my @flds = split /\s+/;
        $results[$_] = $funcs[$_]($flds[$_]) for (0 .. $#funcs);
}

print "results: ", join(", ", @results), "\n";
print "avg of column 1 is: ", $results[0] / $results[4], "\n";
__DATA__
10 20 30 40
12 14 16 18
9  10 11 12
13 14 15 16
[download]

Which gives the following:

roboticus@swill: /Work/Perl/PerlMonks
$ ./sploink_739466.pl
results: 44, 10, 18, 21.5, 4
avg of column 1 is: 11
[download]

...roboticus

UPDATE: Added program output

Actually, that is very feasible. Now that I've dug further into it from previous conversations also, it would lend itself to it, and it would be a major memory saver, to boot.

So many good suggestions. Thank you!

If there are ... an infinite number of Bad solutions ..., is this an attempt to eliminate a number of them in the hope that, to paraphrase Sherlock Holmes, ...whatever remains, however improbable, must point to the answer ? :D

Well, that would certainly be effective. But I was really hoping for someone more well-versed than I in linear algebra or parallelism to share a flash of inspiration.

It's either that, or go with the Seven-Percent Solution, which would probably make it difficult to analyse suggested solutions properly. ;)