Python: 実行時間の比較
Introduction to Algorithms の 1章の章末問題を Python で計算してみる。
・問題
各関数 f(n) と時間 t に対して、アルゴリズムが問題を解くのに f(n) マイクロ秒かかるとき、
t 時間で解くことができる最大の問題のサイズ n を求めよ。
関数 f(n)： lg n √n n n lg n n2 n3 2n n!
時間 t ： 1秒 1分 1時間 1日 1月 1年 1世紀
・コード
二分検索で解くコード。ただし、lg n に関しては n が大きくなりすぎるので直接 2t を求める。
import math
def binary_search(predicate, lower_bound, upper_bound, not_found=0):
"""
Returns the least x for which predicate P(x) is true.
Predicate P must be assumed:
for all x in ordered set S, P(x) implies P(y) for all y > x
@param predicate: unary function which returns true or false
@param lower_bound: lower bound on the search
@param upper_bound: upper bound on the search
@param not_found: return value when all the predicates are false
"""
ret = not_found
while lower_bound < upper_bound:
mid = lower_bound + (upper_bound - lower_bound) / 2
if predicate(mid):
ret = upper_bound = mid
else:
lower_bound = mid + 1
return ret
def main():
# periods
periods = [None] * 7
periods[0] = 1e6 # 1 second = 1,000,000 microsecond
periods[1] = periods[0] * 60 # 1 minute = 60 seconds
periods[2] = periods[1] * 60 # 1 hour = 60 minutes
periods[3] = periods[2] * 24 # 1 day = 24 hours
periods[5] = periods[3] * 365.2425 # 1 year = 365.2425 days
periods[4] = periods[5] / 12.0 # 1 month = 1/12 year
periods[6] = periods[5] * 100 # 1 century = 100 years
# algorithms
def find(func, t, max_n):
return binary_search(lambda n: func(n) > t, 1, max_n) - 1
algos = [
['lg n' , None],
['sqrt n', lambda t: find((lambda n: math.sqrt(n)) , t, 10 ** 32) ],
['n' , lambda t: find((lambda n: n) , t, 10 ** 16) ],
['n lg n', lambda t: find((lambda n: n * math.log(n, 2)), t, 10 ** 16) ],
['n ^ 2' , lambda t: find((lambda n: pow(n, 2)) , t, 10 ** 16) ],
['n ^ 3' , lambda t: find((lambda n: pow(n, 3)) , t, 10 ** 16) ],
['2 ^ n' , lambda t: find((lambda n: pow(2, n)) , t, 100) ],
['n!' , lambda t: find((lambda n: math.factorial(n)) , t, 100) ],
]
# print results
print '%-12s' % 'f(n)',
for i in ('second', 'minute', 'hour', 'day', 'month', 'year', 'century'):
print '%12s' % i,
print
print '-' * (13 * 8 - 1)
for i, algo in enumerate(algos):
print '%-12s' % algo[0],
for t in periods:
if i == 0:
print '%12s' % ('1e+(%.1e)' % (math.log(10, 2) * t)),
else:
val = algo[1](t)
if (val < 1e12):
print '%12d' % val,
else:
print '%12.1e' % val,
print
if __name__ == '__main__':
main()
・出力結果
f(n) second minute hour day month year century
-------------------------------------------------------------------------------------------------------
lg n 1e+(3.3e+06) 1e+(2.0e+08) 1e+(1.2e+10) 1e+(2.9e+11) 1e+(8.7e+12) 1e+(1.0e+14) 1e+(1.0e+16)
sqrt n 1.0e+12 3.6e+15 1.3e+19 7.5e+21 6.9e+24 1.0e+27 1.0e+31
n 1000000 60000000 3600000000 86400000000 2.6e+12 3.2e+13 3.2e+15
n lg n 62746 2801417 133378058 2755147513 72876948666 798145165979 6.9e+13
n ^ 2 1000 7745 60000 293938 1621649 5617557 56175574
n ^ 3 100 391 1532 4420 13802 31600 146678
2 ^ n 19 25 31 36 41 44 51
n! 9 11 12 13 15 16 17
参考：
Introduction to Algorithms, Third Edition Supplemental Content
http://mitpress.mit.edu/algorithms/
Video Lectures – MIT Open Courceware
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/
