pos($string) - length($target) can be replaced with $-[0].
| [reply]
[d/l]
[select] |
Problem: If the string is very large with lots of occurances of 'X', your @offsets array is being constantly resized and copied as you add new values.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.
| [reply]
[d/l]
[select] |
FWIW, push seems to be faster than direct indexing on a pre-grown array, as the following table shows.
The only difference between the windex and windex_2 alternatives in the following table is that the former uses push and the latter uses direct indexing on a pre-grown array. The size of the string is 100_000, containing about 3800 matches. (Full code within the readmore tags.)
Rate wregex windex_2 windex
wregex 212/s -- -24% -32%
windex_2 277/s 31% -- -11%
windex 310/s 47% 12% --
| [reply]
[d/l]
[select] |
In that case, I'd probably code up an XS module that makes two passes over the target string, allocating the result vector once after the first pass, and filling it in on the second.
| [reply] |
The resize and copies have an amortized constant cost per array element added. Put another way, pushing one element at a time averages out to a O(1) operation.
| [reply] |
#! perl -slw
use strict;
use Benchmark::Timer;
my $T= new Benchmark::Timer;
for( 1 .. 1000 ) {
my @small = (1) x 100;
my @large = (1 ) x 130900;
$T->start( "small: add 100 by 1" );
push @small, 1 for 1 .. 100;
$T->stop( "small: add 100 by 1" );
$T->start( "large: add 100 by 1" );
push @large, 1 for 1 .. 100;
$T->stop( "large: add 100 by 1" );
$T->start( "small: add 100 by 100" );
push @small, 1 .. 100;
$T->stop( "small: add 100 by 100" );
$T->start( "large: add 100 by 100" );
push @large, 1 .. 100;
$T->stop( "large: add 100 by 100" );
}
$T->report;
__END__
P:\test>461552,pl
1000 trials of small: add 100 by 1 ( 94.947ms total), 94us/trial
1000 trials of large: add 100 by 1 (112.226ms total), 112us/trial
1000 trials of small: add 100 by 100 ( 16.009ms total), 16us/trial
1000 trials of large: add 100 by 100 ( 15.977ms total), 15us/trial
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.
| [reply]
[d/l] |
