Re: Re: Matching First Character of Strings Efficiently

tye mentioned in the CB that he suspected one of them was broke and expensive_function wasn't being called. I knew immediately he was right, but didn't have a chance to figure it out before heading home. Of course I figured it out on the way home but not in time for Roy Johnson to have already pointed it out. I took some of tye's comments and produced the following results:

        Rate   HB1   HB2 delim  tchn    LR  kval  tye1  tye2
HB1   27.3/s    --  -25%  -58%  -64%  -68%  -69%  -76%  -77%
HB2   36.5/s   34%    --  -43%  -51%  -57%  -59%  -68%  -70%
delim 64.4/s  136%   76%    --  -14%  -25%  -27%  -43%  -47%
tchn  75.0/s  174%  106%   16%    --  -12%  -15%  -34%  -38%
LR    85.4/s  212%  134%   33%   14%    --   -3%  -24%  -29%
kval  88.1/s  222%  141%   37%   17%    3%    --  -22%  -27%
tye1   113/s  314%  210%   76%   51%   32%   28%    --   -6%
tye2   121/s  342%  231%   88%   61%   42%   37%    7%    --
[download]

The updated benchmark is here:

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark 'cmpthese';


my @list;
open (LIST, '<', 'list.rnd') or die "Unable to open list.rnd for readi
+ng : !";
while ( <LIST> ) {
    chomp;
    push @list, $_;
}

my $length = int(rand 240) + 10;
my $str_a = "";
$str_a .= ('a' .. 'z')[ rand 26] while length $str_a < $length;

sub expensive_function {
#    my ($str_a, $str_b) = @_;
#    my $foo;
#    for ( split // , $str_a . $str_b) {
#        $foo++;
#    }
}

cmpthese -5, {
    'tchn' => sub {
        use Inline C =>;
        for my $str_b ( @list ) {
            next if ! same_scan( $str_a, $str_b );
            expensive_function ( $str_a, $str_b );
        }
    },
    'LR' => sub {
        for my $str_b ( @list ) {
            next if index($str_a, substr($str_b, 0, 1));
            expensive_function ( $str_a, $str_b );
        }
    },
    'HB1' => sub {
        my ($a_1st, $rest) = split '', $str_a, 2;
        for my $str_b ( @list ) {
            my ($b_1st, $rest) = split '', $str_b, 2;
            next if $b_1st ne $a_1st;
            expensive_function ( $str_a, $str_b );
        }
    },
    'HB2' => sub {
        my $rev_a = reverse $str_a;
        my $a_1st = chop $rev_a;
        for my $str_b ( @list ) {
            my $rev_b = reverse $str_b;
            my $b_1st = chop $rev_b;
            next if $b_1st ne $a_1st;
            expensive_function ( $str_a, $str_b );
        }
    },
    'delim' => sub {
        my $fc = substr($str_a,0,1);
        for my $str_b ( @list ) {
            next if $str_b !~ /^$fc/;
            expensive_function ( $str_a, $str_b );
        }
    },
    'tye1' => sub {
        for my $str_b ( @list ) {
            next if ord $str_a != ord $str_b;
            expensive_function ( $str_a, $str_b );
        }
    },
    'tye2' => sub {
        my $fc = ord $str_a;
        for my $str_b ( @list ) {
            next if $fc != ord( $str_b );
            expensive_function ( $str_a, $str_b );
        }
    },
    'kval' => sub {
        my $fc = substr $str_a, 0, 1;
        for my $str_b ( @list ) {
            next if $fc ne substr $str_b, 0, 1;
            expensive_function ( $str_a, $str_b );
        }
    },
};
__END__
__C__
int same_scan(char* str1, char* str2)
{
  return str1[0] == str2[0] ? 1 : 0;
}
[download]

Cheers - L~R

Comment on Re: Re: Matching First Character of Strings Efficiently Select or Download Code