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

[Carl Cerecke]

Re: Weird generator id() behaviour (was Re: Python code written in1998,howtoimp rove/change it?)

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:[color=blue]
> 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()[/color]

[Bengt Richter]

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

On Tue, 24 Jan 2006 14:58:27 -0600, skip@pobox.com wrote:
[color=blue]
>
> 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.[/color]
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).ne xt
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','d ummy') # or first pair
for ifoo.x, ifoo.y in pairs: print ifoo.next()

Regards,
Bengt Richter

[Wolfgang Keller]

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

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

This was meant as a question.
[color=blue]
> If they need to resume their calculations from where they left off after the
> last yield.[/color]

Well, no, independently from that.

Just to avoid to inital overhead of the function call.

?

Sincerely,

Wolfgang Keller

[Fredrik Lundh]

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

Wolfgang Keller wrote:
[color=blue][color=green][color=darkred]
> > > 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...[/color][/color]
>
> This was meant as a question.
>[color=green]
> > If they need to resume their calculations from where they left off after the
> > last yield.[/color]
>
> Well, no, independently from that.
>
> Just to avoid to inital overhead of the function call.
>
> ?[/color]

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

</F>

[Wolfgang Keller]

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

> what makes you think that resuming a generator won't involve function[color=blue]
> calls ?[/color]

That was not what I wrote.

I referred to what Peter Hansen <peter@engcorp. com> wrote in
mailman.821.113 7730663.27775.p ython-list@python.org:
[color=blue]
> 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)[/color]

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

[Bengt Richter]

Re: Weird generator id() behaviour (was Re: Python code written in1998,howto improve/change it?)

On Wed, 25 Jan 2006 12:33:17 +1300, Carl Cerecke <cdc@maxnet.co. nz> wrote:
[color=blue]
>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:[color=green]
>> Carl Cerecke wrote:
>> Generator FSM done properly (well, better anyway). They are still almost
>> twice as slow as plain function calls, though.
>>[/color][/color]
<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.

[color=blue][color=green][color=darkred]
>>> def fsm(state, events):[/color][/color][/color]
... for action in events:
... if action == 'lift': state.name = 'ON'
... elif action == 'push': state.name = 'OFF'
... else:
... state.name = 'END'
... break
... yield state
...[color=blue][color=green][color=darkred]
>>> def actions(n):[/color][/color][/color]
... import random
... return iter([random.choice(['lift','push']) for i in range(n-1)] + [None])
...[color=blue][color=green][color=darkred]
>>> class State(object): pass[/color][/color][/color]
...[color=blue][color=green][color=darkred]
>>> def test(r=1000000) :[/color][/color][/color]
... 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)
...[color=blue][color=green][color=darkred]
>>> test(1000)[/color][/color][/color]
0.000058[color=blue][color=green][color=darkred]
>>> test(1000)[/color][/color][/color]
0.000032[color=blue][color=green][color=darkred]
>>> test(1000)[/color][/color][/color]
0.000032[color=blue][color=green][color=darkred]
>>> test(100000)[/color][/color][/color]
0.000032[color=blue][color=green][color=darkred]
>>> a = list(actions(10 ))
>>> a[/color][/color][/color]
['lift', 'push', 'push', 'lift', 'push', 'lift', 'push', 'lift', 'lift', None][color=blue][color=green][color=darkred]
>>> state = State()
>>> state.name = 'START'
>>> f = fsm(state, a)
>>> for state in f: print state.name,[/color][/color][/color]
...
ON OFF OFF ON OFF ON OFF ON ON[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

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

[Magnus Lycka]

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

Wolfgang Keller wrote:[color=blue]
> The way I understand this, resuming a generator causes less overhead than the
> inital overhead of a function call.[/color]

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...
[color=blue][color=green][color=darkred]
>>> from __future__ import generators
>>> def f():[/color][/color][/color]
.... return 1
....[color=blue][color=green][color=darkred]
>>> def g():[/color][/color][/color]
.... while 1:
.... yield 1
....[color=blue][color=green][color=darkred]
>>> it = g()
>>> import time
>>> def t(c, n):[/color][/color][/color]
.... start = time.time()
.... for i in xrange(n):
.... c()
.... print time.time()-start
....[color=blue][color=green][color=darkred]
>>> t(f,1000000)[/color][/color][/color]
0.277699947357[color=blue][color=green][color=darkred]
>>> t(f,1000000)[/color][/color][/color]
0.279093980789[color=blue][color=green][color=darkred]
>>> t(f,1000000)[/color][/color][/color]
0.270813941956[color=blue][color=green][color=darkred]
>>> t(it.next,10000 00)[/color][/color][/color]
0.297060966492[color=blue][color=green][color=darkred]
>>> t(it.next,10000 00)[/color][/color][/color]
0.263942956924[color=blue][color=green][color=darkred]
>>> t(it.next,10000 00)[/color][/color][/color]
0.293347120285

For refernce:[color=blue][color=green][color=darkred]
>>> def t0(c, n):[/color][/color][/color]
.... start = time.time()
.... for i in xrange(n):
.... pass
.... print time.time()-start
....[color=blue][color=green][color=darkred]
>>> t0(it.next,1000 000)[/color][/color][/color]
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.

[Peter Hansen]

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

Wolfgang Keller wrote:[color=blue][color=green]
>>what makes you think that resuming a generator won't involve function
>>calls ?[/color]
>
> That was not what I wrote.
>
> I referred to what Peter Hansen <peter@engcorp. com> wrote in
> mailman.821.113 7730663.27775.p ython-list@python.org:
>[color=green]
>>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)[/color]
>
> The way I understand this, resuming a generator causes less overhead than the
> inital overhead of a function call.[/color]

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

