Benchmark: http://cocodrips.hateblo.jp/entry/2015/10/11/114212#問題2

bench_cntsteps.py

# -*- coding: utf-8 -*-

###
### Benchmark: http://cocodrips.hateblo.jp/entry/2015/10/11/114212#問題2
###

from benchmarker import Benchmarker

try:
    xrange
except NameError:
    xrange = range


def step(n):
    """original code"""
    steps = [0 for i in xrange(n + 1)]
    #steps = [0] * (n + 1)
    steps[1] = 1
    steps[2] = 2
    steps[3] = 4
    for i in xrange(4, n + 1):
        steps[i] = steps[i - 1] + steps[i - 2] + steps[i - 3]
    return steps[n] % 1000000007

def step2(n):
    """improved code"""
    step1, step2, step3 = 1, 2, 4
    if n <= 3:
        return (step1, step2, step3)[n-1]
    for _ in xrange(n-3):
        step4 = step3 + step2 + step1
        step1, step2, step3 = step2, step3, step4
    return step4 % 1000000007



N = 99999

with Benchmarker(10, width=25) as bench:

    @bench('s[4]=s[3]+s[2]+s[1]')
    def _(bm):
        for _ in bm:
            step(N)

    @bench('s4 = s3 + s2 + s1')
    def _(bm):
        for _ in bm:
            step2(N)


###
### Result example
###
"""
$ python bench_cntsteps.py
## benchmarker:         release 4.0.1 (for python)
## python version:      2.7.7
## python compiler:     GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.51)
## python platform:     Darwin-14.5.0-x86_64-i386-64bit
## python executable:   /opt/vs/python/2.7.7/bin/python
## cpu model:           Intel(R) Core(TM) i7-4650U CPU @ 1.70GHz
## parameters:          loop=10, cycle=1, extra=0

##                             real    (total    = user    + sys)
s[4]=s[3]+s[2]+s[1]          7.3711    7.0500    4.6700    2.3800
s4 = s3 + s2 + s1            3.2293    3.2300    3.2200    0.0100

## Ranking                     real
s4 = s3 + s2 + s1            3.2293  (100.0) ********************
s[4]=s[3]+s[2]+s[1]          7.3711  ( 43.8) *********

## Matrix                      real    [01]    [02]
[01] s4 = s3 + s2 + s1       3.2293   100.0   228.3
[02] s[4]=s[3]+s[2]+s[1]     7.3711    43.8   100.0
"""