Hello Matti,

On 2010-01-27 15:17, bearophile wrote:

BCS:

Have you compared it to a decisition tree or lex style state
mechine?

I have now implemented that too, it was not an immediate thing to do
(I have removed the versions 2 to 5 to reduce code size on codepad):

http://codepad.org/zOmPeE13

The results are good:
Timings, ldc, seconds:
test1: 4.48 // normal string switch
test2: 2.98 // perfect hash
test3: 2.09
test4: 2.07
test5: 5.44 // AA. Tango AA opIn_r is bug-slow
test6: 1.18 // new result
I hope this is enough.
I have created that large finite state machine in D with a Python
program :-)
Your test6 is invalid: it reads beyond the bounds of the given array.
For example with input "th", it will check whether the third character
is 'i'; but the length of the array is only 2, so it shouldn't be
doing that.


A simple fix to that is to make he first transition of the state machine based on the length of the key.

that is, 'if' at the top becomes:

           switch(word.length) {
           case 13: goto S...:
           case 12: goto S...:
           case 11: goto S...:
           case 10: goto S...:
           case 9: goto S...:
           case 8: goto S...:
           case 7: goto S...:
           case 6: goto S...:
           case 5: goto S...:
           case 4: goto S...:
           case 3: goto S...:
           case 2: goto S...:

           default: goto UNREC;
           }

--

<IXOYE><


Reply via email to