[skip@pobox.com]

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


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

[skip@pobox.com]

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

[color=blue][color=green]
>> If they need to resume their calculations from where they left off
>> after the last yield.[/color][/color]

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?
[color=blue][color=green][color=darkred]
>>> def square(x):[/color][/color][/color]
... while True:
... yield x*x
...[color=blue][color=green][color=darkred]
>>> g = square(2)
>>> g[/color][/color][/color]
<generator object at 0x3b9d28>[color=blue][color=green][color=darkred]
>>> g.next()[/color][/color][/color]
4[color=blue][color=green][color=darkred]
>>> g.next()[/color][/color][/color]
4[color=blue][color=green][color=darkred]
>>> g.next(3)[/color][/color][/color]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: expected 0 arguments, got 1

Skip

[Bengt Richter]

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

On Wed, 25 Jan 2006 15:50:27 -0600, skip@pobox.com wrote:
[color=blue]
>[color=green][color=darkred]
> >> If they need to resume their calculations from where they left off
> >> after the last yield.[/color][/color]
>
> 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?
>[color=green][color=darkred]
> >>> def square(x):[/color][/color]
> ... while True:
> ... yield x*x
> ...[color=green][color=darkred]
> >>> g = square(2)
> >>> g[/color][/color]
> <generator object at 0x3b9d28>[color=green][color=darkred]
> >>> g.next()[/color][/color]
> 4[color=green][color=darkred]
> >>> g.next()[/color][/color]
> 4[color=green][color=darkred]
> >>> g.next(3)[/color][/color]
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> TypeError: expected 0 arguments, got 1
>[color=green][color=darkred]
>>> def square(xbox):[/color][/color][/color]
... while True: yield xbox[0]*xbox[0]
...[color=blue][color=green][color=darkred]
>>> xbox = [3]
>>> g = square(xbox)
>>> g.next()[/color][/color][/color]
9[color=blue][color=green][color=darkred]
>>> xbox[0]=4
>>> g.next()[/color][/color][/color]
16[color=blue][color=green][color=darkred]
>>> [g.next() for xbox[0] in xrange(10)][/color][/color][/color]
[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

[Petr Jakes]

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

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_stat e", "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,e vent_guard,
action,newstate ):
"""add a new "state/transition" information to the state
machine dictionary"""
if self.states.has _key(start_stat e)== 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=Non e):
'''according to the actual "start_stat e", "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","l ift",None,None, "ON")
fsm.add("ON","p ush",None,motor _off,"OFF")
fsm.add("OFF"," push",None,None ,"OFF")
fsm.add("OFF"," lift",None,moto r_on,"ON")

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

for event in (events):

fsm.execute(eve nt)
print "switch is ", fsm.state