Condition 的順序能決定效能

by thinker

關鍵字:

許多程式語言，對於 and 和 or 的運算，都有其順序。左邊的一項，能決定右邊的項式是否被執行。於是 condition 的順序，就有可能影嚮系統的效能。

我在前篇文章「 linkname:[Pythonic 的 dynamic programming] http://heaven.branda.to/~thinker/GinGin_CGI.py/show_id_doc/228 」中，因為效能的問題，對 $Python$ 程式進行效能改進。又於今日，因為 linkname:FourDollars http://fourdollars.blogspot.com/2007/03/cmclass_08.html 的留言，讓我想起昨日在做效能測試時，即使加了 Dynamic Programming 的技巧，速度還是差其它使用 set 觀念為 base 的程式一截。

仔細觀察後，發覺 set based 的程式，在一開始就過濾掉大量的 value pairs 。再回想一下我之前的程式，其實只要 condition 的順序換一下，一樣可以達到相同的效果。其實這個問題，在昨日寫 code 就有考慮過，但我實在太懶了，隨便就寫下這樣完全相反的順序，也懶的改。在 FourDollars 的留言之後，我提起了興趣，改成該有的順序後， runtime 由 0.101s 變成 0.055s ，效率改進 80% 左右。

我將 I() ，由
{{{#!python
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
}}}
改成
{{{#!python
def I():
    subset = [(a, b) for a, b in combine(range(2, 50), 2) if E(a, b) and F(a, b) and G(a, b) and H(a, b)]
    return subset
}}}
於是 E(a, b) 會最先執行，若傳回值為 True ，才會執行 F() 、 G() 、 H() 。由於 E() 、 F() 一下子就能濾掉大陪份的 pair ，於是後面的計算都能跳過，省下大量的計算時間。

類似的情況，會發生在 and 和 or 這類的邏輯運算。以 and 運算來說
{{{
A and B and $C$
}}}
A 的 False 機率要高於 B 和 $C$ 。

以 or 運算而言
{{{
A or B or $C$
}}}
A 的 True 機率要較 B 和 $C$ 更高。一旦 A 為 True ，程式能立即決定對錯，不需要再執行後面 B 和 $C$ 的判斷。

因此，下次您遇到效能上的問題時，調一下 condition 的順序，把鑑別度高的 condition 往前調，說不定能有不錯的效果。

最後更新時間: 2007-03-08 21:03:49 CST | 引用

查詢:

COMMENTS: