473,326 Members | 2,048 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Python code written in 1998, how to improve/change it?

Hello,
I am trying to study/understand OOP principles using Python. I have
found following code http://tinyurl.com/a4zkn about FSM (finite state
machine) on this list, which looks quite useful for my purposes. As
this code was posted long time ago (November 1998) I would like to ask
if the principles used in this code are still valid in the "modern"
Python and if/how it can be improved (revrited) using futures of
current version of Python.
Thanks for your comments for a "newbie" and for your patience.
Petr Jakes

Jan 19 '06 #1
41 2463
Petr Jakes wrote:
Hello,
I am trying to study/understand OOP principles using Python. I have
found following code http://tinyurl.com/a4zkn about FSM (finite state
machine) on this list, which looks quite useful for my purposes. As
this code was posted long time ago (November 1998) I would like to ask
if the principles used in this code are still valid in the "modern"
Python and if/how it can be improved (revrited) using futures of
current version of Python.
Thanks for your comments for a "newbie" and for your patience.


Python places great store on backwards-compatibility. Consequently I'd
suggest you try the code out, and report any problems you find back on
this list. I'd give you odds it will work.

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

Jan 19 '06 #2
Petr Jakes wrote:
Hello,
I am trying to study/understand OOP principles using Python. I have
found following code http://tinyurl.com/a4zkn about FSM (finite state
machine) on this list, which looks quite useful for my purposes. As
this code was posted long time ago (November 1998) I would like to ask
if the principles used in this code are still valid in the "modern"
Python and if/how it can be improved (revrited) using futures of
current version of Python.
Thanks for your comments for a "newbie" and for your patience.
Petr Jakes


Python has no goto.

