作者ykjiang (York)
看板Python
標題Re: [問題] 排列組合
時間Sun Oct 26 12:33:04 2008
其實遞迴版並不會比較慢,只要稍做調整:
def gen(n):
if n == 0:
return ['']
else:
return [x+y for x in gen(n-1) for y in 'ATCG']
改變迴圈的順序,這是很基本的最佳化作法...
※ 引述《mantour (朱子)》之銘言:
: 測n=10時
: def gen1(n):
: list=['']
: for i in range(n):
: tmp=[j+k for j in list for k in 'ATCG']
: list=tmp
: return list
: 3.949s
: 下面的版本在我的電腦上測n=10為17.545s
: : def gen(n):
: : if n == 0:
: : return ['']
: : else:
: : return [x + y for x in ['A', 'T', 'C', 'G'] for y in gen(n - 1)]
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.70.98.179
推 adair326:請問一下為什麼換順序就會比較快? 10/26 14:20
→ ykjiang:因最裡面的迴圈跑最頻繁,調換後,最裡面那圈做的事變少 10/26 14:55
→ ykjiang:在 n 夠大時,調換後還可減少記憶體跟硬碟間 swap 的頻率 10/26 14:58
→ ykjiang:關於第二點,可以參考 OS 相關書籍 10/26 14:59
→ ykjiang:關於虛擬記憶體及 page fault 相關的章節 10/26 15:00