I was quite pleasantly surprised its speed. I notice, however, that the code runs about three times more slowly under 5.30 than under 5.8. I assume this is due to the many modifications made to the regex engine over the years to accommodate Unicode. Any comment on this would be of interest.

3x slower seems an awful lot. Are both perls built with the same options?

Unicode support could be part of it: it would be worth redoing the timings under 5.30 supplying either /a or /aa as a flag on the regexp. However for these patterns (ASCII input and pattern, no use of \w-style classes) I'd expect the cost between versions to be low, and the benefit of the /a flags to be zero.

There have also been numerous small changes added in recent years as a result of bugs (mostly found by fuzzers) that had the potential to be security holes. Such changes almost always make things a tiny bit slower, and as you accumulate more and more of them they add up. So it might also be informative to run the regexp tests from 5.30 under 5.8 (which might need some adaptation) to see a sample of the bugs 5.30 doesn't have.

If you're doing timings, I'd also be interested how my code from 11146164 compares - I'd expect it to win a lot by avoiding the embedded code block, and give back a fraction of that by doing more backtracking. (You should add at least the /s flag to my qr{} for proper comparison.)

# (what is proper match behavior of empty template?)

Since we're assuming implicit anchors, I think it should just match the empty string. That wasn't a case I attempted to handle though, and I doubt the OP cares about it.

> I'd expect it to win a lot

This will largely depend on the dictionary and the test samples.

With post filtering a pattern like "adieu" would produce many false positives to be filtered, but the result set would be huge anyway.°

But a pattern like "Mississippi" would produce no false positives.

But avoiding some false positives with lookaheads might turn out to be more expensive than filtering them a posteriori.

Assuming the OP is only looking for some matches instead of all matches, I'm confident my approach does better.

Or at least good enough to be justified by simpler code.

FWIW: prefer the non-embedded version.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

Update

°) all 5 letter words in the dictionary ( not 26**5 ) minus those with at least one repetition. Probably one thousand in English?

> However, the code runs about three times more slowly under 5.30 than under 5.8.

Please benchmark the older conservative inside-out version too.

I have a hunch the delay is due to security checks connected to use re 'eval'

So not embedding the code could avoid these problems.

Here are some raw timings I get, using the extensive word list I have for crosswords:

% perl -nwle 'END{ warn +(times)[0],"\n" }
  print $_
' /usr/share/dict/hv.words | wc -l
0.04
285520
% perl -nwle 'END{ warn +(times)[0],"\n" }
  print $_ if /^(.)(?!\1)(.)(?!\1|\2)(.)(?!\1|\2|\3)(.)(?!\1|\2|\3|\4)
+(.)$/
' /usr/share/dict/hv.words | wc -l
0.13
8632
% perl -MList::MoreUtils=uniq -nwle 'END{ warn +(times)[0],"\n" }
  print $_ if /^(?:(.)(.)(.)(.)(.)(?(?{ 5 != uniq $1, $2, $3, $4, $5 }
+)(?!)))$/
' /usr/share/dict/hv.words | wc -l
0.39
8632
% perl -MList::MoreUtils=uniq -nwle 'END{ warn +(times)[0],"\n" }
  print $_ if /^(.)(.)(.)(.)(.)$/ && 5 == uniq $1, $2, $3, $4, $5
' /usr/share/dict/hv.words | wc -l
0.1
8632
%
[download]

Oh, the anchor needs to come before the code block!

% perl -MList::MoreUtils=uniq -nwle 'END{ warn +(times)[0],"\n" }
  print $_ if /^(?:(.)(.)(.)(.)(.)$(?(?{ 5 != uniq $1, $2, $3, $4, $5 
+})(?!)))/
' /usr/share/dict/hv.words | wc -l
0.12
8632
%
[download]

I guess I was wrong (but it's important to get that anchor in the right place).

I think this is rather an answer to Re^6: Nonrepeating characters in an RE (performance).

And you tested the "worst case" of a pattern like adieu which resulted in 8632 hits.

And it turns out that my intuition, that a posteriori filtering outside the regex is a sufficient approach, wasn't too bad.

You didn't tell us the Perl version and I can't see a use re 'eval' happening, so no info about the observed slow down with newer versions.

> (but it's important to get that anchor in the right place)

Yes, that's a lesson I had to learn for this task already Re: Merging multiple variations of a serial number (regex as "mini prolog").

Because otherwise the regex will never reach an anchor behind a FAIL, hence longer words will be checked too.

The OP didn't tell us which anchors he plans to use, so ...

There is also (?PRUNE) to be considered to avoid unwanted backtracking, but in this case we have no quantifiers to spawn a tree anyway.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

(As reference frame, for single 'neocene' template, parent code reports ~400 ms at my PC and 5.32 Perl)

I think the task relates to items classification in a list (characters in string in this case), but unfortunately I don't see how to efficiently do this in Perl, without overhead of regexes. Not even with PDL to the rescue -- I'm mentioning it because below there are (slow) PDL solution and (fast) another "array language" solution, but PDL seems to lack primitive i.e. built-in functions, or I didn't find them.

Simple transliteration when string (argument) and "searchlist" are the same, with "replacelist" being any agreed-upon sequence, would do. The fact that "searchlist" items won't be unique, i.e. classes will not be named/numbered consecutively (i.e. some of "replacelist" items will be skipped) doesn't matter if template is transliterated in the same manner:

no warnings 'misc';             # "Replacement list is longer..."
my $tpl = 'abccbccbddb';
my $tpl_fixed = eval qq( \$tpl =~ tr!$tpl!a-z!r );
for ( qw/Mississippi Mossossoppo Panama/ ) {
    say $tpl_fixed eq eval qq( tr!$_!a-z!r )
        ? 'yes'
        : 'no'
}
[download]

and it takes (ahem) ~7s for 'neocene' and '354984si.ngl' (too many string evals?)

With PDL, the closest thing which comes to mind is that "equality table" of template and matching words should be the same. E.g., for 'neocene' such equality table will be:

1 0 0 0 0 1 0
0 1 0 0 1 0 1
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 1 0 0 1 0 1
1 0 0 0 0 1 0
0 1 0 0 1 0 1
[download]

and it's relatively easy to build. Let's pack all words into huge 2D table of bytes (I think it's easy to adjust this solution for shorts, in case of UTF-16 encoded non-ASCII input), padding words with BAD values -- BADs are not equal to themselves and so we'll get correct equality tables, stored in 3D array.

use strict;
use warnings;
use feature 'say';
use Data::Dump 'dd';
use Time::HiRes 'time';
use PDL;
use List::Util 'reduce';

use constant DICTIONARY => './354984si.ngl';
use constant TEMPLATE   => 'neocene';

open my $fh, '<', DICTIONARY;
chomp( my @dictionary = <$fh> );
close $fh;

my $width = reduce 
    { $a > length $b ? $a : length $b } 0, @dictionary, TEMPLATE;
my $height = @dictionary + 1;

my $words = zeroes byte, $width, $height;
my $data = pack "(A$width)*", @dictionary, TEMPLATE;
${ $words-> get_dataref } = $data;
$words-> upd_data;

my $t = time;

$words-> inplace-> setvaltobad( 32 );
my $table = $words-> dummy( 0, $width ) 
             == 
            $words-> dummy( 1, $width );
$words-> inplace-> setbadtoval( 32 );
$table-> badflag( 0 );

my $mask = ( $table == $table-> slice( '', '', -1 ))
    -> clump( 2 )
    -> bandover
    -> slice([ 0, -2 ])
    -> dummy( 0, $width );

my @found = split ' ', 
    ${ $words-> where( $mask )-> get_dataref };

say time - $t;
dd \@found;

__END__

1.04205107688904
["kaitaka", "lauhala", "metreme", "neocene", "tempete"]
[download]

And that's too slow... (fun, though). Note, this time includes tables preparation for all words, and therefore it won't be so bad if there are many templates, not just one. Plus, to my surprise (they happen with PDL) crude profiling shows ~30% of time is spent on bandover call, which is strange.

On the other hand, in J REPL:

   i.~ 'Mississippi'
0 1 2 2 1 2 2 1 8 8 1
   (i.~~.) 'Mississippi'
0 1 2 2 1 2 2 1 3 3 1
[download]

2nd example is to demonstrate it's easy to have nice consecutive "class numbers", but it hinders performance somewhat and not worth any effort as I said. Then:

   # words =: 'b' freads 'path_to/354984si.ngl'
354984
   template =: 'neocene'
   ] pattern =: i.~ template
0 1 2 3 1 0 1
   find =: dyad def '(#~ (x & -:) @ i.~ @ >) y'
   pattern find words
+-------+-------+-------+-------+-------+
|kaitaka|lauhala|metreme|neocene|tempete|
+-------+-------+-------+-------+-------+
   25 (6!:2) 'pattern find words'
0.0499341
[download]

The last funny command gets sentence execution time averaged over 25 runs, which is, therefore, just ~50 ms. BTW, if template is not to be anchored (OP disappeared :)) and exact brief remains guesswork), implementing sliding window is not too difficult; as case is sometimes with "array language" it leads to huge amount of redundant work to fill rectangular arrays (in addition to redundancy which already was there), but even then execution remains faster (but with lower ratio) than with Perl's regex, even though re-engine aborts early to avoid useless work.

I tried to compare binary strings which encode "equality tables", halves (triangles). I generate these strings through eval-group inside the regex:


#!/usr/bin/perl -l

use warnings;
use strict;

my $template = 'neocene';

my $equality_triangle_template = '';
$template =~ m/(.).*?(.)(?{ $equality_triangle_template .= $1 eq $2 ? 
+1 : 0 })(*FAIL)/;

my @dict;
@dict = <>; # <-- 354984si.ngl
chomp @dict;

my @good = grep {
    my $equality_triangle_word = '';
    m/(.).*?(.)(?{ $equality_triangle_word .= $1 eq $2 ? 1 : 0 })(*FAI
+L)/;
    $equality_triangle_word eq $equality_triangle_template;
    }
    grep length == length $template, 
    @dict;

print for @good;
^Z
kaitaka
lauhala
metreme
neocene
tempete
[download]

P.S.One can use (.).*(.) instead of (.).*?(.), omitting question mark - non-greediness modifier (possibly it is only slightly faster).