Re: Performance issue in the loop.

in reply to Performance issue in the loop.

If, based on your answers in this thread, ultimate goal is better speed after all (and not mysterious slow-downs on every 10th run, about which I have nothing to add), then as usual in case of large arrays, use PDL;. Second pair of results are for 10x $n.

use warnings;
use strict;

use feature 'say';
use Time::HiRes 'time';

srand( 1 );
my $n = 2e3;
my @input = map int rand 1e5, 1 .. $n;

my ( $check1, $check2 );

{                   # original code
    my $t = time;

    my @max;

    push @max, ( sort { $b <=> $a } @input )[ 0 ];
    my @sums = @input;

    for my $i ( 1 .. $n - 1 ){
    
        my $max = -~0;
        for my $j ( $i .. $n - 1 ){
        # HOT-SPOT {
            ( $sums[ $j - $i ] += $input[ $j ] ) > $max 
                and $max = $sums[ $j - $i ];
        # HOT-SPOT }
        }
        push @max, $max;
    }

    say time - $t;
    $check1 = pack 'I*', @max;
}

{                   # PDL
    my $t = time;

    use PDL;
    use PDL::NiceSlice;
    
    my $sums = zeroes long, scalar @input;
    my $vec  = pdl long, \@input;
    
    my @max = map $sums( 0 : -$_ - 1 )
        -> inplace
        -> plus( $vec( $_ : -1 ), 0 )
        -> maximum
    , 0 .. $#input;

    say time - $t;
    $check2 = pack 'I*', @max;
}

use Test::More;
is $check1, $check2;
done_testing;

__END__

0.148595094680786
0.0387320518493652
ok 1
1..1

14.5055229663849
0.759373903274536
ok 1
1..1
[download]

Comment on Re: Performance issue in the loop. Select or Download Code

Replies are listed 'Best First'.
Re^2: Performance issue in the loop. by etj (Deacon) on Feb 27, 2022 at 03:53 UTC
Moar PDL! Here's my tweak of vr's excellent code, for use in the perldl REPL, which doesn't feature the check, just does timing (and doesn't use strict because of the REPL), and uses "+=" instead of the wordier "->inplace->plus": `$n = 2e4; @input = map int rand 1e5, 1 .. $n; $sums = zeroes long, scalar @input; $vec = pdl long, \@input; with_time { my @max = map +($sums( 0 : -$_ - 1 ) += $vec( $_ : -1 ))-> +maximum, 0 .. $#input };` [download] I also increased the $n. EDIT: in PDL 2.077 `with_time` is always available in the PDL shells so I removed the definition of it here.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^2: Performance issue in the loop.
by etj (Deacon) on Feb 27, 2022 at 03:53 UTC

Here's my tweak of vr's excellent code, for use in the perldl REPL, which doesn't feature the check, just does timing (and doesn't use strict because of the REPL), and uses "+=" instead of the wordier "->inplace->plus":

$n = 2e4;
@input = map int rand 1e5, 1 .. $n;
$sums = zeroes long, scalar @input;
$vec  = pdl long, \@input;
with_time { my @max = map +($sums( 0 : -$_ - 1 ) += $vec( $_ : -1 ))->
+maximum, 0 .. $#input };
[download]

EDIT: in PDL 2.077 with_time is always available in the PDL shells so I removed the definition of it here.

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom