简单理解Python中基于生成器的状态机

简单生成器有许多优点。生成器除了能够用更自然的方法表达一类问题的流程之外,还极大地改善了许多效率不足之处。在 Python 中,函数调用代价不菲;除其它因素外,还要花一段时间解决函数参数列表(除了其它的事情外,还要分析位置参数和缺省参数)。初始化框架对象还要采取一些建立步骤(据 Tim Peters 在 comp.lang.python 上所说,有 100 多行 C 语言程序;我自己还没检查 Python 源代码呢)。与此相反,恢复一个生成器就相当省力;参数已经解析完了,而且框架对象正“无所事事地”等待恢复(几乎不需要额外的初始化)。当然,如果速度是最重要的,您不应该使用字节码已编译过的动态语言;但即使在速度不是主要考虑因素的情况下,快点总比慢点好。
回忆状态机

在“可爱的 Python”前面的另一篇文章中,我介绍了StateMachine 类 ,给定的机器需要多少状态处理程序,它就允许用户添加多少状态处理程序。在模型中,将一个或多个状态定义为终态(end state),仅将一个状态定义为初始状态(start state)(调用类方法对此进行配置)。每个处理程序都有某种必需的结构;处理程序将执行一系列操作,然后过一会儿,它带着一个标记返回到 StateMachine.run() 方法中的循环内,该标记指出了想得到的下一个状态。同样,用 cargo 变量允许一个状态把一些(未处理的)信息传递给下一个状态。

我介绍的 StateMachine 类的典型用途是以一个有状态的方式使用输入。例如,我所用的一个文本处理工具(Txt2Html)从一个文件中读取数行内容;依据每行所属的类别,需要以特殊的方式对其进行处理。然而,您经常需要看看前面几行提供的上下文来确定当前行属于哪个类别(以及应该怎样处理它)。构建在 StateMachine 类上的这个过程的实现可以定义一个 A 处理程序,该处理程序读取几行,然后以类似 A 的方式处理这些行。不久,满足了一个条件,这样下一批的几行内容就应该由 B 处理程序来处理了。 A 把控制传递回 .run() 循环,同时指示切换到 B 状态 ― 以及任何 A 不能正确处理的、 B 应该在阅读额外的几行之前处理的额外的行。最后,某个处理程序将它的控制传递给某个被指定为终态的状态,处理停止(halt)。

对于前面一部分中的具体代码示例,我使用了一个简化过的应用程序。我处理由迭代函数产生的数字流,而不是处理多行内容。每个状态处理程序仅打印那些在期望的数字范围内的数字(以及关于有效状态的一些消息)。当数字流中的一个数字传到一个不同的范围内,另一个不同的处理程序就会接管“处理”。对于这一部分,我们将看看另一种用生成器实现相同数字流处理的方式(有一些额外的技巧和功能)。但是,一个更复杂的生成器示例有可能对更象上一段中提到的输入流进行处理。我们再来看看前一个状态机删减过代码的版本:
清单 1. statemachine_test.py

from statemachine import StateMachine
def ones_counter(val):
  print "ONES State:  ",
  while 1:
    if val <= 0 or val >= 30:
      newState = "Out_of_Range" ; break
    elif 20 <= val < 30:
      newState = "TWENTIES";   break
    elif 10 <= val < 20:
      newState = "TENS";     break
    else:
      print " @ %2.1f+" % val,
    val = math_func(val)
  print " >>"
  return (newState, val)
# ... other handlers ...
def math_func(n):
  from math import sin
  return abs(sin(n))*31
if __name__== "__main__":
  m = StateMachine()
  m.add_state("ONES", ones_counter)
  m.add_state("TENS", tens_counter)
  m.add_state("TWENTIES", twenties_counter)
  m.add_state("OUT_OF_RANGE", None, end_state=1)
  m.set_start("ONES")
  m.run(1)

读者如果接下来对导入的 StateMachine 类以及它的方法如何工作感兴趣,应该看看前面的文章。

使用生成器

基于生成器的状态机的完整版本比我更愿意在本专栏中介绍的代码样本略长。不过,下面的代码样本是完整的应用程序,而且不需要导入单独的 statemachine 模块以提供支持。总的来说,这个版本比基于类的那个版本要短一些(我们将看到它有一些特别之处,而且还非常强大)。
清单 2. stategen_test.py

from __future__ import generators
import sys
def math_gen(n):  # Iterative function becomes a generator
  from math import sin
  while 1:
    yield n
    n = abs(sin(n))*31
# Jump targets not state-sensitive, only to simplify example
def jump_to(val):
  if  0 <= val < 10: return 'ONES'
  elif 10 <= val < 20: return 'TENS'
  elif 20 <= val < 30: return 'TWENTIES'
  else:        return 'OUT_OF_RANGE'
def get_ones(iter):
  global cargo
  while 1:
    print "\nONES State:   ",
    while jump_to(cargo)=='ONES':
      print "@ %2.1f " % cargo,
      cargo = iter.next()
    yield (jump_to(cargo), cargo)
def get_tens(iter):
  global cargo
  while 1:
    print "\nTENS State:   ",
    while jump_to(cargo)=='TENS':
      print "#%2.1f " % cargo,
      cargo = iter.next()
    yield (jump_to(cargo), cargo)
def get_twenties(iter):
  global cargo
  while 1:
    print "\nTWENTIES State: ",
    while jump_to(cargo)=='TWENTIES':
      print "*%2.1f " % cargo,
      cargo = iter.next()
    yield (jump_to(cargo), cargo)
def exit(iter):
  jump = raw_input('\n\n[co-routine for jump?] ').upper()
  print "...Jumping into middle of", jump
  yield (jump, iter.next())
  print "\nExiting from exit()..."
  sys.exit()
def scheduler(gendct, start):
  global cargo
  coroutine = start
  while 1:
    (coroutine, cargo) = gendct[coroutine].next()
if __name__ == "__main__":
  num_stream = math_gen(1)
  cargo = num_stream.next()
  gendct = {'ONES'    : get_ones(num_stream),
       'TENS'    : get_tens(num_stream),
       'TWENTIES'  : get_twenties(num_stream),
       'OUT_OF_RANGE': exit(num_stream)     }
  scheduler(gendct, jump_to(cargo))

关于基于生成器的状态机,要研究的地方还很多。第一点在很大程度上是表面性的。我们安排 stategen_test.py 只能使用函数,不能使用类(至少按我的意思,生成器更有一种函数编程的感觉而非面向对象编程(OOP)的感觉)。但是,如果希望的话,您可以很容易地把相同的通用模型包装到一个或多个类中。

我们的样本中的主函数是 scheduler() ,它完全是一般性的(但是比前面的模式中的 StateMachine 要短许多)。函数 scheduler() 要求生成器-迭代器对象字典(“实例化的”生成器)作为参数。给每个生成器取的字符串名称可以是您所希望的任意名称 ― 生成器工厂函数的字面名称是一个显而易见的选择,但是我在示例中使用大写的关键字名称。 scheduler() 函数还接受“初始状态”作为参数,但如果您希望的话,也许可以自动选择一个缺省值。

每个“已调度的”生成器遵循一些简单的惯例。每个生成器运行一段时间,然后产生一对值,包含期望的跳转和某个“cargo” ― 就像用前面的模型一样。没有生成器被明确地标记为“终态”。相反,我们允许各个生成器选择产生错误来结束 scheduler() 。特殊情况下,如果生成器“离开”终态或者到达一个 return 状态,生成器将产生 StopIteration 异常。如果需要的话,您可以捕获这个异常(或者是一个不同的异常)。在我们的例子中,我们使用 sys.exit() 来终止应用程序,在 exit() 生成器中会遇到这个 sys.exit()。

要注意关于代码的两个小问题。上面的样本使用一个更简洁的循环生成器-迭代器,而不是使用迭代函数来生成我们的数字序列。生成器仅随着每个后续的调用发出一个(无穷的/不确定的)数字流,而不是连续返回“最后的值”。这是一个虽然小但却好用的生成器样本。而且,上面把“状态转换”隔离在了一个单独的函数中。在实际程序中,状态转变跳转更是上下文相关的,而且可能要在实际的生成器体内决定。该途径简化了样本。尽管可能用处不大,但是您姑且听听,我们完全可以通过一个函数工厂产生生成器函数从而进一步简化;但是一般情况每个生成器都不会与其它生成器相似到足以使这种方法切实可行。

协同程序和半协同程序

细心的读者可能注意到了,实际上我们不知不觉地进入了一种比最初所表明的要有用得多的流控制结构。在样本代码中,不仅仅只是有了状态机。事实上,上面的模式是一个很有效的协同程序通用的系统。大多数读者在此或许会需要一些背景知识。

协同程序是程序功能的集合,它允许任意地分支到其它的控制上下文中 以及从分支点任意恢复流。我们在大多数编程语言中所熟悉的子例程是通用协同程序的一种极为有限的分支情况。子例程仅从顶端的一个固定点进入并且只退出一次(它不能被恢复)。子例程还总是把流传送回它的调用者处。本质上,每个协同程序代表一个可调用的延续 ― 尽管添加一个新的单词并不一定能向不知道这个单词的人阐明它的意思。Randall HydeAn 的 The Art of Assembly中的“Cocall Sequence Between Two Processes”插图对于解释协同程序大有帮助。 参考资料上有到此图的链接。参考资料中还有到 Hyde 的综合讨论的链接,该讨论相当不错。

不管算不算负面影响,您还是会注意到,在许多语言中臭名昭著的 goto 语句也允许任意分支,但是在一个不太结构化的上下文中,它能导致“通心粉 代码”。

Python 2.2+ 的生成器向协同程序迈进了一大步。这一大步是指,生成器 ― 和函数/子例程不同 ― 是可恢复的,并且可以在多个调用之后得到值。然而,Python 生成器只不过是 Donald Knuth 所描述的“半协同程序”。生成器是可恢复的,并且可以在别处分支控制 ― 但是它只能分支控制回到直接调用它的调用者处。确切的说,生成器上下文(和任何上下文一样)可以自己调用其它生成器或函数 ― 甚至可以它自己进行递归调用 ― 但是每个最终的返回必须经由返回上下文的线性层次结构传递。Python 生成器不考虑“生产者”和“消费者”的常见协同程序用法(可以随意从对方的中间位置继续)。

幸运的是,用 Python 生成器模仿配备齐全的的协同程序相当容易。简单的窍门就是和上面样本代码中生成器十分类似的 scheduler() 函数。事实上,我们所提出的状态机本身就是一个常见得多的协同程序框架模式。适应这种模式能克服 Python 生成器中仍存在的小缺陷(让粗心大意的程序员也能发挥出通心粉代码的全部力量)。

操作中的 Stategen

要想准确了解 stategen_test.py 中发生了什么,最简单的办法就是运行它:
清单 3. 运行 STATEGEN(手工跳转控制)

% python stategen_test.py
ONES State:    @ 1.0
TWENTIES State:  *26.1  *25.3
ONES State:    @ 4.2
TWENTIES State:  *26.4  *29.5  *28.8
TENS State:    #15.2  #16.3  #16.0
ONES State:    @ 9.5  @ 3.8
TENS State:    #18.2  #17.9
TWENTIES State:  *24.4
TENS State:    #19.6
TWENTIES State:  *21.4
TENS State:    #16.1  #12.3
ONES State:    @ 9.2  @ 6.5  @ 5.7
TENS State:    #16.7
TWENTIES State:  *26.4  *30.0
[co-routine for jump?] twenties
 ...Jumping into middle of TWENTIES
TWENTIES State:
TENS State:    #19.9
TWENTIES State:  *26.4  *29.4  *27.5  *22.7
TENS State:    #19.9
TWENTIES State:  *26.2  *26.8
Exiting from exit()...

这个输出和前面的 statemachine_test.py 中的输出基本上是完全相同的。结果中的每一行分别表示在特定的处理程序或生成器中使用的流;在行的开头声明了流上下文。但是,每当另一个协同程序分支转到生成器内时,生成器版本 恢复执行(在一个循环内),而不仅仅是再次 调用处理程序函数。假设所有的 get_*() 协同程序体都包含在无限循环中,这点差异就不那么明显了。

