in reply to The sum of absolute differences in the counts of chars in two strings.
Here's my benchmark of a couple of PP and several I::C versions based (loosely) on the ideas posted in the thread along with my chosen I::C version which gains a little performance by using chars for the counting as 127 chars is a reasonable maximum length. And gains a little more by restricting the alphabet to printable ascii chars only, which is also reasonable for the envisaged use. The benchmark results are:
Rate PP trg mb Pb JF me PP 0.168/s -- -92% -96% -97% -97% -97% trg 2.14/s 1170% -- -55% -58% -59% -68% mb 4.72/s 2703% 121% -- -8% -10% -30% Pb 5.13/s 2948% 140% 9% -- -3% -23% JF 5.27/s 3031% 147% 12% 3% -- -21% me 6.70/s 3881% 213% 42% 31% 27% --
And the code:
#! perl -slw use strict; use Inline C => Config => BUILD_NOISY => 1; use Inline C => <<'END_C', NAME => 'deltasum', CLEAN_AFTER_BUILD => 0 +; // Assumes equal length ascii strings and no embedded nulls. int deltasum( char *a, char *b ) { signed char counts[256] = { 0, }; int i, sum = 0; while( *a && *b ) ++counts[ *a++ ], --counts[ *b++ ]; for( i = 32; i < 127; ++i ) sum += abs( counts[ i ] ); return sum; } int Perlbotics(char* a, char* b) { int counter_tab[256] = { 0 }; int i; int sum = 0; for ( ; *a ; ++a ) ++counter_tab[ *a ]; for ( ; *b ; ++b ) --counter_tab[ *b ]; for ( i = 0; i < 256; ++i ) { /* maybe reduced to significant range? + */ sum += abs( counter_tab[i] ); } return sum; } int mbethke(char *s, char *t) { int i, sum=0, freqs[256] = { 0 }; for(i=0; i<strlen(s); ++i) freqs[s[i]]++; for(i=0; i<strlen(t); ++i) freqs[t[i]]--; for(i=0; i<256; ++i) sum += abs(freqs[i]); return sum; } int JavaFan(char *s, char *t) { int i, sum=0, freqs[256] = { 0 }; while (*s) {freqs[*s++]++;} while (*t) {freqs[*t++]--;} for(i=0; i<256; ++i) sum += abs(freqs[i]); return sum; } END_C use Data::Dump qw[ pp ]; use Benchmark qw[ cmpthese ]; sub deltaSum { my( $sum, @counts ) = 0; ++$counts[ $_ ] for unpack 'C*', $_[0]; --$counts[ $_ ] for unpack 'C*', $_[1]; $sum += abs( $counts[ $_ ] // 0 ) for 32 .. 127; return $sum; } sub genTr { my $code = join "+", map{ "abs( \$_[0] =~ tr[$_][$_] - \$_[1] =~ tr[$_][$_] )" } @_; eval "sub{ $code; }"; } chomp( our @s = <DATA> ); our $I //= -1; cmpthese $I, { PP => q[ my $total = 0; for my $i ( 0 .. $#s ) { $total += deltaSum( @s[ $i, $_ ] ) for $i+1 .. $#s; } print "deltaSum : $total" if $I == 1; ], trg => q[ my $total = 0; my $sub = genTr( qw[a c g t ] ); for my $i ( 0 .. $#s ) { $total += $sub->( @s[ $i, $_ ] ) for $i+1 .. $#s; } print "tr_g : $total" if $I == 1; ], me => q[ my $total = 0; for my $i ( 0 .. $#s ) { $total += deltasum( @s[ $i, $_ ] ) for $i+1 .. $#s; } print "deltasum : $total" if $I == 1; ], Pb => q[ my $total = 0; for my $i ( 0 .. $#s ) { $total += Perlbotics( @s[ $i, $_ ] ) for $i+1 .. $#s; } print "Perbotics : $total" if $I == 1; ], mb => q[ my $total = 0; for my $i ( 0 .. $#s ) { $total += mbethke( @s[ $i, $_ ] ) for $i+1 .. $#s; } print "mbethke : $total" if $I == 1; ], JF => q[ my $total = 0; for my $i ( 0 .. $#s ) { $total += JavaFan( @s[ $i, $_ ] ) for $i+1 .. $#s; } print "JavaFan : $total" if $I == 1; ], }; __DATA__ aaaaaaaaaaacccg aaaaaaaaaaccccg aaaaaaacccccccc aaaaaaaaacccccg aaaaaaaaaaaccgg aaaaaaaaaacccgg aaaaaaacccccccg aaaaaaaaaccccgg aaaaaaaaaaccggg aaaaaaaacccccgg aaaaaaccccccccg aaaaaaaaacccggg aaaaacccccccccg aaaaaaaccccccgg aaaaccccccccccg aaaaaaaaccccggg aaaaaaaaaacgggg aaaaaacccccccgg aaaaaaaaaacccct aaaaaaaaaccgggg aaaaaccccccccgg aaaaaaacccccggg aaaaaaaaaccccct aaaaaaaaaaaccgt aaaacccccccccgg aaaaaaaacccgggg aaaaaaccccccggg aaaaaaaacccccct aaaaaaaaaaaaggt aaaaaaaaaacccgt aaaccccccccccgg aaaaacccccccggg aaaaaaaaacggggg aaaaaaaccccgggg aaaaaaaccccccct aaaaaaaaaccccgt aaaaaaaaaaacggt aaaaaaaaccggggg aaaaccccccccggg aaaaaacccccgggg aaaaaacccccccct aaaaaaaacccccgt aaaaaaaaaaccggt aaaaaccccccgggg aaacccccccccggg aaaaaaacccggggg aaaaaaaccccccgt aaaaaccccccccct aaaaaaaaacccggt aaaaaaaaaaagggt aaaaaaaacgggggg aaaacccccccgggg aaccccccccccggg aaaaaaccccggggg aaaaaaaaccccggt aaaaaaaaaacgggt aaaaaacccccccgt aaaacccccccccct aaaaacccccggggg aaaaaaaccgggggg aaaccccccccgggg aaaaaccccccccgt aaaaaaacccccggt aaaaaaaaaccgggt aaaaccccccggggg aaaaaaaaggggggg aacccccccccgggg aaaaaacccgggggg aaaaaaaacccgggt aaaaaaaaaaggggt aaaacccccccccgt aaaaaaccccccggt aacccccccccccct aaacccccccggggg accccccccccgggg aaaaaccccgggggg aaaaaaaaaaccctt aaaaaaacggggggg aaaaacccccccggt aaaaaaaccccgggt aaaccccccccccgt aaaaaaaaacggggt aaccccccccggggg aaaaaaaaacccctt aaaacccccgggggg aaaaaaccggggggg aaaaaaaaaaacgtt aacccccccccccgt aaaaaacccccgggt aaaaaaaaccggggt aaaaccccccccggt aaaaaaaaccccctt aaaaaaagggggggg acccccccccggggg aaaccccccgggggg aaaaacccggggggg aaaaaaaaaaccgtt aaacccccccccggt aaaaaaacccggggt aaaaaccccccgggt aaaaaaaaagggggt aaaaaaacccccctt aacccccccgggggg aaaaaacgggggggg aaaaaaaaacccgtt aaaaaaaaaaaggtt aaaaccccggggggg aaccccccccccggt aaaaaaccccggggt aaaaaaaacgggggt aaaacccccccgggt aaaaaaaaccccgtt aaaaaaaaaacggtt accccccccgggggg aaaaaccgggggggg aaacccccggggggg aaaaaaccccccctt aaaccccccccgggt acccccccccccggt aaaaacccccggggt aaaaaaaccgggggt aaaacccgggggggg aaaaaaacccccgtt aaaaaaaaaccggtt aaaaaaggggggggg cccccccccgggggg aaccccccggggggg aaaaacccccccctt aaaaaacccgggggt aaaaaaaaggggggt aaaaccccccggggt aacccccccccgggt acccccccggggggg aaaccccgggggggg aaaaaaaaaagggtt aaaaaaaacccggtt aaaaaaccccccgtt aaaaacggggggggg aaaaccccccccctt aaaaaccccgggggt aaacccccccggggt accccccccccgggt aaaaaaacggggggt aaaaacccccccgtt aaaaccggggggggg aacccccgggggggg aaacccccccccctt aaaaaaaaacgggtt ccccccccggggggg aaaaaaaccccggtt aaaaaaaaaaacttt aaccccccccggggt aaaaaaccggggggt aaaacccccgggggt aaacccggggggggg accccccgggggggg aaaaccccccccgtt aaccccccccccctt aaaaaaaaccgggtt aaaaaacccccggtt aaaaaaaaaaccttt aaaaacccggggggt aaaaaaagggggggt aaaccccccgggggt acccccccccggggt aaccccggggggggg aaaacgggggggggg aaaaaccccccggtt aaacccccccccgtt aaaaaaacccgggtt cccccccgggggggg aaaaaaaaaggggtt aaaaaaaaacccttt aaaaccccggggggt aaaaaacgggggggt aacccccccgggggt aaccccccccccgtt aaaacccccccggtt aaaaaaaacggggtt aaaccgggggggggg aaaaaaccccgggtt acccccggggggggg aaaaaaaaaacgttt aaaaaaaaccccttt aaaaaccgggggggt aaacccccggggggt accccccccgggggt aaaaacccccgggtt acccccccccccgtt aaaaaaaccggggtt aaaccccccccggtt aacccgggggggggg aaaaaaaaaccgttt aaccccccggggggt cccccccccgggggt aaaaaaggggggggt aaaaaaacccccttt aaaacccgggggggt accccgggggggggg aacccccccccggtt aaaaaacccggggtt aaaaccccccgggtt aaaaaaaagggggtt aaaaaaccccccttt aaaaaaaaaaggttt aaaaacggggggggt aaaccccgggggggt aaaaaaaacccgttt acccccccggggggt aaaaaccccggggtt aaaaaaacgggggtt aaccggggggggggg accccccccccggtt aaacccccccgggtt aaaaaaaccccgttt ccccccccggggggt aaaaccggggggggt aacccccgggggggt aaaaaaaaacggttt aaaaacccccccttt aaccccccccgggtt cccccccccccggtt aaaaaaccgggggtt aaaacccccggggtt aaacccggggggggt aaaaagggggggggt accccccgggggggt aaaaaacccccgttt aaaaaaaaccggttt aaaaccccccccttt aaaccccccggggtt acccccccccgggtt aaaaacccgggggtt aaaaaaaggggggtt cccccccgggggggt aaaaaaacccggttt aaaaaaaaagggttt aaaaaccccccgttt aaacccccccccttt aaaacgggggggggt aaccccggggggggt aaaaccccgggggtt aaaaaacggggggtt ccccccccccgggtt aacccccccggggtt aaaccgggggggggt aaccccccccccttt aaaaaaaacgggttt aaaacccccccgttt acccccggggggggt aaaaaaccccggttt aaaaaaaaaactttt aaaaaccggggggtt accccccccggggtt aaacccccgggggtt aaaccccccccgttt aaaaaaaccgggttt aaaaggggggggggt aaaaacccccggttt aacccgggggggggt ccccccggggggggt cccccccccggggtt aaaaaagggggggtt aaccccccgggggtt aaaaaaaaacctttt aaaacccggggggtt aaaaccccccggttt aaaaaacccgggttt aacccccccccgttt aaacggggggggggt aaaaaaaaggggttt accccgggggggggt aaaaaaaaaagtttt aaaccccggggggtt aaaaaaaaccctttt acccccccgggggtt aaaaacgggggggtt aaaaaccccgggttt aaccggggggggggt accccccccccgttt aaacccccccggttt aaaaaaacggggttt ccccccccgggggtt aaaaaaacccctttt aaaaccgggggggtt aacccccggggggtt aaaaaaaaacgtttt aaaacccccgggttt aaaaaaccggggttt acccggggggggggt aaccccccccggttt aaaaaaccccctttt aaaaaggggggggtt aaaaaaaaccgtttt accccccggggggtt aaacccgggggggtt acccccccccggttt aaaaacccggggttt aaaccccccgggttt aaaaaaagggggttt ccccggggggggggt aacgggggggggggt cccccccggggggtt aaaaaaaaaggtttt aaaacggggggggtt aaaaacccccctttt aaccccgggggggtt aaaaaaacccgtttt aacccccccgggttt aaaaaacgggggttt ccccccccccggttt aaaaccccggggttt aaaaaaaacggtttt aaaccggggggggtt aaaaccccccctttt aaaaaaccccgtttt acccccgggggggtt aaaaaccgggggttt aaacccccggggttt accccccccgggttt aaaaaaaccggtttt aaacccccccctttt aaaaacccccgtttt ccccccgggggggtt aaaagggggggggtt aacccggggggggtt acggggggggggggt aaaaaaggggggttt aaaacccgggggttt cccccccccgggttt aaccccccggggttt accccggggggggtt aaccccccccctttt aaaaaaaagggtttt aaaaccccccgtttt aaaaaacccggtttt aaacgggggggggtt aaaccccgggggttt acccccccggggttt aaaaacggggggttt aaaaaaacgggtttt aaaaaccccggtttt aaccgggggggggtt cccccggggggggtt aaacccccccgtttt acccccccccctttt aaaaccggggggttt aacccccgggggttt ccccccccggggttt aaaaaaaaacttttt aaccccccccgtttt acccgggggggggtt ccccccccccctttt aaaaaaccgggtttt aaaacccccggtttt aaaggggggggggtt aaaaaaaaccttttt aaaaagggggggttt aaacccggggggttt accccccgggggttt acccccccccgtttt aacggggggggggtt ccccgggggggggtt aaaaacccgggtttt aaaaaaaggggtttt aaaccccccggtttt aaccccggggggttt cccccccgggggttt aaaaaaaaagttttt aaaacgggggggttt aaaaaaacccttttt ccccccccccgtttt accggggggggggtt aacccccccggtttt aaaaaacggggtttt aaaaccccgggtttt aaaaaaaacgttttt acccccggggggttt aaaccgggggggttt aaaaaaccccttttt accccccccggtttt aagggggggggggtt aaacccccgggtttt aaaaaccggggtttt aacccgggggggttt aaaaggggggggttt aaaaacccccttttt ccccccggggggttt aaaaaaaccgttttt aaaaaagggggtttt acgggggggggggtt aaccccccgggtttt cccccccccggtttt aaaacccggggtttt aaaaccccccttttt accccgggggggttt aaaaaaaaggttttt aaaaaacccgttttt aaacggggggggttt ccgggggggggggtt acccccccgggtttt aaaccccggggtttt aaaaacgggggtttt aaaaaccccgttttt aaacccccccttttt cccccgggggggttt aaccggggggggttt aaaaaaacggttttt aacccccggggtttt aaaaccgggggtttt ccccccccgggtttt acccggggggggttt aaaacccccgttttt aaccccccccttttt aaaaaaccggttttt aaagggggggggttt aaacccgggggtttt accccccggggtttt aaaaaggggggtttt ccccggggggggttt aaaccccccgttttt acccccccccttttt aaaaaaagggttttt aacgggggggggttt aaaaacccggttttt aaaacggggggtttt aaccccgggggtttt cccccccggggtttt aaaaccccggttttt accgggggggggttt ccccccccccttttt aaaaaacgggttttt aacccccccgttttt acccccgggggtttt aaaaaaaactttttt aaaccggggggtttt aaacccccggttttt cccgggggggggttt aaggggggggggttt accccccccgttttt aaaaaccgggttttt aaaagggggggtttt aacccggggggtttt aaaaaaacctttttt ccccccgggggtttt aaaaaaggggttttt cccccccccgttttt acggggggggggttt aaccccccggttttt aaaacccgggttttt accccggggggtttt aaacgggggggtttt aaaaaaaagtttttt aaaaaaccctttttt acccccccggttttt ccggggggggggttt aaaaacggggttttt aaaccccgggttttt aaaaaaacgtttttt aaaaacccctttttt cccccggggggtttt aaccgggggggtttt aaaaccggggttttt ccccccccggttttt aacccccgggttttt aaaggggggggtttt aaaaccccctttttt acccgggggggtttt aaaaaaccgtttttt aaaaagggggttttt cgggggggggggttt accccccgggttttt aaacccggggttttt aaacccccctttttt aacggggggggtttt aaaaacccgtttttt ccccgggggggtttt aaaaaaaggtttttt cccccccgggttttt aaccccggggttttt aaaacgggggttttt aaccccccctttttt aaaaaacggtttttt accggggggggtttt aaaaccccgtttttt aaaccgggggttttt acccccggggttttt acccccccctttttt aagggggggggtttt aaaaaccggtttttt cccggggggggtttt aaacccccgtttttt aacccgggggttttt aaaaggggggttttt ccccccggggttttt aaaaaagggtttttt aaaacccggtttttt acgggggggggtttt aaccccccgtttttt aaaaaaaattttttt aaacggggggttttt accccgggggttttt aaaccccggtttttt ccgggggggggtttt acccccccgtttttt aaaaacgggtttttt aaccggggggttttt aaaaaaacttttttt cccccgggggttttt aaaaccgggtttttt ccccccccgtttttt aggggggggggtttt aacccccggtttttt aaaaaaccttttttt acccggggggttttt aaagggggggttttt cggggggggggtttt aaaaaggggtttttt aaacccgggtttttt accccccggtttttt aacgggggggttttt ccccggggggttttt aaaaacccttttttt aaaaaaagttttttt aaccccgggtttttt cccccccggtttttt aaaacggggtttttt aaaaaacgttttttt accgggggggttttt aaaaccccttttttt acccccgggtttttt aaaccggggtttttt cccgggggggttttt aaaaaccgttttttt aaggggggggttttt aaacccccttttttt ccccccgggtttttt aacccggggtttttt aaaagggggtttttt aaaacccgttttttt aaaaaaggttttttt acggggggggttttt aaccccccttttttt accccggggtttttt aaacgggggtttttt aaaaacggttttttt ccggggggggttttt aaaccccgttttttt acccccccttttttt cccccggggtttttt aaccgggggtttttt aaaaccggttttttt agggggggggttttt ccccccccttttttt aacccccgttttttt aaaggggggtttttt acccgggggtttttt cgggggggggttttt aaacccggttttttt accccccgttttttt aaaaagggttttttt ccccgggggtttttt aacggggggtttttt aaaaaaatttttttt cccccccgttttttt aaccccggttttttt aaaacgggttttttt accggggggtttttt aaaaaactttttttt ggggggggggttttt acccccggttttttt aaaccgggttttttt cccggggggtttttt aaaaacctttttttt aagggggggtttttt aaaaggggttttttt ccccccggttttttt aacccgggttttttt aaaaaagtttttttt acgggggggtttttt aaaaccctttttttt aaacggggttttttt accccgggttttttt ccgggggggtttttt aaaaacgtttttttt aaacccctttttttt aaccggggttttttt cccccgggttttttt aaaaccgtttttttt aaccccctttttttt aggggggggtttttt acccggggttttttt aaagggggttttttt aaacccgtttttttt cggggggggtttttt acccccctttttttt aaaaaggtttttttt ccccggggttttttt aacgggggttttttt aaaacggtttttttt aaccccgtttttttt ccccccctttttttt accgggggttttttt aaaccggtttttttt gggggggggtttttt acccccgtttttttt aaggggggttttttt cccgggggttttttt aaaagggtttttttt aacccggtttttttt ccccccgtttttttt acggggggttttttt accccggtttttttt aaacgggtttttttt aaaaacttttttttt ccggggggttttttt cccccggtttttttt aaccgggtttttttt aaaaccttttttttt agggggggttttttt acccgggtttttttt aaaggggtttttttt aaaaagttttttttt aaacccttttttttt cgggggggttttttt ccccgggtttttttt aacggggtttttttt aaaacgttttttttt aaccccttttttttt accggggtttttttt aaaccgttttttttt acccccttttttttt aagggggtttttttt cccggggtttttttt aacccgttttttttt aaaaggttttttttt acgggggtttttttt aaacggttttttttt accccgttttttttt ccgggggtttttttt cccccgttttttttt aaccggttttttttt aggggggtttttttt aaagggttttttttt acccggttttttttt cggggggtttttttt aacgggttttttttt ccccggttttttttt aaaactttttttttt accgggttttttttt aaacctttttttttt gggggggtttttttt aaggggttttttttt cccgggttttttttt aaaagtttttttttt aaccctttttttttt acggggttttttttt aaacgtttttttttt acccctttttttttt ccggggttttttttt aaccgtttttttttt agggggttttttttt acccgtttttttttt aaaggtttttttttt aacggtttttttttt accggtttttttttt ggggggttttttttt aagggtttttttttt cccggtttttttttt acgggtttttttttt aaacttttttttttt ccgggtttttttttt aaccttttttttttt aggggtttttttttt cggggtttttttttt aacgttttttttttt accgttttttttttt gggggtttttttttt aaggttttttttttt ccggttttttttttt cgggttttttttttt acctttttttttttt ggggttttttttttt
|
|---|