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><