フィボナッチ関数にみるメモ化(memoization)の効果

Why is one of these two algorithms for finding the n-th Fibonacci number more efficient? – StackOverflow

setdefaultに置き換えるとシンプルに書けるが,関数呼び出しのコストがボトルネックになるので,やはりEAFPに考えるのがリーズナブル.

from functools import lru_cache


def fib(n):
    return n if n<2 else fib(n-1) + fib(n-2)


def fib2(n, d={0: 0}):
    if n < 2:
        return n
    else:
        try:
            return d[n]
        except KeyError:
            d[n] = fib2(n-1, d) + fib2(n-2, d)
            return d[n]
        
        
def fib3(n, d={0: 0}):
    return n if n < 2 else d.setdefault(n, fib2(n-1, d)+fib2(n-2, d))


@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n<2 else fib_memo(n-1) + fib_memo(n-2)


%timeit [fib(i) for i in range(30)]
%timeit [fib2(i) for i in range(30)]
%timeit [fib3(i) for i in range(30)]
%timeit [fib_memo(i) for i in range(30)]

%timeit [fib2(i) for i in range(10000)]
%timeit [fib3(i) for i in range(10000)]
%timeit [fib_memo(i) for i in range(10000)]
1 loop, best of 3: 692 ms per loop
100000 loops, best of 3: 7.04 µs per loop
10000 loops, best of 3: 22.2 µs per loop
100000 loops, best of 3: 5.24 µs per loop

100 loops, best of 3: 2.56 ms per loop
100 loops, best of 3: 10.1 ms per loop
1000 loops, best of 3: 1.81 ms per loop
広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください