|
Re: Producing a list of offsets efficiently
by tlm (Prior) on May 28, 2005 at 20:31 UTC
|
index beats everything else I have tried, including various regexps. The fastest I have found is
my @o;
my $o = -1;
push @o, $o while ($o = index($s, 'a', $o+1)) > -1;
| [reply]
[d/l]
[select] |
Re: Producing a list of offsets efficiently
by dws (Chancellor) on May 28, 2005 at 20:10 UTC
|
my $string = "aXbcXdefgXhijXklmnopqrXstuvwXyz";
my $target = 'X';
my @offsets;
while ( $string =~ /$target/g ) {
push @offsets, pos($string) - length($target);
}
print "@offsets\n";
Does the trick for me, and it scales to arbitrary substrings.
(Update: hoisting length($target) out of the loop is a no-brainer. Alas, I had no brain at the time.)
| [reply]
[d/l]
[select] |
|
|
pos($string) - length($target) can be replaced with $-[0].
| [reply]
[d/l]
[select] |
|
|
| [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] |
|
|
|
|
|
Re: Producing a list of offsets efficiently
by Forsaken (Friar) on May 28, 2005 at 23:02 UTC
|
use strict;
use warnings;
my $string = 'insertreallylongstringwithlotsandlotsoffunkycharactersan
+difonefeelsreallyspecialperhapsevenaspacesomewhere";
my $char_to_be_matched = 'X';
my @matches;
my $offset = 0;
foreach my $char (split(//, $string))
{
if($char eq $char_to_be_matched) #alternatively some regex magic
{ push(@matches, $offset); }
$offset++;
}
I'm pretty certain there's one or more things that I'm not taking into account in this example, but you get the general idea ;-)
| [reply]
[d/l] |
Re: Producing a list of offsets efficiently
by injunjoel (Priest) on May 28, 2005 at 21:15 UTC
|
Greetings all
not sure how efficient this is but I thought I would pay homage to TimToady.
#!/usr/bin/perl -w
use strict;
my $string = "aXbcXdefgXhijXklmnopqrXstuvwXyz";
my $target = "X";
my $count = 0;
my @indices = map{$count++;/$target/? $count-1:();}split //,$string;
print "@indices";
exit
-InjunJoel
"I do not feel obliged to believe that the same God who endowed us with sense, reason and intellect has intended us to forego their use." -Galileo
| [reply]
[d/l] |
|
|
Rate wmap count wgrep wregex windex
wmap 5.42/s -- -12% -60% -97% -98%
count 6.13/s 13% -- -54% -97% -98%
wgrep 13.5/s 148% 120% -- -93% -96%
wregex 198/s 3558% 3132% 1372% -- -37%
windex 317/s 5741% 5062% 2251% 60% --
| [reply]
[d/l]
[select] |
|
|
Of course wmap() and count() are going to be the slowest, because they go through the string twice: once to split it into individual elements, and again to compare each element to the desired one. The index() approach is very certainly the fastest. I wrote a function called aindex() a long time ago that did just that -- used index to step through a string and return all the indices of a substring in that string.
| [reply] |
|
|
Re: Producing a list of offsets efficiently
by sh1tn (Priest) on May 29, 2005 at 00:15 UTC
|
| [reply] |
|
|
How?
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] |
