FSM to Func: Difference between revisions
Adamcolton (talk | contribs) Created page with "How to convert a finite state machine to an efficient func The finite state machine can be written as a table, and that table can be flattened to a list. We apply successive ..." |
Adamcolton (talk | contribs) No edit summary |
||
| Line 10: | Line 10: | ||
I know this can work semi-efficiently from any list. Start with what ever number appears most. Look at bit affinity and slice affinity. Choose the operation that will change the most values to our target value. | I know this can work semi-efficiently from any list. Start with what ever number appears most. Look at bit affinity and slice affinity. Choose the operation that will change the most values to our target value. | ||
I need to watch the cost. I is already 2 ops, each layer is going to be another 3 to 5 ops. I'm not sure how many ops a map lookup is, but a table will beat this quickly if we're not careful. | |||
There is room for a lot of improvement though. The states don't need to be contiguous. And there can be multiple accept and reject values, particularly if they can be isolated to a few ranges. | There is room for a lot of improvement though. The states don't need to be contiguous. And there can be multiple accept and reject values, particularly if they can be isolated to a few ranges. | ||
Latest revision as of 00:42, 9 October 2015
How to convert a finite state machine to an efficient func
The finite state machine can be written as a table, and that table can be flattened to a list. We apply successive additions of other lists until the entire list is a single value.
Mutators
- (i&x)*y
- ( (i+x)>>y )*z
i = S<<8 + C
I know this can work semi-efficiently from any list. Start with what ever number appears most. Look at bit affinity and slice affinity. Choose the operation that will change the most values to our target value.
I need to watch the cost. I is already 2 ops, each layer is going to be another 3 to 5 ops. I'm not sure how many ops a map lookup is, but a table will beat this quickly if we're not careful.
There is room for a lot of improvement though. The states don't need to be contiguous. And there can be multiple accept and reject values, particularly if they can be isolated to a few ranges.