Re^2: Faster indexing an array

Thanks a lot.

Davidos solution is faster than mine, and LanX' and CountZeros is the fastest.

For some reason Devel::NYTProf gives better results for C-style loops over 'for my $i (...)'.

The hashref is a relict from having this part in an sub, then refactored down, then inlined, now 1-lined. See here the same logic in Algorithm::Diff:

sub _withPositionsOfInInterval
{
    my $aCollection = shift;    # array ref
    my $start       = shift;
    my $end         = shift;
    my $keyGen      = shift;
    my %d;
    my $index;
    for ( $index = $start ; $index <= $end ; $index++ )
    {
        my $element = $aCollection->[$index];
        my $key = &$keyGen( $element, @_ );
        if ( exists( $d{$key} ) )
        {
            unshift ( @{ $d{$key} }, $index );
        }
        else
        {
            $d{$key} = [$index];
        }
    }
    return wantarray ? %d : \%d;
}
[download]

Having an arrayref comes from the two input-parameters, sequences X, Y or sometimes also called A, B in the descriptions of diff/LCS/align-algorithms.

Helmut Wollmersdorfer

Comment on Re^2: Faster indexing an array Download Code

Replies are listed 'Best First'.
Re^3: Faster indexing an array by LanX (Saint) on Sep 19, 2014 at 22:34 UTC
The `if(exists...)` test isn't necessary and can be optimized away! `DB<119> unshift @{ $d{key} }, 'bla' => 1 DB<120> \%d => { key => ["bla"] }` [download] Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :)}	[reply] [d/l] [select]
Re^3: Faster indexing an array by LanX (Saint) on Sep 19, 2014 at 23:17 UTC
you didn't tell us that you need only an interval out of the array, the fastest approach with my version of Perl is iterating over an interval or array slice `DB<173> use Time::HiRes qw/time/ DB<174> @x=();$t=time; for (my $i=$start; $i<=$end;$i++) { push @x, +$a[$i]}; print time-$t 0.21531081199646 DB<175> @y=(); $t=time; push @y, $_ for @a[$start..$end]; print time +-$t 0.1353440284729 DB<176> @z=();$t=time; push @z, $a[$_] for $start..$end; print time- +$t 0.142512083053589` [download] (you are welcome to do proper benchmarking =) but optimizing or inlining `&$keyGen( $element, @_ )` should lead to much more efficiency, since 25% of 15% doesn't count much!!! update of course you could directly iterate over the values of a hash slice of an array slice... :) `DB<180> %h=(); $i=$start; $t=time; push @$_, $i++ for @h{@a[$start.. +$end]}; print time-$t => 1 0.427901983261108` [download] BTW: `@a=0..1e6;$start=1e5;$end=2*$start;` Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :)}	[reply] [d/l] [select]
Re^4: Faster indexing an array by wollmers (Scribe) on Sep 20, 2014 at 06:54 UTC
It's not my code, it's from Algorithm::Diff. Of course, A::Diff could be faster, maybe I take over the module.	[reply]

update