第十三號艦隊
0%

Memoization in programming languages

Posted on Edited on In , ,

程式計算中有個技巧，叫做Memoization，避免重複計算相同的工作。
以下分別用C/Python/Haskell來當範例

C Language

以Fibonacci Number來說，遞迴的表示式這樣。

lang: c
1
2
3
4
5
int fib(int n)
{
	if (n < 2) return n;
	return fib(n - 1) + fib(n - 2);
}

加上Memoization的程式碼會變這樣

lang: c
1
2
3
4
5
6
7
8
int _fib[100];
int fib(int n)
{
	if (n < 2) return n;
	if (_fib[n] != -1) return _fib[n];
	return (_fib[n] = fib(n - 1) + fib(n - 2));
}
memset(_fib, -1, sizeof(fib));

Python

至於Python版Recursive的程式碼也相當相似

lang: python
1
2
3
4
5
def fib(n):
    if n in [0,1]:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

不過由於Python將Function當First-Class Function，可以寫出像這樣的程式碼。

lang: python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def memoize(fn):
    stored = {}
    def memoized(*args):
        try:
            return stored[args]
        except:
            result = fn(*args)
            stored[args] = result
            return result
    return memoized

def fib(n):
    if n in [0,1]:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

fib = memoize(fib)

更甚者可以使用Python的Decorator來簡化程式碼

lang: python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def memoize(fn):
    stored = {}
    def memoized(*args):
        try:
            return stored[args]
        except:
            result = fn(*args)
            stored[args] = result
            return result
    return memoized

@memoize
def fib(n):
    if n in [0,1]:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

Haskell

Haskell反而是裡面最麻煩的，因為他是個純Pure Functional Language。同樣的先來看Recursive版本。

lang: haskell
1
2
3
4
fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

而Memorize版的方法不少，不過比起上面兩種反而難以理解。

lang: haskell
1
2
3
4
5
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib(n - 2) + memoized_fib(n - 1)

果然各種程式語言個有所長，看情況決定該用些什麼語言解決問題才是。