翟本喬談雲端運算

雲端運算喊得很熱，不過我是看了翟本喬在COSCUP 2010的演講才清楚甚麼叫雲端運算
他提到與其人云亦云，不如看看NIST(美國國家標準暨技術研究院)的定義吧
http://csrc.nist.gov/groups/SNS/cloud-computing/
事實上文件中也提到雲端計算的定義隨時再改進，目前的版本是第15版，2009年所制定。

簡單的說，雲端計算是一種按使用量計費的服務，而可使用的資源包含網路頻寬、磁碟空間、記憶體、應用軟體等等。一個服務要稱得上雲端必須具備以下條件:
五種特徵

1. On-demand self-service - 使用者要使用服務時可自行索取，無須人力協調(像自助餐)
2. Broad network access - 可使用各式網路存取(如PC、手機、iPad等等)
3. Resource pooling - 服務提供者的資源可分散世界各地，而使用者無須知道服務所發生的地點
4. Rapid elasticity - 使用者能快速地取得服務和停止服務
5. Measured Service - 可量化資源的使用量 (當然，這是計算價錢的基礎)

限制Windows程式的記憶體使用量

和朋友討論到，在windows下如何限制一個程式的記憶體使用量，以避免佔用過多的系統資源。

其中一個解法為使用 SetProcessWorkingSetSize()，最簡單的情況下只需要三行程式:

int pid = GetCurrentProcessId();
HANDLE hProcess = OpenProcess(PROCESS_SET_QUOTA, FALSE, pid);
SetProcessWorkingSetSize(hProcess, minMemBytes, maxMemBytes);

不過實際執行程式會發現，只要記憶體還算充足，程式還是能獲得超過上限的記憶體。在我的4GB電腦上，大概可以使用到1.8G的記憶體，才會無法配置新的記憶體。

加快遞迴函數的計算

演算法中有一個簡單但是實用的技巧叫 memoization，可用於加快遞迴函數的計算，基本的想法就是把計算過的值儲存起來，並在呼叫前檢查是否已經計算過。

比如說我們要計算Fibonacci數列的值，公式為

F(0) = 0

F(1) = 1

F(n) = F(n-1), F(n-2)

用C++來實作並配合memoization的話程式如下

int fibonacci(int n)
{
    if (n<2)
        return n;
    static map<int,int> mymap;
    map<int,int>::iterator it;
    it = mymap.find(n);
    if (it==mymap.end())
    {
        int f = fibonacci(n-1) + fibonacci(n-2);
        mymap[n] = f;
        return f;
    }
    else
        return it->second;
} 

主要的概念在於使用 map 來儲存計算過的 f(n)。

上述的方法需要自己在程式中檢查傳入的參數是否有計算過，
然而人是懶惰的，在某些程式語言中可以將一個函數直接"升級"，
獲得memoization的能力。
比如說下面是ypcat提供的python的範例

def memoize(f, cache={}):
  def g(*args):
    key = tuple(args)
    if key not in cache:
      cache[key] = f(*args)
    return cache[key]
  return g

def fib(n):
  return n if n<2 else fib(n-1)+fib(n-2)

fib = memoize(fib)
print fib(300) 

比C++更方便的地方在於使用了一個函數 memoize 來包裝遞迴函數，執行的時候還可以把 fib() 直接替換為包裝過的函數。

Python, C#, Java, Lisp 等支援 first-class function 的語言都能達成以上功能，
那C++有沒有辦法自動memoization呢? 我目前還不確定。