Robert Feldt <feldt / ce.chalmers.se> writes:

> I'm contemplating the fastest way to implement state-machines and
> goto-like structures in Ruby. Don't worry, it's not that I'm reverting to
> some old programming style; the code will be auto-generated. However,
> there is a performance consideration so I'd like to generate as fast code 
> as possible.

Assuming:

1. The run time performance is dominated by the transition lookup, and

2. The states are numeric and relatively compact,

The following uses recursive arrays, and seems to be almost twice as
fast as the Hash-based version


Dave


     class DaveSM
       attr_accessor :state

       def initialize(start, transitions)
         @state = start
         @states = {}

         @transitions = []
         transitions.each do |k,v|
           row = []
           v.each do |tin, newstate|
             [ tin ].flatten.each do |token|
               row[token] = newstate
             end
           end if v
           @transitions[k] = row
           @states[row.id] = k
         end

         # make structure recursive
         @transitions.each do |row|
           row.collect! {|entry| entry && @transitions[entry]} if row
         end
       end

       def run(inputs)
         row = @transitions[@state]
         for i in inputs
           row = row[i]
         end
         @state = @states[row.id]
       end

       def states
         @states.values
       end
     end