Re^3: An efficient, scalable matrix transformation algorithm

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

# GMCH....

my @funcs_gmch = (
    undef,  # first_timestamp
    \&avg_gmch,
    \&max_gmch,
    \&min_gmch,
    \&first_gmch,
    \&last_gmch,
  ) ;

sub downsample_gmch {
    my( $resolution, $data ) = @_;

    my $first_timestamp =
        first_timestamp_for_resolution( $resolution, $data->[0][0] );

    my @output;
    push( @output, $first_timestamp );

    push( @output, $funcs_gmch[$_]->( $data, $_ ) ) for ( 1..$#funcs_g
+mch);

    return( @output );
}

sub avg_gmch {
  my ($rd, $i) = @_ ;

  my $s = 0 ;
  $s += $_->[$i] foreach (@$rd) ;

  return $s / scalar(@$rd) ;
} ;

sub max_gmch {
  my ($rd, $i) = @_ ;

  my $m = $rd->[0]->[$i] ;
  $m < $_->[$i] and $m = $_->[$i]  foreach (@$rd) ;

  return $m ;
} ;

sub min_gmch {
  my ($rd, $i) = @_ ;

  my $m = $rd->[0]->[$i] ;
  $m > $_->[$i] and $m = $_->[$i]  foreach (@$rd) ;

  return $m ;
} ;

sub first_gmch {
  my ($rd, $i) = @_ ;

  return $rd->[0]->[$i] ;
} ;

sub last_gmch {
  my ($rd, $i) = @_ ;

  return $rd->[-1]->[$i] ;
} ;
[download]

Comment on Re^3: An efficient, scalable matrix transformation algorithm Select or Download Code

Replies are listed 'Best First'.
Re^4: An efficient, scalable matrix transformation algorithm by gone2015 (Deacon) on Jan 28, 2009 at 18:05 UTC
FWIW, this transpose runs ~3.5 times faster than the loop you had (on my machine, anyway). The message here is that the trick with Perl is to replace a `for` or `while` by `map` or `grep` if possible ! `sub transpose_gmch { my ($matrix) = shift ; my @result = () ; my $lc = $#{$matrix->[0]} ; for my $col (0..$lc) { push @result, [map $_->[$col], @$matrix] ; } ; return( \@result ); }` [download]	[reply] [d/l] [select]
Re^5: An efficient, scalable matrix transformation algorithm by Luftkissenboot (Novice) on Jan 29, 2009 at 07:37 UTC
Ah, too much good stuff! It seems that the transposition step is unnecessary for this algorithm, anyway, but that is a much better implementation, regardless, and I'll incorporate it for later use. Quite the performance jump that map() provides. Mmm, lispy goodness. It might further be worthwhile to pass it on in the RT to the Math::Matrix maintainer as a performance patch, since that's where I took the original function from, also. Thank you again, kind and knowledgeable good sir monk.	[reply]
Re^4: An efficient, scalable matrix transformation algorithm by Luftkissenboot (Novice) on Jan 28, 2009 at 15:21 UTC
Wonderful! Indeed, this is what dHarry was getting at, too. Clearly the transpose() step is extraneous, but I guess I was blinded by the way in which my object structure was currently set up to see a manner to address the individual columns. (But that's my own issue, and is clear now.) Thank you both!	[reply]