Re: Re: Regexp for alphbetical order match within the string

Very clever, -10. (I got that on an assignment once.)

Surprisingly, your expression is not case-insensitive, despite the /i switch. That is because you can end up with character classes like [B-z]. One possible remedy: /(.)(??{"[^lc($1)-z]"})/. (Also note that you don't need the .*).

The other thing about your regex is that it is about 30 times slower than the other recommendations. Don't even try to benchmark it for more than a few thousand iterations. But it is cool.

The other solutions are all comparable to each other for performance. My benchmarking code attached.

#!perl

use strict;
use warnings;

my @tstrs = qw(
abdc
aBcxz
abccCcccz
abcdefghijklmnop
qrstuvwxyzabz
zabc
abca
);

sub m_sorted {
    $_[0] !~ /(.)(??{"[^lc($1)-z]"})/;
}

sub substr_sorted {
    my $lstr = lc shift;
    my $test = substr($lstr, 0, 1);
    for my $i (1..length($lstr)-1) {
        my $ntst = substr($lstr, $i, 1);
        return 0 if  $ntst lt $test;
        $test = $ntst;
    }
    1;
}

sub expl_sorted {
    my $lstr = lc shift;
    $lstr eq join('', sort split //, $lstr);
}

my $gen_m_pat = join '', map "$_*", 'a'..'z';
sub gen_m_sorted {
    $_[0] =~ /^$gen_m_pat$/oi;
}

use Benchmark;
timethese(100_000, {
#    'm_sorted'      => sub { for (@tstrs) { chomp; my $is = m_sorted 
+$_; } },
    'substr_sorted' => sub { for (@tstrs) { chomp; my $is = substr_sor
+ted $_; }},
    'expl_sorted'   => sub { for (@tstrs) { chomp; my $is = expl_sorte
+d $_; }},
    'gen_m'   => sub { for (@tstrs) { chomp; my $is = gen_m_sorted $_;
+ }},
});

for (@tstrs) {
    print "$_\n";
    print " m says: ", m_sorted($_) ? '' : 'not ', "sorted\n";
    print " substr says: ", substr_sorted($_) ? '' : 'not ', "sorted\n
+";
    print " expl says: ", expl_sorted($_) ? '' : 'not ', "sorted\n";
    print " gen_m says: ", gen_m_sorted($_) ? '' : 'not ', "sorted\n";
}
[download]

Update: had replaced .* with +, when it can simply be removed altogether.

Comment on Re: Re: Regexp for alphbetical order match within the string Select or Download Code

Replies are listed 'Best First'.
Re: Re: Re: Regexp for alphbetical order match within the string by BrowserUk (Patriarch) on Oct 30, 2003 at 22:33 UTC
Just for grins, this tests about 50% quicker than the substr version in your benchmark. `sub is_sorted{ my( $str, $p, $x ) = ( lc shift, 0 ); chop$x lt $x and return 0 while $x = substr $str, $p++, 2; 1; };` [download] Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "Think for yourself!" - Abigail Hooray!	[reply] [d/l]
Re: Regexp for alphbetical order match within the string by Roy Johnson (Monsignor) on Oct 31, 2003 at 14:47 UTC
Nice work! On my box, it was about 30% faster, and this subtle tweaking is about 25% faster, yet: `sub improved { my $lstr = lc shift; my ($p, $ntst) = (length($lstr)-1); chop($ntst = substr($lstr, $p, 2)) lt $ntst and return 0 while ($p--); 1; }` [download] while this very similar model is actually slower `sub hobbled { my $str = lc shift; my ($p, $x) = (length($str)-1); chop($x) lt $x and return 0 while $x = substr($str, $p--, 2); 1; }` [download]	[reply] [d/l] [select]