If you think about the possible execution paths through a function, you
can represent that as a finite state machine: A FSM is just a graph, and
in a function, you get a FSM by treating each statement as a node, and
statements that can follow that statement (in the execution order) have
a (directed) edge to them (let's ignore exceptions for the moment). So for:

a=b
if a == 3:
z = 0
else:
z = 1
print 'spam'

we get:
(a=b) -> (if a == 3) -> (z = 0)
| |
(z = 1) -> (print 'spam)

Now, when we want to emulate a FSM in a function directly (rather than
some slower table-driven scheme), we need to use the constructs provided
by the language. But simple 'if' statements just don't cut it. We end up
with:

while state != 'final':
if state == 1:
# do state 1 stuff here
state = 3
elif state == 2:
# if cond:
state == 1
else:
state == 99
elif
...
else:
# unknown state

Problem with this approach is that, on average, you'll have n/2
comparisons of the state variable. What you want is to jump directly
from state 1 to state 3 without having to go anywhere else. You want a goto.

Another goto-less way is with functions. Each function is a state, which
sets a global function variable to the next state-function:

def f_state_1():
global func
# do state 1
func = f_state_3

def f_state_2():
global func
# do state_2 stuff
if cond:
func = f_state_1
else:
func = f_state_99

#etc.

func = f_state_1 # start_state

while func != None:
func()
We've eliminated the numerous comparisons, and it is, arguably, more
pythonic. But now you have a function-call overhead on each state
transition, and any information shared between states has to be in an
enclosing scope.

We want a goto.

Unfortunately, this is about the only problem I can think of where gotos
are useful. And for reasons well explained elsewhere, gotos are Not Good.

I've solved this in a very efficient, but rather unpythonic way.

First, you write (or generate) the code in the first way indicated
above. Lots of inefficient 'if' statements in one big function (say,
'fsm'). Then, you write another function (say 'gotoize') which takes fsm
as an argument, and *changes the byte code* of the fsm code object to
add JUMP_ABSOLUTE bytecodes (i.e. gotos) where the 'state' variable gets
reassigned.
fsm can then be decorated with gotoize, and you have a very fast (for
python) FSM. You are, essentially, doing some (fairly simple) byte-code
optimisation.

I can dig out the code if you are interested (except it's pretty untidy
at the moment. I'd be ashamed to show it in it's current state :-)

Ooops. I just reread your post and you claim (or is that plead?)
"newbie" status. Sorry if this is over your head. Hope it helps anyway.

Cheers,
Carl.
Jan 19 '06 #3
On Fri, 20 Jan 2006 10:27:58 +1300,
Carl Cerecke <cd*@maxnet.co.nz> wrote:
Petr Jakes wrote:
[ a query regarding some 1998 python code that implements a finite state
machine ]
Python has no goto.
Thank goodness!
func = f_state_1 # start_state while func != None:
func() We've eliminated the numerous comparisons, and it is, arguably, more
pythonic ...
Agreed.
... now you have a function-call overhead on each state transition ...
Have you profiled your code and demonstrated that this particular
function call consumes too much time?

If you can't stand the overhead of one [extra, parameterless] function
call per transition, especially *after* having eliminated the numerous
comparisons, then Python may not be the best tool for the job.
... and any information shared between states has to be in an
enclosing scope.
Well, no, not exactly. Consider an instance of a class that contains
its own data (and perhaps some of its own transition functions) but
inherits the basic state machine machinery from a finite state machine
class (or simply passes itself to a function that implements a finite
state machine by examining attributes of its argument).

And then there are (or should be!) purists who will claim that if your
state machine requires information to be shared between states, then you
don't have enough states! ;-)
We want a goto.


No, we don't.

Regards,
Dan

--
Dan Sommers
<http://www.tombstonezero.net/dan/>
Jan 19 '06 #4
On Fri, 20 Jan 2006 10:27:58 +1300 in comp.lang.python, Carl Cerecke
<cd*@maxnet.co.nz> wrote:

[...]

Python has no goto.
+1

[...]
We want a goto.


-1

Regards,
-=Dave

--
Change is inevitable, progress is not.
Jan 19 '06 #5
Carl Cerecke wrote:
Python has no goto.


Not in the standard library. You have to download the module:
http://www.entrian.com/goto/

;)

STeVe
Jan 19 '06 #6
Dave Hansen wrote:
On Fri, 20 Jan 2006 10:27:58 +1300 in comp.lang.python, Carl Cerecke
<cd*@maxnet.co.nz> wrote:

[...]
Python has no goto.

+1

[...]
We want a goto.

-1


I agree entirely. My (rather unclearly made) point was that, for the
particular application (FSM), an unrestricted jump is really handy. Not
that we want goto in python (Eurghhhh!!) just to make this one case easier.

I learnt programming on a Commodore-64 where BASIC programs where
required to be liberally sprinkled with gotos (No else. Only one,
global, scope. No real functions). I know first hand the pain gotos can
inflict. We don't want to go back there.

But. They are still really handy for directly implementing a FSM in
code! Hence my JUMP_ABSOLUTE bytecode rewrite hack for FSMs.

Cheers,
Carl.
Jan 19 '06 #7
Dan Sommers wrote:
On Fri, 20 Jan 2006 10:27:58 +1300,
Carl Cerecke <cd*@maxnet.co.nz> wrote:
... now you have a function-call overhead on each state transition ...

Have you profiled your code and demonstrated that this particular
function call consumes too much time?


Yes. For a parser reading a reasonable size input file, the difference
is large enough to be noticeable.
If you can't stand the overhead of one [extra, parameterless] function
call per transition, especially *after* having eliminated the numerous
comparisons, then Python may not be the best tool for the job.


Maybe. Except the bytecode *is* quite fast enough. There is just no way
of writing python code so the compiler can generate that bytecode. Hence
the JUMP_ABSOLUTE bytecode rewrite hack.

Cheers,
Carl.
Jan 19 '06 #8
Thanks for your comments,
The mentioned "8 years old" code actually works somehow.

I am trying to solve very similar problem about FSM as the code in the
example does and I do not want to be overburden by the if/elif stuff or
by declaring state functions (which IMHO is very similar approach as
if/elif).

Because of above mentioned, something like FSM-generator looks as a way
to go for me (if I can judge with my poor skills).

I am using Steve's book "Python Web Programming" which is actually the
best I have found about OOP, classes etc. but as a newbie I am just
lost with subclass and mapping attributes etc. while trying to study
the code in the example (http://tinyurl.com/a4zkn).

All I wanted to know, if, thanks to the improvements in the Python
functionality over the years, it is possible to simplify somhow the old
code.

Otherwise I have to dig through :)

Petr Jakes

PS:
I agree and I do understand the reasons why NOT to use GOTO statements
in the code (aka spaghetti code).

Jan 20 '06 #9
Steven Bethard wrote:
Carl Cerecke wrote:
Python has no goto.

Not in the standard library. You have to download the module:
http://www.entrian.com/goto/


Haha! Sure. But have you seen how it's implemented? I don't think it
will win many performace prizes. Nifty hack though.

Cheers,
Carl.
Jan 20 '06 #10
On 19 Jan 2006 15:53:54 -0800, Petr Jakes <pe**@tpc.cz> wrote:
Thanks for your comments,
The mentioned "8 years old" code actually works somehow.

I am trying to solve very similar problem about FSM as the code in the
example does and I do not want to be overburden by the if/elif stuff or
by declaring state functions (which IMHO is very similar approach as
if/elif).

I'm not sure why nobody else in this thread said it, but the most
common way of implementing state machines I've seen in Python (unless
theres only a couple states you can manage with if/elif) is to use a
dict to map states to callables.
Because of above mentioned, something like FSM-generator looks as a way
to go for me (if I can judge with my poor skills).

I am using Steve's book "Python Web Programming" which is actually the
best I have found about OOP, classes etc. but as a newbie I am just
lost with subclass and mapping attributes etc. while trying to study
the code in the example (http://tinyurl.com/a4zkn).

All I wanted to know, if, thanks to the improvements in the Python
functionality over the years, it is possible to simplify somhow the old
code.

Otherwise I have to dig through :)

Petr Jakes

PS:
I agree and I do understand the reasons why NOT to use GOTO statements
in the code (aka spaghetti code).

--
http://mail.python.org/mailman/listinfo/python-list

Jan 20 '06 #11
Chris Mellon wrote:
I'm not sure why nobody else in this thread said it, but the most
common way of implementing state machines I've seen in Python (unless
theres only a couple states you can manage with if/elif) is to use a
dict to map states to callables.


Ah. Well, my post suggested, as one option, the callables call
each other directly. No mapping required. But if you want a dict
in there somewhere, feel free to put one in :-)

I was complaining about the function-call overhead of this method
though, which can be quite significant for a FSM where each state
does only a little processing, and there are many transitions -
such as in a parser reading in a large file.

The byte-code rewriting hack mentioned in a previous post
eliminates this overhead. But, I concede, is somewhat ugly.

Cheers,
Carl.
Jan 20 '06 #12
Carl Cerecke wrote:
Chris Mellon wrote:
I'm not sure why nobody else in this thread said it, but the most
common way of implementing state machines I've seen in Python (unless
theres only a couple states you can manage with if/elif) is to use a
dict to map states to callables.

Ah. Well, my post suggested, as one option, the callables call
each other directly.


Doh! No I didn't. And they shouldn't. Otherwise the call stack
gets out of hand. But I did suggest that each callable representing a
state set a global variable, just before it returns, to the callable
representing the next state to be called. Still no map required. Just a
while loop. In any case, the function call/return is wasted cycles.

Cheers,
Carl.
Jan 20 '06 #13
Carl Cerecke wrote:
Carl Cerecke wrote:
Ah. Well, my post suggested, as one option, the callables call
each other directly.


Doh! No I didn't. And they shouldn't. Otherwise the call stack
gets out of hand. But I did suggest that each callable representing a
state set a global variable, just before it returns, to the callable
representing the next state to be called. Still no map required. Just a
while loop. In any case, the function call/return is wasted cycles.


I believe the more modern approach to this is to use generators in some
way, yield each other as the next state. This way you avoid all almost
all the function call overhead (the part that takes significant time,
which is setting up the stack frame) and don't have to resort to
bytecode hacks for better performance.

Of course, if you have a state machine with many small states each doing
a tiny bit of processing and you're still concerned over performance,
you probably should be looking into Pysco or Pyrex and avoid making your
code really unreadable.

-Peter

Jan 20 '06 #14

Petr> Hello, I am trying to study/understand OOP principles using
Petr> Python. I have found following code http://tinyurl.com/a4zkn about
Petr> FSM (finite state machine) on this list, which looks quite useful
Petr> for my purposes. As this code was posted long time ago (November
Petr> 1998) I would like to ask if the principles used in this code are
Petr> still valid in the "modern" Python and if/how it can be improved
Petr> (revrited) using futures of current version of Python.

A more up-to-date version of my finite state machine class (referenced in
the 1998 post you refer to) is available here:

http://orca.mojam.com/~skip/python/fsm.py

It's still in use, though I haven't written anything new with it in a year
or so.

Skip
Jan 20 '06 #15
Steven Bethard schrieb:
Carl Cerecke wrote:
Python has no goto.

Not in the standard library. You have to download the module:
http://www.entrian.com/goto/

;)

STeVe

This remerbers me to VATICAL, a famous programming language from the 80s.

http://www.uni-weimar.de/~mildenbe/s...l/vatical.html

It's in German only and I'm not aware of a English translation.

Please be aware that content of that page is not political correct and
may offend your religious sensibilities.

Hans Georg
Jan 20 '06 #16
On Thu, 19 Jan 2006 23:16:57 -0500, Peter Hansen <pe***@engcorp.com> wrote:
Carl Cerecke wrote:
Carl Cerecke wrote:
Ah. Well, my post suggested, as one option, the callables call
each other directly.


Doh! No I didn't. And they shouldn't. Otherwise the call stack
gets out of hand. But I did suggest that each callable representing a
state set a global variable, just before it returns, to the callable
representing the next state to be called. Still no map required. Just a
while loop. In any case, the function call/return is wasted cycles.


I believe the more modern approach to this is to use generators in some
way, yield each other as the next state. This way you avoid all almost
all the function call overhead (the part that takes significant time,
which is setting up the stack frame) and don't have to resort to
bytecode hacks for better performance.

Of course, if you have a state machine with many small states each doing
a tiny bit of processing and you're still concerned over performance,
you probably should be looking into Pysco or Pyrex and avoid making your
code really unreadable.

How about something like
actions = dict( ... a=compile('print "A"; state="b"','','exec'),
... b=compile('print "B"; state="c"','','exec'),
... c=compile('print "C"; state=None','','exec')
... ) state = 'a'
while state: eval(actions[state])

...
A
B
C

Regards,
Bengt Richter
Jan 20 '06 #17
On Fri, 20 Jan 2006 10:27:58 +1300, Carl Cerecke wrote:
We want a goto.

Unfortunately, this is about the only problem I can think of where gotos
are useful. And for reasons well explained elsewhere, gotos are Not Good.

I've solved this in a very efficient, but rather unpythonic way.


There is a module that does both GOTO and COMEFROM.

http://www.entrian.com/goto/

PLEASE don't use it in real code.

--
Steven.

Jan 21 '06 #18
Bengt Richter wrote:
On Thu, 19 Jan 2006 23:16:57 -0500, Peter Hansen <pe***@engcorp.com> wrote: How about something like
>>> actions = dict( ... a=compile('print "A"; state="b"','','exec'),
... b=compile('print "B"; state="c"','','exec'),
... c=compile('print "C"; state=None','','exec')
... ) >>> state = 'a'
>>> while state: eval(actions[state])

...
A
B
C


Good idea. But we can eliminate the dictionary lookup:

a1 = compile('print "A"; state=b1','','exec')
b1 = compile('print "B"; state=c1','','exec')
c1 = compile('print "C"; state=None','','exec')

state = a1
while state:
eval(state)
Cheers,
Carl
Jan 22 '06 #19
Sorry, I can't get in. Can you please show me, how to use your approach
on the simple push/push ON/OFF button for example please?

PS: seriously it is not a homework :) and I feel it like a shame I am
asking such a simple questions :(

States: ON, OFF
Transition event: "push", "lift"

transition diagram:
=========================

___ lift
| |
_V___|__
,->| ON |__
| |________| |
lift | | push
| ________ |
'--| OFF |<-'
|________|
^ |
|___|push

Jan 22 '06 #20
Sorry for the typo in my previous posting. Of course it has to be: ....
simple liftt/push ON/OFF button....

Jan 22 '06 #21
Petr Jakes wrote:
Sorry, I can't get in. Can you please show me, how to use your approach
on the simple push/push ON/OFF button for example please?

PS: seriously it is not a homework :) and I feel it like a shame I am
asking such a simple questions :(

States: ON, OFF
Transition event: "push", "lift"

transition diagram:
=========================

___ lift
| |
_V___|__
,->| ON |__
| |________| |
lift | | push
| ________ |
'--| OFF |<-'
|________|
^ |
|___|push


As a starting point, how about:

l = 'lift'
p = 'push'

action_sequence = [l,p,p,l,l,p,l,p,None]
next_action = iter(action_sequence).next

s_on = compile('''
print 'on'
action = next_action()
if action == 'lift':
state = s_on
elif action == 'push':
state = s_off
else:
state = None
''','','exec')

s_off = compile('''
print 'off'
action = next_action()
if action == 'lift':
state = s_on
elif action == 'push':
state = s_off
else:
state = None
''','','exec')
state = s_on # start state
while state:
eval(state)

Cheers,
Carl
Jan 23 '06 #22
On Mon, 23 Jan 2006 08:53:59 +1300, Carl Cerecke <cd*@maxnet.co.nz> wrote:
Bengt Richter wrote:
On Thu, 19 Jan 2006 23:16:57 -0500, Peter Hansen <pe***@engcorp.com> wrote:

How about something like
>>> actions = dict(

... a=compile('print "A"; state="b"','','exec'),
... b=compile('print "B"; state="c"','','exec'),
... c=compile('print "C"; state=None','','exec')
... )
>>> state = 'a'
>>> while state: eval(actions[state])

...
A
B
C


Good idea. But we can eliminate the dictionary lookup:

a1 = compile('print "A"; state=b1','','exec')
b1 = compile('print "B"; state=c1','','exec')
c1 = compile('print "C"; state=None','','exec')

state = a1
while state:
eval(state)

Cool. But unfortunately, neither version works inside a function's local namespace.
Using exec instead of eval seems to do it in either context though.
Now, how can we get optimized code (i.e., LOAD_FAST vs LOAD_NAME etc in a1 etc)
without byte code hackery?

Regards,
Bengt Richter
Jan 23 '06 #23
On Fri, 20 Jan 2006 05:16:57 +0100, Peter Hansen wrote
(in article <ma**************************************@python.o rg>):
I believe the more modern approach to this is to use generators in some
way, yield each other as the next state. This way you avoid all almost
all the function call overhead (the part that takes significant time,
which is setting up the stack frame) and don't have to resort to
bytecode hacks for better performance.


Dumb question from a endless newbie scripting dilettant:

Do you have a reference to a cookbook example for this method?

Sidequestion: As I understand it, as a general rule generators are more
efficient than functions in any case where the function is called several
times, right? So basically if I want to write a long-running program in
Python, it would make sense to code all functions that are likely to be
called more than once as generators...

TIA,

Sincerely,

Wolfgang Keller

Jan 24 '06 #24
Wolfgang Keller wrote:
On Fri, 20 Jan 2006 05:16:57 +0100, Peter Hansen wrote
(in article <ma**************************************@python.o rg>):

I believe the more modern approach to this is to use generators in some
way, yield each other as the next state. This way you avoid all almost
all the function call overhead (the part that takes significant time,
which is setting up the stack frame) and don't have to resort to
bytecode hacks for better performance.

Dumb question from a endless newbie scripting dilettant:

Do you have a reference to a cookbook example for this method?


It turns out that generators are more efficient than the eval function
excuting bits of compiled code. About 20-25% faster.

However, the generators exhibit some weird behaviour.

The included code shows an example using a compile/eval FSM method, and
a generator method. Note, in particular, the pattern of ids of the
generator objects. I had expected some complications in the ids, but not
a repeatable sequence of length 3 after the first generator object.

What is going on? Anybody?

#!/usr/bin/env python

import time

s_on = compile('''
print 'on'
action = next_action()
if action == 'lift':
state = s_on
elif action == 'push':
state = s_off
else:
state = None
''','','exec')

s_off = compile('''
print 'off'
action = next_action()
if action == 'lift':
state = s_on
elif action == 'push':
state = s_off
else:
state = None
''','','exec')
def g_on():

print "on"
action = next_action()
if action == 'lift':
yield g_on()
elif action == 'push':
yield g_off()
else:
yield None

def g_off():

print "off"
action = next_action()
if action == 'lift':
yield g_on()
elif action == 'push':
yield g_off()
else:
yield None
def actions(n):
import random
for i in range(n-1):
yield random.choice(['lift','push'])
yield None

#r = 1000000
r = 10
next_action = actions(r).next

#a = time.clock()
while next_action():
pass
#z = time.clock()
#print "action generator:",z-a
next_action = actions(r).next
#print "---"
state = s_on # start state
#a = time.clock()
while state:
eval(state)
#z = time.clock()
#print z-a
print "---"

next_action = actions(r).next
s_g_on = g_on()
s_g_off = g_off()
state = s_g_on
#a = time.clock()
while state:
print id(state)
state = state.next()
#z = time.clock()
#print z-a
#Cheers,
#Carl.
Jan 24 '06 #25
On Tue, 24 Jan 2006 21:19:26 +0100, Carl Cerecke wrote
(in article <43******@usenet01.boi.hp.com>):
def g_on():

print "on"
action = next_action()
if action == 'lift':
yield g_on()
elif action == 'push':
yield g_off()
else:
yield None

def g_off():

print "off"
action = next_action()
if action == 'lift':
yield g_on()
elif action == 'push':
yield g_off()
else:
yield None


Amazing.

Executable pseudo-code, really. :-)

And that's even (run-time) efficient?

Tanks a lot,

Sincerely,

Wolfgang Keller

Jan 24 '06 #26

Wolfgang> So basically if I want to write a long-running program in
Wolfgang> Python, it would make sense to code all functions that are
Wolfgang> likely to be called more than once as generators...

If they need to resume their calculations from where they left off after the
last yield.

Skip
Jan 24 '06 #27
Carl Cerecke wrote:
It turns out that generators are more efficient than the eval function
excuting bits of compiled code. About 20-25% faster.


why are you using generators to return things from a function, when
you can just return the things ?

def f_on():
print "on"
action = next_action()
if action == 'lift':
return f_on
elif action == 'push':
return f_off

def f_off():
print "off"
action = next_action()
if action == 'lift':
return f_on
elif action == 'push':
return f_off

state = f_on
while state:
state = state()

</F>

Jan 24 '06 #28
Fredrik Lundh wrote:
Carl Cerecke wrote:

It turns out that generators are more efficient than the eval function
excuting bits of compiled code. About 20-25% faster.

why are you using generators to return things from a function, when
you can just return the things ?


Trying to find the fastest way to implement finite state machine.
The included file times 4 different ways, with functions the fastest.

The reason, I think, for the unusual sequence if id()s of the generators
- see grandparent post - (and the reason for their poor performance
compared to functions), is because the reference to the generator is
being lost, then another generator is being created with the same id.
Properly done, I would expect generators to out perform functions.

These are the numbers I get on a P3 600:
$ ./foo.py
action generator overhead: 13.25
---
exec: 8.7
---
eval: 10.09
---
generators: 6.68
---
functions: 3.37
#!/usr/bin/env python

import time

s_on = compile('''
#print 'on'
action = next_action()
if action == 'lift':
state = s_on
elif action == 'push':
state = s_off
else:
state = None
''','','exec')

s_off = compile('''
#print 'off'
action = next_action()
if action == 'lift':
state = s_on
elif action == 'push':
state = s_off
else:
state = None
''','','exec')

def f_on():
action = next_action()
if action == 'lift':
return f_on
elif action == 'push':
return f_off
else:
return None

def f_off():
action = next_action()
if action == 'lift':
return f_on
elif action == 'push':
return f_off
else:
return None
def g_on():

#print "on"
action = next_action()
if action == 'lift':
yield g_on()
elif action == 'push':
yield g_off()
else:
yield None

def g_off():

#print "off"
action = next_action()
if action == 'lift':
yield g_on()
elif action == 'push':
yield g_off()
else:
yield None
def actions(n):
import random
for i in range(n-1):
yield random.choice(['lift','push'])
yield None

r = 1000000
#r = 10
next_action = actions(r).next

a = time.clock()
while next_action():
pass
z = time.clock()
print "action generator overhead:",z-a
common = z-a

print "---"
next_action = actions(r).next
state = s_on # start state
a = time.clock()
while state:
exec state
z = time.clock()
print "exec:",z-a-common

print "---"
next_action = actions(r).next
state = s_on # start state
a = time.clock()
while state:
eval(state)
z = time.clock()
print "eval:",z-a-common

print "---"
next_action = actions(r).next
s_g_on = g_on()
s_g_off = g_off()
state = s_g_on
a = time.clock()
while state:
#print id(state)
state = state.next()
z = time.clock()
print "generators:",z-a-common

print "---"
next_action = actions(r).next
state = f_on
a = time.clock()
while state:
state = state()
z = time.clock()
print "functions:",z-a-common
Jan 24 '06 #29
Carl Cerecke wrote:
Fredrik Lundh wrote:
Carl Cerecke wrote:

It turns out that generators are more efficient than the eval function
excuting bits of compiled code. About 20-25% faster.


why are you using generators to return things from a function, when
you can just return the things ?

Trying to find the fastest way to implement finite state machine.
The included file times 4 different ways, with functions the fastest.

The reason, I think, for the unusual sequence if id()s of the generators
- see grandparent post - (and the reason for their poor performance
compared to functions), is because the reference to the generator is
being lost, then another generator is being created with the same id.
Properly done, I would expect generators to out perform functions.


Generator FSM done properly (well, better anyway). They are still almost
twice as slow as plain function calls, though.

def g_on():

while 1:
action = next_action()
if action == 'lift':
yield s_g_on
elif action == 'push':
yield s_g_off
else:
break
yield None

def g_off():

while 1:
action = next_action()
if action == 'lift':
yield s_g_on
elif action == 'push':
yield s_g_off
else:
break
yield None

def actions(n):
import random
for i in range(n-1):
yield random.choice(['lift','push'])
yield None

r = 1000000
#r = 10
next_action = actions(r).next
s_g_on = g_on()
s_g_off = g_off()
state = s_g_on

while state:
state = state.next()
z = time.clock()
Jan 24 '06 #30
Adding a continue statemtent after the yield statements yields :-) a
speed increase. Still not as good as functions though. (about 30% slower)

Cheers,
Carl

Carl Cerecke wrote:
Carl Cerecke wrote:
Generator FSM done properly (well, better anyway). They are still almost
twice as slow as plain function calls, though.

def g_on():

while 1:
action = next_action()
if action == 'lift':
yield s_g_on
elif action == 'push':
yield s_g_off
else:
break
yield None

def g_off():

while 1:
action = next_action()
if action == 'lift':
yield s_g_on
elif action == 'push':
yield s_g_off
else:
break
yield None

def actions(n):
import random
for i in range(n-1):
yield random.choice(['lift','push'])
yield None

r = 1000000
#r = 10
next_action = actions(r).next
s_g_on = g_on()
s_g_off = g_off()
state = s_g_on

while state:
state = state.next()
z = time.clock()

Jan 24 '06 #31
On Tue, 24 Jan 2006 14:58:27 -0600, sk**@pobox.com wrote:

Wolfgang> So basically if I want to write a long-running program in
Wolfgang> Python, it would make sense to code all functions that are
Wolfgang> likely to be called more than once as generators...

If they need to resume their calculations from where they left off after the
last yield.

Hm, I wonder how (all untested)

def foo(x,y):
return x**2+y**2
for pair in pairs: print foo(*pair)

would compare to

def bar(arglist):
while True:
x,y = arglist
yield x**2 + y**2
barargs = []
ibar = bar(barargs).next
for barargs[:] in pairs: print ibar()

Of course, for simple stuff there's always manual inlining ;-)

for x, y in pairs: print x**2, y**2

Hm, <bf warning> it might be interesting if one could bind arg list items of
a generator from the outside, e.g.,

def gfoo(x, y):
while True:
yield x**2 + y**2

ifoo = gfoo('dummy','dummy') # or first pair
for ifoo.x, ifoo.y in pairs: print ifoo.next()

Regards,
Bengt Richter
Jan 25 '06 #32
> > So basically if I want to write a long-running program in
Python, it would make sense to code all functions that are
likely to be called more than once as generators...

This was meant as a question.
If they need to resume their calculations from where they left off after the
last yield.


Well, no, independently from that.

Just to avoid to inital overhead of the function call.

?

Sincerely,

Wolfgang Keller

Jan 25 '06 #33
Wolfgang Keller wrote:
So basically if I want to write a long-running program in
Python, it would make sense to code all functions that are
likely to be called more than once as generators...


This was meant as a question.
If they need to resume their calculations from where they left off after the
last yield.


Well, no, independently from that.

Just to avoid to inital overhead of the function call.

?


what makes you think that resuming a generator won't involve function
calls ?

</F>

Jan 25 '06 #34
> what makes you think that resuming a generator won't involve function
calls ?
That was not what I wrote.

I referred to what Peter Hansen <pe***@engcorp.com> wrote in
ma**************************************@python.or g:
I believe the more modern approach to this is to use generators in some
way, yield each other as the next state. This way you avoid all almost
all the function call overhead (the part that takes significant time,
which is setting up the stack frame)


The way I understand this, resuming a generator causes less overhead than the
inital overhead of a function call.

Again, I'm just a poor scripting dilettant who's asking questions.

Sincerely,

Wolfgang Keller

Jan 25 '06 #35
On Wed, 25 Jan 2006 12:33:17 +1300, Carl Cerecke <cd*@maxnet.co.nz> wrote:
Adding a continue statemtent after the yield statements yields :-) a
speed increase. Still not as good as functions though. (about 30% slower)

Cheers,
Carl

Carl Cerecke wrote:
Carl Cerecke wrote:
Generator FSM done properly (well, better anyway). They are still almost
twice as slow as plain function calls, though.
<snip>
I think I would use a generator to do state transitions, but make the state
external, or at least the part that's interesting to the outside world.

In this peculiar example the transition rules are the same for both states,
so you only need one implementation of the logic. So the example is not so nice.

def fsm(state, events): ... for action in events:
... if action == 'lift': state.name = 'ON'
... elif action == 'push': state.name = 'OFF'
... else:
... state.name = 'END'
... break
... yield state
... def actions(n): ... import random
... return iter([random.choice(['lift','push']) for i in range(n-1)] + [None])
... class State(object): pass ... def test(r=1000000): ... state = State()
... state.name = 'ON'
... from time import clock
... t0 = clock()
... for state in fsm(state, actions(r)): pass
... t1 = clock()
... print '%12.6f'%((t1-t0)/r)
... test(1000) 0.000058 test(1000) 0.000032 test(1000) 0.000032 test(100000) 0.000032 a = list(actions(10))
a ['lift', 'push', 'push', 'lift', 'push', 'lift', 'push', 'lift', 'lift', None] state = State()
state.name = 'START'
f = fsm(state, a)
for state in f: print state.name, ...
ON OFF OFF ON OFF ON OFF ON ON


Obviously you can keep state in the fsm generator by placing yields in different places and
looping in different ways, but always storing the externally interesting state as attributes
of the state parameter and yielding that to tell the world the latest. Since only attributes
are being modified, the original state binding could be used and the generator's yielded
value could be ignored, but it could be handy if the generator is passed around IWT.

The world could also feed info in as attributes of state. And other generators could share
the same external state variable and all kinds of weird things could be built ;-)

Regards,
Bengt Richter
Jan 25 '06 #36
Wolfgang Keller wrote:
The way I understand this, resuming a generator causes less overhead than the
inital overhead of a function call.


I don't have Python 2.4 handy, but it doesn't seem to be true in 2.3.
I'm not very proficient with generators though, so maybe I'm doing
something stupid here...
from __future__ import generators
def f(): .... return 1
.... def g(): .... while 1:
.... yield 1
.... it = g()
import time
def t(c, n): .... start = time.time()
.... for i in xrange(n):
.... c()
.... print time.time()-start
.... t(f,1000000) 0.277699947357 t(f,1000000) 0.279093980789 t(f,1000000) 0.270813941956 t(it.next,1000000) 0.297060966492 t(it.next,1000000) 0.263942956924 t(it.next,1000000) 0.293347120285

For refernce: def t0(c, n): .... start = time.time()
.... for i in xrange(n):
.... pass
.... print time.time()-start
.... t0(it.next,1000000)

0.0523891448975

Maybe the ratio is completely different in a newer Python than
2.3.4 (RH EL3 standard install). Or maybe it's very different if
there are plenty of local variables etc in f / g.

Jan 25 '06 #37
Wolfgang Keller wrote:
what makes you think that resuming a generator won't involve function
calls ?


That was not what I wrote.

I referred to what Peter Hansen <pe***@engcorp.com> wrote in
ma**************************************@python.or g:
I believe the more modern approach to this is to use generators in some
way, yield each other as the next state. This way you avoid all almost
all the function call overhead (the part that takes significant time,
which is setting up the stack frame)


The way I understand this, resuming a generator causes less overhead than the
inital overhead of a function call.


I think in the spirit of avoiding "premature optimization" and all
things related, now is the time to re-inject the other part of my
above-quoted posting, where I also said:

"""
Of course, if you have a state machine with many small states each doing
a tiny bit of processing and you're still concerned over performance,
you probably should be looking into Pysco or Pyrex and avoid making your
code really unreadable.
"""

-Peter

Jan 25 '06 #38

Wolfgang> So basically if I want to write a long-running program in
Wolfgang> Python, it would make sense to code all functions that are
Wolfgang> likely to be called more than once as generators...

Skip> If they need to resume their calculations from where they left off
Skip> after the last yield.

Bengt> Hm, I wonder how (all untested)
...
Bengt> would compare to
...

I was thinking about things like complex tokenizers. Take a look, for
example, at the SpamBayes tokenizer and think about how to implement it
without yield. Clearly it can be don (and not all that difficult). Still,
I think the generator version would be easier to understand and modify.

Skip
Jan 25 '06 #39
If they need to resume their calculations from where they left off
after the last yield.
Wolfgang> Well, no, independently from that.

Wolfgang> Just to avoid to inital overhead of the function call.

How do you pass in parameters? Consider:

def square(x):
return x*x

vs

def square(x)
while True:
yield x*x

How do you get another value of x into the generator?
def square(x): ... while True:
... yield x*x
... g = square(2)
g <generator object at 0x3b9d28> g.next() 4 g.next() 4 g.next(3)

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: expected 0 arguments, got 1

Skip
Jan 25 '06 #40
On Wed, 25 Jan 2006 15:50:27 -0600, sk**@pobox.com wrote:
>> If they need to resume their calculations from where they left off
>> after the last yield.
Wolfgang> Well, no, independently from that.

Wolfgang> Just to avoid to inital overhead of the function call.

How do you pass in parameters? Consider:

def square(x):
return x*x

vs

def square(x)
while True:
yield x*x

How do you get another value of x into the generator?
>>> def square(x): ... while True:
... yield x*x
... >>> g = square(2)
>>> g <generator object at 0x3b9d28> >>> g.next() 4 >>> g.next() 4 >>> g.next(3) Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: expected 0 arguments, got 1
def square(xbox): ... while True: yield xbox[0]*xbox[0]
... xbox = [3]
g = square(xbox)
g.next() 9 xbox[0]=4
g.next() 16 [g.next() for xbox[0] in xrange(10)]

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

One way to answer your question literally,
whatever it may do to your gag reflex ;-)

Regards,
Bengt Richter
Jan 26 '06 #41
To provide some feedback I vould like to show the code which works fine
for me as a FSM machine. As speed is not the crucial issue for my
application, I have decided to use an approach showed in the Skip
Montanaro's code.
http://orca.mojam.com/~skip/python/fsm.py
(it is using dictionary to store state/transition dependencies).

Tanks to all for your previous postings.

Petr Jakes

State machine example, for the pull/push button mentioned earlier in
this discussion thread

class FSM:
'''the "states" dictionary contains user defined "state/transition
table" in the format:
{'start_state': {'event': {'guard': ('action', 'end_state')}},
according to the actual "start_state", "event" and "guard"
combination,
the "execute" method reads the relevant "action" and "end_state"
from the "states" dictionary, then executes "action" and setup
"end_state" '''
def __init__(self):
self.states = {}

def add(self,start_state, event_trigger,event_guard,
action,newstate):
"""add a new "state/transition" information to the state
machine dictionary"""
if self.states.has_key(start_state)== False :
self.states[start_state]={}
if self.states[start_state].has_key(event_trigger)== False :
self.states[start_state][event_trigger]={}
if
self.states[start_state][event_trigger].has_key(event_guard)== False :
self.states[start_state][event_trigger][event_guard]={}
self.states[start_state][event_trigger][event_guard]=(action,
newstate)

def start(self, state):
"""set the start state"""
self.state = state

def execute(self, event,guard=None):
'''according to the actual "start_state", "event" and "guard"
combination
read the relevant "action" and "end_state from the
"states" dictionary,
then execute "action" and setup "end_state" '''
action, end_state = self.states[self.state][event][guard]
if action is not None:
apply(action, (self.state, event))
self.state = end_state
return

'''actions they has to be executed while the event occurs'''
def motor_off(state, input): print "pushing the switch to the OFF
position"
def motor_on(state, input): print "lifting the switch to the ON
position"
fsm = FSM()

'''we have to define "state/transition table" first,
wher state transitions are defined as:
('start_state', 'event', 'guard', 'action', 'end_state)'''
fsm.add("ON","lift",None,None,"ON")
fsm.add("ON","push",None,motor_off,"OFF")
fsm.add("OFF","push",None,None,"OFF")
fsm.add("OFF","lift",None,motor_on,"ON")

fsm.start("ON")
print "start state is", fsm.state
events=("push","push","push","lift","lift","push", "lift","push","lift","lift","lift","push","lif t")

for event in (events):

fsm.execute(event)
print "switch is ", fsm.state

Jan 28 '06 #42

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

68
by: Lad | last post by:
Is anyone capable of providing Python advantages over PHP if there are any? Cheers, L.
82
by: Edward Elliott | last post by:
This is just anecdotal, but I still find it interesting. Take it for what it's worth. I'm interested in hearing others' perspectives, just please don't turn this into a pissing contest. I'm in...
47
by: John Salerno | last post by:
I have to say, I'm having a very enjoyable time learning and using Python. I spent a year playing around with C# and I feel like I learned/know less about it than I do about Python from just the...
1
by: Petr Prikryl | last post by:
Do you think that the following could became PEP (pre PEP). Please, read it, comment it, reformulate it,... Abstract Introduction of the mechanism for language extensions via modules...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.