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_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)

原文轉自：http://www.kjueaiud.com