Comparison of running times

Python: 実行時間の比較

Introduction to Algorithms の 1章の章末問題を Python で計算してみる。

・問題

各関数 f(n) と時間 t に対して、アルゴリズムが問題を解くのに f(n) マイクロ秒かかるとき、
t 時間で解くことができる最大の問題のサイズ n を求めよ。

　関数 f(n)：　lg n　　√n　　n　　n lg n　　n²　　n³　　2ⁿ　　n!
　時間 t　　：　1秒　　1分　　1時間　　1日　　1月　　1年　　1世紀

・コード

二分検索で解くコード。ただし、lg n に関しては n が大きくなりすぎるので直接 2^t を求める。

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/