lazy ideas in programming(程式設計中的惰性思想)

　　lazy形容詞，懶惰的，毫無疑問是一個貶義詞。但是，對于計算機領域，lazy卻是非常重要的優化思想：把任務推遲到必須的時刻，好處是避免重複計算，甚至不計算。本文的目的是抛磚引玉，總結一些程式設計中的lazy idea，以期有一些啟發。google “lazy”這個單詞，在計算機領域高頻出現三個詞：lazy loading（惰性加載）、lazy initializing（惰性初始化）、lazy evaluation（惰性求值），本文并不刻意區分，因為不管是loading、initializing還是evaluation都需要耗費計算機的運算資源，而且，loading（initializing）也是某種意義上的evaluation。

lazy ideas：

　　在GOF的設計模式中，并沒有一個叫“lazy loading”之類的設計模式，但是其思想貫穿在很多設計模式中。其中比較明顯的就是singleton和proxy模式。

singleton

　　單例模式的實作一般都有兩種方式，要麼在調用之前就建立好單例對象（eager way），要麼在第一次調用的時候生成單例對象（lazy way)，兩者對象的代碼大緻是這樣的：

　　

1 class eager_meta(type):
 2     def __init__(clz, name, bases, dic):
 3         super(eager_meta, clz).__init__(name, bases, dic)
 4         clz._instance = clz()
 5 
 6 class singleton_eager(object):
 7     __metaclass__ = eager_meta
 8 
 9     @classmethod
10     def instance(clz):
11         return clz._instance
12 
13 
14 class singleton_lazy(object):
15     __instance = None
16     @classmethod
17     def instance(clz):
18         if clz.__instance is None:
19             clz.__instance = singleton_lazy()
20         return clz.__instance      

 　　PS：在python中，這樣使用單例模式不是很pythonic，更好的辦法可見在stackoverflow上的這篇文章《creating-a-singleton-in-python》。另外在多線程環境下，要實作線程安全的單例還是很複雜的，具體讨論可參見iteye上的分析。

proxy：

　　代理模式屬于責任型模式， 使得一個對象代表另一個對象進行各種操作，常用場景包括

• remote proxy（遠端代理），如RMI， RPC

• virtual proxy（虛代理），根據需要建立開銷很大的對象，如文檔中圖檔的加載

• （保護代理）：控制對原始對象的通路， 如智能指針

　　其中 viatual proxy是使用lazy loading很好的例子

Short-circuit evaluation：

　　短路求值在絕大多數程式設計語言都有實作，比較常見的文法如下：

　　　　x and y(x && y)

　　　　x or y(x || y)

　　　　x if bool else y(bool？ x : y )

　　短路求值基本上都是數學邏輯的展現，如果第一個參數已經能推導出這個表達式的意義，那麼後面的參數是無需計算的。短路求值非常有用，不僅能避免無用的計算，對于邏輯判斷也非常有用。比如在python中，判斷一個對象的is_ok屬性為True，我們一般這麼寫

　　if(obj.is_ok)

　　如果obj被指派成了None，那麼就會報一個異常，是以可以寫成

　　if(obj is not None and obj.is_ok)

　　python中，一些函數也有短路求值的特性，比如在這篇文章中提到的any函數：

1     ret = any(self.calc_and_ret(e) for e in elements)
2     def self.calc_and_ret(self, e):
3         # do a lot of calc here which effect self
4         return True(or False)      

    本意是希望對所有的element都計算，然後傳回一個結果，但事實上由于短路求值， 可能後面很多的元素都不會再調用calc_and_ret

generator：

　　在python和javascript語言中都有generator，generator與普通的函數相比，可以多次（甚至無限次）傳回，而且傳回值是在需要的時候才生成。在python中，下面兩段代碼非常相似，但事實上差異非常大：

1 　　　　for x in [i*i for i in xrange(10000)]
2 　　　　　　# do sth with i
3 
4 　　　　for x in (i*i for i in xrange(10000)]
5 　　　　　　# do sth with i      

　　generator更廣泛的應用可以參見《python yield generator 詳解》。javascript中generator的文法和使用與python都非常類似，可以參見這篇文章。

