Pythonic 的 dynamic programming

by thinker

關鍵字:

linkname:[Dynamic Programming] http://en.wikipedia.org/wiki/Dynamic_programming 是演算法中，很重要的效能改進技巧。前面的 linkname:[試題的 $Python$ 解法] http://heaven.branda.to/~thinker/GinGin_CGI.py/show_id_doc/227 一文，程式執行許多重複的計算，致使效能低落，於是讓我想起 Dynamic Programming 這個技巧。

== Pythonic ==
這裡會用到兩個很重要 $Python$ 功能和特色， decorator 和 first-class function 。我們定義了一個稱為 dynamic 的 decorator ，為 function 增進效能。

== Dynamic Programming ==
{{{#!python
def combine(data, n):
    sels = list(range(n))
    while True:
        yield tuple([data[i] for i in sels])
        try:
            i = [i for i in range(n) if sels[i] + n - i < len(data)][-1]
        except IndexError:
            break
        c = sels[i]
        for i in range(i, n):
            c = c + 1
            sels[i] = c
            pass
        pass
    pass

def dynamic(func):
    cache = {}
    def wrapper(*args):
        try:
            return cache[args]
        except KeyError:
            cache[args] = func(*args)
            pass
        return cache[args]
    return wrapper

sdict = {}
pdict = {}
for x, y in combine(range(2, 50), 2):
    sdict.setdefault(x + y, []).append((x, y))
    pdict.setdefault(x * y, []).append((x, y))
    pass

def E(x, y):
    $C$ = x * y
    return len(pdict[$C$]) >= 2

@dynamic
def F(x, y):
    D = x + y
    subset = [(a, b) for a, b in sdict[D] if E(a, b)]
    return len(subset) >= 2

@dynamic
def G(x, y):
    $C$ = x * y
    subset = [(a, b) for a, b in pdict[$C$] if F(a, b)]
    return (len(subset) == 1)

@dynamic
def H(x, y):
    D = x + y
    subset = [(a, b) for a, b in sdict[D] if G(a, b) and E(a, b)]
    return (len(subset) == 1)

def I():
    subset = [(a, b) for a, b in combine(range(2, 50), 2) if H(a, b) and G(a, b) and F(a, b) and E(a, b)]
    return subset

print I()

}}}

我在可能會大量重複呼叫的 function 前面，都加上 dynamic 這個 decorator ，造成的效能改進相當的可觀。根據測試，用 time (1) 指令計算時間，大概差 8 倍的執行效率。用 $Python$ 的 timeit 計算時間，大概差 10 倍左右的時間。

最後更新時間: 2007-03-07 23:35:32 CST | 引用

查詢:

COMMENTS: