歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Unix知識 >> 關於Unix

Python中的算法和編程方法(使用狀態機)

什麼是 Python? 請簡要回顧本專欄中的第一篇文章,Python 是由 Guido van Rossum 開發 的免費高級解釋型語言。其語法簡單易懂,而其 面向對象 的語義功能強大(但又靈活)。Python 可以廣泛使用並具有高度的可移植性。 什麼是狀態機? 關於狀態機的一個極度
  什麼是 Python?
  請簡要回顧本專欄中的第一篇文章,Python 是由 Guido van Rossum 開發的免費高級解釋型語言。其語法簡單易懂,而其面向對象的語義功能強大(但又靈活)。Python 可以廣泛使用並具有高度的可移植性。
  
  什麼是狀態機?
  關於狀態機的一個極度確切的描述是它是一個有向圖形,由一組節點和一組相應的轉移函數組成。狀態機通過響應一系列事件而“運行”。每個事件都在屬於“當前”節點的轉移函數的控制范圍內,其中函數的范圍是節點的一個子集。函數返回“下一個”(也許是同一個)節點。這些節點中至少有一個必須是終態。當到達終態,狀態機停止。
  
  但一個抽象的數學描述(就像我剛給出的)並不能真正說明在什麼情況下使用狀態機可以解決實際編程問題。另一種策略就是將狀態機定義成一種強制性編程語言,其中節點也是源碼行。從實用角度看,這個定義盡管精確,但它和第一種描述一樣,都是紙上談兵、毫不實用。(對於說明型、函數型或基於約束的語言,例如,Haskell、Scheme 或 Prolog,不一定會發生這種情況。)
  
  讓我們嘗試使用更適合身邊實際任務的例子來進行討論。邏輯上,每個規則表達式都等價於一個狀態機,而每個規則表達式的語法分析器都實現這個狀態機。實際上,大多數程序員編寫狀態機時,並沒有真正考慮到這一點。
  
  在以下這個例子中,我們將研究狀態機的真正探索性定義。通常,我們有一些不同的方法來響應一組有限數量的事件。某些情況下,響應只取決於事件本身。但在其它情況下,適當的操作取決於以前的事件。
  
  本文中討論的狀態機是高級機器,其目的是演示一類問題的編程解決方案。如果有必要按響應事件行為的類別來討論編程問題,那麼您的解決方案很可能是顯式狀態機。
  
  文本處理狀態機
  最可能調用顯式狀態機的一個編程問題涉及到處理文本文件。處理文本文件通常包括讀取信息單元(通常叫做字符或行),然後對剛讀取的單元執行適當操作。某些情況下,這個處理是“無狀態的”(即每個這樣的單元都包含了足夠的信息,可以正確確定要執行什麼操作)。在其它情況下,即使文本文件不是完全無狀態,數據也只有有限的上下文(例如,操作取決於不比行號更多的信息)。但是,在其它常見文本處理問題中,輸入文件是極具“狀態”的。每一塊數據的含義取決於它前面的字符串(也許是它後面的字符串)。報告、大型機數據輸入、可讀文本、編程源文件和其它種類的文本文件都是有狀態的。一個簡單例子是可能出現在 Python 源文件中的一行代碼:
  
  myObject = SomeClass(this, that, other)
  
  這行表示,如果恰好有以下幾行圍繞著這一行,則有部分內容不同:
  
  """How to use SomeClass:
  myObject = SomeClass(this, that, other)
  """
  我們應知道我們處於“塊引用”狀態以確定這行代碼是一部分注釋而不是 Python 操作。
  
  何時不使用狀態機
  當開始為任何有狀態的文本文件編寫處理器的任務時,問一問自己,您希望在文件中找到什麼類型的輸入項。每種類型的輸入項都是一種狀態的候選項。這些類型共有幾種。如果數字很大或者不確定,則狀態機也許不是正確的解決方法。(在這種情況下,某些數據庫解決方案可能更適合。)
  
  還請考慮您是否需要使用狀態機。許多情況下,最好從更簡單的方法入手。也許會發現即使文本文件是有狀態的,也有一種簡單的方法可以分塊讀取它(其中每一塊是一種類型的輸入值)。實際上,在單一狀態塊中,僅當文本類型之間的轉移需要基於內容的計算時,才有必要實現狀態機。
  
  下面這個簡單的例子說明了需要使用狀態機的情況。請考慮用於將一列數字劃分成幾塊的兩個規則。在第一個規則中,列表中的零表示塊之間的間斷。第二個規則中,當一個塊中的元素總和超過 100 時,會發生塊之間的間斷。由於它使用累加器變量來確定是否達到了阈值,您不能“馬上”看到子列表的邊界。因此,第二個規則也許更適合於類似於狀態機的機制。
  
  稍微有些狀態、但由不太適合用狀態機處理的文本文件的例子是 Windows 風格的 .ini 文件。這種文件包括節頭、注釋和許多賦值。例如:
  
  ; set the colorscheme and userlevel
  [colorscheme]
  background=red
  foreground=blue
  title=green
  
  [userlevel]
  login=2
  title=1
  
  我們的例子沒有實際含義,但它表明了 .ini 格式一些有趣的特性。
  
  就某種意義而言,每一行的類型由它的第一個字符確定(可能是分號、左花括號或字母)。
  
  從另一種角度看,這種格式是“有狀態的”,因為關鍵字 "title" 大概表示如果它出現在每一節中,那麼就有獨立的內容。
  
  您可以編寫一個有 COLORSCHEME 狀態和 USERLEVEL 狀態的文本處理器程序,這個程序仍處理每個狀態的賦值。但這好象不是處理此問題的 正確方法。例如,可以使用 Python 代碼在這個文本文件中只創建自然塊,如:
  
  處理 .INI 文件的分塊 Python 代碼
  
  import string
  txt = open('hypothetical.ini').read()
  sects = string.split(txt, '[')
  for sect in sects:
   # do something with sect, like get its name
   # (the stuff up to ']') and read its assignments
  
  或者,如果願意,可以使用單個 current_section 變量來確定位置:
  
  處理 .INI 文件的計算 Python 代碼
  
  for line in open('hypothetical.ini').readlines():
   if line[0] == '[':
   current_section = line(1:-2)
   elif line[0] == ';':
   pass # ignore comments
   else:
   apply_value(current_section, line)
  
  何時使用狀態機
  現在,我們已經決定了如果文本文件“太簡單”就不使用狀態機,讓我們再研究 需要使用狀態機的情況。本專欄中 最近一篇文章討論了實用程序 Txt2Html,它將“智能 ASCII”(包括本文)轉換成 HTML。讓我們扼要重述。
  
  “智能 ASCII”是一種文本格式,它使用一些間隔約定來區分文本塊的類型,如頭、常規文本、引語和代碼樣本。雖然讀者或作者能容易地通過查看分析這些文本塊類型之間的轉移,但卻沒有簡單的方法可以讓計算機將“智能 ASCII”文件分割成組成它的文本塊。不像 .ini 文件示例,文本塊類型可以任何順序出現。在任何情況下都沒有單一定界符來分隔塊(空行 通常分隔文本塊,但代碼樣本中的空行卻不一定結束代碼樣本,並且文本塊不需要用空行來分隔)。由於需要以不同方式重新格式化每個文本塊以生成正確的 HTML 輸出,狀態機似乎就是自然的解決方案。
  
  Txt2Html 閱讀器的一般功能如下:
  
  在初始狀態中啟動。
  讀取一行輸入。
  根據輸入和當前狀態,轉移到新狀態或按適合當前狀態的方式處理該行。
  
  這個例子是關於您會遇到的最簡單的情況,但它說明了我們描述過的以下模式:
  
  Python 中一個簡單的狀態機輸入循環
  
  global state, blocks, bl_num, newblock
  #-- Initialize the globals
  state = "HEADER"
  blocks = [""]
  bl_num = 0
  newblock = 1
  for line in fhin.readlines():
   if state == "HEADER": # blank line means new block of header
   if blankln.match(line): newblock = 1
   elif textln.match(line): startText(line)
   elif codeln.match(line): startCode(line)
   else:
   if newblock: startHead(line)
   else: blocks[bl_num] = blocks[bl_num] + line
   elif state == "TEXT": # blank line means new block of text
   if blankln.match(line): newblock = 1
   elif headln.match(line): startHead(line)
   elif codeln.match(line): startCode(line)
   else:
   if newblock: startText(line)
   else: blocks[bl_num] = blocks[bl_num] + line
   elif state == "CODE": # blank line does not change state
   if blankln.match(line): blocks[bl_num] = blocks[bl_num] + line
   elif headln.match(line): startHead(line)
   elif textln.match(line): startText(line)
   else: blocks[bl_num] = blocks[bl_num] + line
   else:
   raise ValueError, "unexpected input block state: "+state
  
  可以用 Txt2Html 下載從中取出該代碼的源文件(請參閱參考資料)。請注意:變量 state 聲明為 global,在函數(如 startText())中更改它的值。轉移條件,如 textln.match(),是規則表達式模式,但它們可能也是定制函數。實際上,以後會在程序中執行格式化。狀態機只將文本文件分析成 blocks 列表中帶標簽的塊。
  
  抽象狀態機類
  在表單和函數中使用 Python 實現抽象狀態機很容易。這使程序的狀態機模型比前一個例子中的簡單條件塊顯得更突出(初看,其中的條件與其它條件沒有什麼不同)。而且,以下類及其關聯處理程序在隔離狀態中操作方面完成得很好。許多情況下,這改善了封裝和可讀性。
  
  文件:statemachine.py
  
  from string import upper
  class StateMachine:
   def __init__(self):
   self.handlers = {}
   self.startState = None
   self.endStates = []
   def add_state(self, name, handler, end_state=0):
   name = upper(name)
   self.handlers[name] = handler
   if end_state:
   self.endStates.append(name)
   def set_start(self, name):
   self.startState = upper(name)
   def run(self, cargo):
   try:
   handler = self.handlers[self.startState]
   except:
   raise "InitializationError", "must call .set_start() before .run()"
   if not self.endStates:
   raise "InitializationError", "at least one state must be an end_state"
   while 1:
   (newState, cargo) = handler(cargo)
   if upper(newState) in self.endStates:
   break
   else:
   handler = self.handlers[upper(newState)]
  
  StateMachine 類實際上正是抽象狀態機所需要的。因為使用 Python 傳遞函數對象是如此簡單,與其它語言中的相似類比較,這個類所需使用行數非常少。
  
  要真正使用 StateMachine 類,需要為每個要使用的狀態創建一些處理程序。處理程序必須符合模式。它循環處理事件,直到要轉移到另一個狀態,此時處理程序應該將一個字節組(它包括新狀態名稱以及新的狀態處理程序需要的任何 cargo)傳遞回去。
  
  在 StateMachine 類中將 cargo 用作變量的做法將封裝狀態處理程序所需的數據(該狀態處理程序不必調用它的 cargo 變量)。狀態處理程序使用 cargo 來傳遞下一個處理程序所需的內容,於是新的處理程序可以接管前一個處理程序的遺留工作。 cargo 通常包括文件句柄,它允許下一個處理程序可以在前一個處理程序停止後讀取更多數據。 cargo 還可能是數據庫連接、復雜的類實例或帶有幾個項的列表。
  
  現在,讓我們研究測試樣本。在本例中(在以下代碼示例中概述),cargo 只是不斷將反饋傳送給迭代函數的一個數字。只要 val 處於某個范圍內,則 val 的下一個值永遠只是 math_func(val)。一旦函數返回了超出范圍的值,那麼該值將傳送到另一個處理程序,或者狀態機在調用了一個什麼也不做的終態處理程序後就退出。示例說明了一件事: 事件不必是輸入事件。它也可以是計算事件(這種情況很少)。狀態處理程序相互之間的區別只是在輸出它們處理的事件時使用不同的標記。該函數比較簡單,沒必要使用狀態機。但它很好地說明了概念。代碼也許比解釋更易於理解!
  
  文件: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)
  def tens_counter(val):
   print "TENS State: ",
   while 1:
   if val <= 0 or val >= 30:
   newState = "Out_of_Range"; break
   elif 1 <= val < 10:
   newState = "ONES"; break
   elif 20 <= val < 30:
   newState = "TWENTIES"; break
   else:
   print " #%2.1f+" % val,
   val = math_func(val)
   print " >>"
   return (newState, val)
  def twenties_counter(val):
   print "TWENTIES State:",
   while 1:
   if val <= 0 or val >= 30:
   newState = "Out_of_Range"; break
   elif 1 <= val < 10:
   newState = "ONES"; break
   elif 10 <= val < 20:
   newState = "TENS"; break
   else:
   print " *%2.1f+" % val,
   val = math_func(val)
   print " >>"
   return (newState, val)
  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)

Copyright © Linux教程網 All Rights Reserved