Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re^2: Faster indexing an array

by wollmers (Scribe)
on Sep 19, 2014 at 22:09 UTC ( [id://1101302]=note: print w/replies, xml ) Need Help??


in reply to Re: Faster indexing an array
in thread 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; }

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

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"] }

    Cheers Rolf

    (addicted to the Perl Programming Language and ☆☆☆☆ :)

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

    (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

    BTW: @a=0..1e6;$start=1e5;$end=2*$start;

    Cheers Rolf

    (addicted to the Perl Programming Language and ☆☆☆☆ :)

      It's not my code, it's from Algorithm::Diff. Of course, A::Diff could be faster, maybe I take over the module.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1101302]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2024-03-29 02:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found