函數式程式設計語言中的應用：

　　lazy evaluation在函數式程式設計語言中使用得非常頻繁，python也可以當做函數式程式設計語言來使用，而更為明顯的是haskell，在其首頁的features介紹裡面就有大大的“lazy”

cache：

　　cache也是一種lazy思想，如果之前有計算結果，那麼直接複用之前的結果就行了，幹嘛還要重新計算呢？而且最開始的緩存内容， 也是在需要的時候才計算的，而不是一開始就計算好。wiki上有python實作的簡單例子：

 　　

1 class Fruit:
 2     def __init__(self, item):
 3         self.item = item
 4     
 5 class Fruits:
 6     def __init__(self):
 7         self.items = {}
 8     
 9     def get_fruit(self, item):
10         if item not in self.items:
11             self.items[item] = Fruit(item)
12         
13         return self.items[item]
14 
15 if __name__ == '__main__':
16     fruits = Fruits()
17     print(fruits.get_fruit('Apple'))
18     print(fruits.get_fruit('Lime'))      

Dirty Flag：

　　在《Dirty Flag模式及其應用》一文中，列舉了Dirty Flag模式的諸多應用場景。Dirty Flag顯然也是很明顯的lazy evaluation。比如《game programming pattern》中的例子：子模型的世界坐标取決于父模型的世界坐标以及子模型在父模型坐标空間的相對坐标，如果父模型的世界坐标變化時就主動去重新計算子模型的坐标，因為兩幀之間父模型的坐标可能多次變換，往往會造成備援的計算。是以Dirty Flag隻是在父模型坐标變化的時候标記，繪制的時候再計劃所有受影響的模型的世界坐标。

CopyOnWrite：

　　CopyOnWrite即寫時複制，如果大家對一份資源隻有讀請求時，那麼資源是可以共享的，當某個通路者需要修改資源（寫操作）時，就将資源拷貝一份給該通路者使用。即資源的拷貝被延遲到了第一次"寫"的時候。CopyOnWrite最廣為人知的兩個應用場景，一個是Unix like系統fork調用産生的子程序共享父程序的位址空間，知道寫操作才會拷貝一份。另一個是java中的copyonwrite容器，用于多線程并發情況下的高效通路，cookshell上有對copyonwrite容器的詳細介紹。

web開發中的惰性加載與惰性預加載：

　　在web前端和APP開發中，當提到惰性加載或者動态加載，大家往往會想到分頁、輪播圖、瀑布流，這些都展現了惰性加載的思想。其中，瀑布流在出諸多圖檔分享網站中使用非常廣泛，比如花瓣網，當滑動到螢幕底部的時候才會去加載新的内容。為什麼要使用惰性加載，第一個是使用者體驗的問題，圖檔資源流量比較大，一次加載太多對伺服器和浏覽器壓力都很大，對帶寬要求也很高；另外，可能使用者根本就不會滑動到最下面，多加載的内容就白白浪費了。 

　　當然太”Lazy”了也是不好的，總不能讓玩家滑動到底部才一邊顯示loading icon，一邊開始加載。為了提高使用者體驗，這類網站也會做預加載（predictive loading），即多準備一兩頁的内容，或者在滑屏到一定程度時開始加載新的一頁，不過這樣的預加載也是惰性預加載（lazy predictive loading）。

總結：

　　本文列舉了惰性計算在程式設計中的一些具體例子，希望能給自己以及大家有所啟發，在以後遇到問題的時候多一種解決思路。由于本人程式設計領域以及程式設計語言的局限性，肯定還有諸多遺漏，歡迎大家在評論裡補充。

references：

lazy loading

lazy initializing

lazy evaluation

Short-circuit_evaluation

CopyOnWrite

Dirty Flag模式及其應用

python yield generator 詳解

本文版權歸作者xybaby（博文位址：http://www.cnblogs.com/xybaby/）所有，歡迎轉載和商用，請在文章頁面明顯位置給出原文連結并保留此段聲明，否則保留追究法律責任的權利，其他事項，可留言咨詢。