String compare performance

[Austin Hastings]

On 11/27/2010 11:53 AM, bearophile wrote:
> While translating a common Python script to D, I have found something interesting, so I have reduced it to a little benchmark.
>
> Below there is the reduced Python2 code (it uses Psyco), and a little program to generate some test data. The timing of the first D2 version is not good compared to the Python-Psyco program (the generation of the *300 array is a quick thing), so I have created two more D2 versions to show myself that D2 wasn't broken :-)
>
> The reduced code looks like a syntetic benchmark, but it has about the same performance profile of a 60 lines long Python script (the original code was using xrange(0,len(...)-3,3)  instead of xrange(len(...)-3), but the situation doesn't change much).
>

It's not clear to me if the point of your post is "how do I make this go 
faster?" or "Waa! D underperforms Python by default".

If it is the former, a state machine is probably the right answer for 
long input strings.

start -> E

E A,C,G:-> E
E T:-> T

T A:-> TA
T C:-> E
T G:-> TG
T T:-> T

TA A,G:-> E, {++count}
TA C:-> E
TA T:-> T

TG A:-> E, {++count}
TG C,G:-> E
TG T:-> T


Since the probability of failure is about .75, 0.5, {.5 or .75}, the 
overall comparison cost is about 1 + .25 + .125 = 1.375, times 
compare+loop times n, plus all the function call overhead, etc.

Using a DFA should reduce the cost to 1 * index, times n, assuming you 
are using a small alphabet (I'm guessing that your codons are 
ascii+uppercase only, table-size = 26).

=Austin