Friday, April 27, 2007

Python的Generator

Python的generator,說起來就是用起來像是iterator的function。由於撰寫一段function,並讓他攜帶某些資訊,要比重新打造一個支援特定iteration模式的container要簡短許多,generator可以在許多方面降低程式的複雜度,甚至提昇效率。 首先我們以尋訪檔案資料夾為例。假設我們現在要遞迴的掃瞄一個資料夾,並且對每一張圖片製作縮圖,我們可以這樣寫:
def findAndGenThumb(root):
  for item in os.listdir(root):
     if isPicture(item):
       genThumb(item)
     if os.path.isdir(item):
       findAndGenThumb(item)
相當直接明瞭。但是,如果之後要對每一張圖片抽取其EXIF資訊呢?為了程式的結構簡單,我們必須要分離「尋訪資料夾的每一個圖片元素」與「對每一個圖片元素施加某種操作」兩個意圖。
def findPic(root):
    files = []
    for item in os.listdir(root):
        if isPicture(item):
            files.append(item)
        if os.path.isdir(item):
            files.append(findPic(item))
    return files
這樣一來,我們先呼叫findPic('c:\\')取得一個含有圖片名稱的list,接下來便可以對該list進行操作:
for p in findPic('c:\\'):
    genThumb(p)
    #...Anything operates on a picture file
這個作法的問題在於,檔案數量可能非常龐大,而存在一個list裡面會消耗相當程度的空間。難道我們不能夠想辦法「修改回圈的內部」嗎?generator便提供了這樣的機會。 Generator的便是在function內使用關鍵字yield。我們可以把yield想成return,只是該function碰到yield並且回傳值之後,並不會結束,而是暫時凍結自己的執行狀態。同時,對於外面來說,這個function第一次呼叫的結果,會是一個iterator。之後每一次呼叫iteroator.next(),就會得到該function所yield的值。值得注意的是,generator一次只送回一個iteration(一次yield)執行的結果,並沒有暫存的container。而在每次呼叫next()之間,該function的狀態會被儲存起來。 跟一般的container比較一下:
container = [1,2,3,4,5] 
def tempStorage(c):
    tempList = []
    for item in c:
        print item
        tempList.append(item)
    return tempList

for item in tempStorage(container):
    print "receive" + str(item)
會得到 >>>
1
2
3
4
5
receive1
receive2
receive3
receive4
receive5
而換成一個generator:
def genStorage(c):
    for item in c:
        print item
        yield item

#use this generator as a container
for item in genStorage([1,2,3,4,5]):
    print "receive" + str(item)
會得到
1
receive1
2
receive2
3
receive3
4
receive4
5
receive5
也就是說,Generator每次執行到yield就會停住,下一次next()被呼叫的時候才會再「醒過來」。最後,我們用generator來尋訪檔案樹,把他轉換成一個container,但是不需要把所有檔案都記起來。如果檔案數量很多,generator的版本會省很多記憶體,因為被交換的只有yield後面的物件,而沒有一個很大的container:
#A generator that walk through file tree
def getPics(root):
    for item in os.listdir(root):
        if isPicture(item):
            yield item
        if isDir(item):
            getPics(item)

#Use that generator as a iteratable container directly
for p in getPics('c:\\')
   doSomething(p)

#Or call it's next explicitly
g = getPics('c:\\')
while True:
    try:
        pic = g.next()
        doSomething(p)
    except StopIteration:
        #g.next() raises "StopIteration" if the actual generating function exits.
        break
這樣一來,是不是很簡單易懂呢?而且,就算檔案很多,也不用花費多餘的記憶體。而使用起來就像是一般的container一樣直覺、單純、一致。不需要自己寫一個支援iteration的class,也不需要用stack或是queue來簿記目前尋訪到哪一層。聽起來是不是很熟悉呢?是的,我們可以把檔案樹想成一個資料結構,而這個資料結構需要某種特定的尋訪方式。透過generator,我們可以制定各種想要的尋訪方式,並且把結果轉換成為另一個container。 Generator方便之處在於會幫你記住function裡面local scope的執行環境,不用再自己使用一些global的狀態變數,也不會像C/C++的function static variable一樣,要時常注意重複呼叫的問題,同時也免除自己製作一個class進行繁瑣的狀態維護動作。 除了拿來做traversal,generator也可以拿來產生合成的collection,或是產生無限大的collection,或是用於分攤昂貴的loop成本。由於Application layer勢必要處理、過濾各式各樣的collection,generator的好處在這些地方就很明顯了。

3 comments:

Mea said...

Well said.

Falldog said...

寫得很好,簡單易懂,感謝~

Alex said...

這才了解 yield 的妙用, 感激!