Well, it doesn't quite rule them all, but it is fast: About three times faster than using one function per state. Faster than using generators. Faster than using code objects.
Some, possibly minor, problems: 1. The generated code is ugly. 2. The generated code can be quite large, depending on the shape of the FSM (Maximum theoretical size left as an exercise for the reader ;-) 3. Not as fast as byte code hacks, or using pyrex/psyco. Peter Hansen is right. One of those is likely a better solution if you don't need pure python. The example FSM has input alphabet ['a','b','c'] and looks like: state 0: a -> 1 b -> 2 c -> 1 state 1: a -> 1 b -> 3 c -> 2 state 2: a -> 1 b -> 2 c -> 3 state 3: a -> 2 b -> 3 c -> 0 The algorithm basically transforms the FSM into a tree of while loops, with breaks letting us go back up the tree, and a variable ("goto"!) telling us where the chain of breaks should stop. Note: 1. It would be more efficient with a labelled break (or a labelled continue) such as is available in Java. 2. There are some opportunities for optimisation of the generated code. Running this code will print out the generated FSM code for both a while/break implementation of the FSM and a function-based implementation. It then does some timing measurements. Cheers, Carl. #!/usr/bin/env python from StringIO import StringIO # number of random inputs fed to the FSM (if we are using that input generator) r = 1000000 #r = 10 # specific string of input chars (if we are using the appropriate input generator) inp = ['a','a','b','a','a','c','b','c','b','c','c','c','c','c','b'] # list of states, each state is a dict describing transitions to other states. states = [ {'a':1,'b':2,'c':1}, {'a':1,'b':3,'c':2}, {'a':1,'b':2,'c':3}, {'a':2,'b':3,'c':0}] ind = " " class State(object): def __init__(self, num): self.num = num self.gotos = {} def show(self, indent = ""): ''' Representaion of this state, and the states 'underneath' it ''' print indent+`self.num`+':' for i,g in self.gotos.items(): if type(g) == State: print indent+"-"+i+"->" g.show(indent+" ") else: print indent+"-"+i+"-> "+`g` def code(self, out, lvl): ''' Spit out code for a while/break based state machine ''' print >>out,lvl+"while 1: # state",self.num print >>out,lvl+ind+"#print '%d'"%self.num print >>out,lvl+ind+"n = next()" for i,g in self.gotos.items(): print >>out,lvl+ind+"if n == '"+i+"':" if type(g) == State: g.code(out,lvl+ind+ind) else: if g != self.num: print >>out,lvl+ind+ind+"goto = "+`g` print >>out,lvl+ind+ind+"break" else: print >>out,lvl+ind+ind+"continue" print >>out,lvl+ind+"if n == None: return",self.num print >>out,lvl+ind+"if goto != "+`self.num`+":" print >>out,lvl+ind+ind+"break" def functions(out,states, lvl = ""): ''' Spit out code for a function-based state machine ''' for num,transitions in enumerate(states): print >>out,lvl+"def state_"+`num`+"():" print >>out,lvl+ind+"#print '%d'"%num print >>out,lvl+ind+"n = next()" for i,g in transitions.items(): print >>out,lvl+ind+"if n == '"+i+"':" print >>out,lvl+ind+ind+"return state_"+`g` print >>out,lvl+ind+"if n == None: return None" start = State(0) # set up the hierarchy of State objects def dfs(state, history): for i,s in states[state.num].items(): if s in history: state.gotos[i] = s else: child = State(s) state.gotos[i] = child dfs(child, history+[s]) dfs(start,[start.num]) #print start #start.show() fun = StringIO() print >>fun,"def fsm():" start.code(fun," ") functions(fun,states) def next_gen(): # for when we want specific input for i in inp: print i yield i yield None import random def next_genr(): # for when we want lots of input for i in range(r): n = random.choice(['a','b','c']) #print n yield n yield None next = next_genr().next # show the generated code of both FSM implementations print fun.getvalue() exec fun.getvalue() import time # we want to ignore the cost of getting input, so we measure that first. a = time.clock() n = 1 while n: n = next() z = time.clock() in_time = z-a print "input time:",in_time print "--" next = next_genr().next a = time.clock() f = fsm() z = time.clock() print "while/break:",z-a-in_time next = next_genr().next a = time.clock() state = state_0 while state: state = state() z = time.clock() print "functions:",z-a-in_time -- http://mail.python.org/mailman/listinfo/python-list