要了解 stategen_test.py 中的本质差异,看看 exit() 生成器中发生了什么。第一次调用生成器-迭代器时,从用户处收集一个跳转目标(这是现实中的应用中有可能利用的事件驱动分支决策的一种简单情况)。然而,当再次调用 exit() 时,它位于生成器的一个稍后的流上下文中 ― 显示退出消息,并调用 sys.exit() 。交互作用样本中的用户完全可以直接跳转到“out_of_range”,不用转到另一个“处理程序”就退出(但是它 将执行一个到这个相同生成器内的递归跳转)。

结束语

我在介绍中说过,我期望状态机版本的协同程序运行速度大大超过前面介绍的带回调处理程序的类(class-with-callback-handler)"版本的速度。恢复生成器-迭代器效率要高得多。特定的示例如此简单,几乎不足以作为评判标准,但是我欢迎读者对具体结果进行反馈。

但不管我介绍的“协同程序模式”在速度方面可能取得什么样的进展,在它实现的惊人的通用流控制面前都会黯然失色。comp.lang.python 新闻组上的许多读者都曾询问过 Python 的新生成器有多通用。我想,我所描述的框架的可用性作了回答:“和您想要的一样!”对于大多数和 Python 有关的事情,对某些事情 编程通常比 理解它们要简单得多。试试我的模式;我想您会发现它很有用。

(0)

相关推荐

  • javascript与有限状态机详解

    简单说,它有三个特征: 复制代码 代码如下: * 状态总数(state)是有限的.* 任一时刻,只处在一种状态之中.* 某种条件下,会从一种状态转变(transition)到另一种状态. 它对JavaScript的意义在于,很多对象可以写成有限状态机. 举例来说,网页上有一个菜单元素.鼠标悬停的时候,菜单显示:鼠标移开的时候,菜单隐藏.如果使用有限状态机描述,就是这个菜单只有两种状态(显示和隐藏),鼠标会引发状态转变. 代码可以写成下面这样: 复制代码 代码如下: var menu = { //

  • 一个状态机的实现

    话不多说,先看代码: interface IState { string Name { get; set; } //后件处理 IList<IState> Nexts { get; set; } Func<IState /*this*/, IState /*next*/> Selector { get; set; } } class State : IState { public string Name { get; set; } = "State"; IList

  • 状态机的概念和在Python下使用状态机的教程

    什么是状态机? 关于状态机的一个极度确切的描述是它是一个有向图形,由一组节点和一组相应的转移函数组成.状态机通过响应一系列事件而"运行".每个事件都在属于"当前"节点的转移函数的控制范围内,其中函数的范围是节点的一个子集.函数返回"下一个"(也许是同一个)节点.这些节点中至少有一个必须是终态.当到达终态,状态机停止. 但一个抽象的数学描述(就像我刚给出的)并不能真正说明在什么情况下使用状态机可以解决实际编程问题.另一种策略就是将状态机定义成一种强

  • 简单理解Python中基于生成器的状态机

    简单生成器有许多优点.生成器除了能够用更自然的方法表达一类问题的流程之外,还极大地改善了许多效率不足之处.在 Python 中,函数调用代价不菲:除其它因素外,还要花一段时间解决函数参数列表(除了其它的事情外,还要分析位置参数和缺省参数).初始化框架对象还要采取一些建立步骤(据 Tim Peters 在 comp.lang.python 上所说,有 100 多行 C 语言程序:我自己还没检查 Python 源代码呢).与此相反,恢复一个生成器就相当省力:参数已经解析完了,而且框架对象正"无所事事

  • 简单理解Python中的装饰器

    Python的装饰器可以实现在代码运行期间修改函数的上下文, 即可以定义函数在执行之前进行何种操作和函数执行后进行何种操作, 而函数本身并没有任何的改变. 首先, 我们先定义一个函数, 这个函数可以输出我的个人昵称: def my_name(): print "Yi_Zhi_Yu" my_name() # Yi_Zhi_Yu 那假如我需要在个人昵称输出前, 在输出我的个人uid呢, 当然, 要求是不改动现有的my_name函数, 这个时候就可以使用装饰器了 首先, 装饰器也是个函数,

  • 简单介绍Python中利用生成器实现的并发编程

    我们都知道并发(不是并行)编程目前有四种方式,多进程,多线程,异步,和协程. 多进程编程在python中有类似C的os.fork,当然还有更高层封装的multiprocessing标准库,在之前写过的python高可用程序设计方法中提供了类似nginx中master process和worker process间信号处理的方式,保证了业务进程的退出可以被主进程感知. 多线程编程python中有Thread和threading,在linux下所谓的线程,实际上是LWP轻量级进程,其在内核中具有和进

  • Python中的生成器

    目录 1.列表生成式 1.列表生成式 代码演示: # 列表生成式 list_1 = [x**2 for x in range(10)] # x**2处也可以放函数 print(list_1) #[0, 1, 4, 9, 16, 25, 36, 49, 64, 81] # 代码等价于 list_2 = [] for x in range(10): list_2.append(x**2) print(list_2) 2.生成器 通过列表生成式,我们可以直接创建一个列表.但是,受到内存限制,列表容量肯

  • 深入理解python中函数传递参数是值传递还是引用传递

    目前网络上大部分博客的结论都是这样的: Python不允许程序员选择采用传值还是传 引用.Python参数传递采用的肯定是"传对象引用"的方式.实际上,这种方式相当于传值和传引用的一种综合.如果函数收到的是一个可变对象(比如字典 或者列表)的引用,就能修改对象的原始值--相当于通过"传引用"来传递对象.如果函数收到的是一个不可变对象(比如数字.字符或者元组)的引用,就不能 直接修改原始对象--相当于通过"传值"来传递对象. 你可以在很多讨论该问题

  • 简单谈谈python中的语句和语法

    python程序结构 python"一切皆对象",这是接触python听到最多的总结了.在python中最基层的单位应该就是对象了,对象需要靠表达式建立处理,而表达式往往存在于语句中,多条语句组成代码块,多个代码块再组成一整个程序.python的核心其实是由语句和表达式组成.所以在这里简单探讨一下python中的语句和表达式. 因为以后可能会接触到两个版本的python,所以这里讲一讲python2与python3的语句差异: 1.python2中没有nolocal语句. 2.prin

  • 简单谈谈python中的lambda表达式

    最近在coding时发现使用lambda还是有诸多优点的,很多时候代码更整洁,更pythonic,所以在此简单总结一下 1.lambda是什么 举个简单的例子: func = lambda x: x*x def func(x): return x*x 两个func的定义是完全相同的,那两种函数定义方法配合map使用,将list中所有元素求平方,代码会是什么样的, def func(x): return x*x map(func, [i for i in range(10)]) map(lambd

  • 对python中基于tcp协议的通信(数据传输)实例讲解

    阅读目录 tcp协议:流式协议(以数据流的形式通信传输).安全协议(收发信息都需收到确认信息才能完成收发,是一种双向通道的通信) tcp协议在OSI七层协议中属于传输层,它上承用户层的数据收发,下启网络层.数据链路层.物理层.可以说很多安全数据的传输通信都是基于tcp协议进行的. 为了让tcp通信更加方便需要引入一个socket模块(将网络层.数据链路层.物理层封装的模块),我们只要调用模块中的相关接口就能实现传输层下面的繁琐操作. 简单的tcp协议通信模板:(需要一个服务端和一个客户端) 服务

  • 详解python中的生成器、迭代器、闭包、装饰器

    迭代是访问集合元素的一种方式.迭代器是一个可以记住遍历的位置的对象.迭代器对象从集合的第一个元素开始访问,直到所有的元素被访问完结束.迭代器只能往前不会后退. 1|1可迭代对象 以直接作用于 for 循环的数据类型有以下几种: 一类是集合数据类型,如 list . tuple . dict . set . str 等: 一类是 generator ,包括生成器和带 yield 的generator function. 这些可以直接作用于 for 循环的对象统称为可迭代对象: Iterable .

  • 彻彻底底地理解Python中的编码问题

    Python处理文本的功能非常强大,但是如果是初学者,没有搞清楚python中的编码机制,也经常会遇到乱码或者decode error.本文的目的是简明扼要地说明python的编码机制,并给出一些建议. 问题1:问题在哪里? 问题是我们的靶子,心中没有问题去学习就会抓不住重点. 本文使用的编程环境是centos6.7,python2.7.我们在shell中键入python以打开python命令行,并键入如下两句话: s = "中国zg" e = s.encode("utf-8

随机推荐