より良いエンジニアを目指して

1日1つ。良くなる!上手くなる!

Pythonが提供するアルゴリズムのテクニック「メモ化」の機構

競技プログラミングで出題されるアルゴリズムを考える上で、メモ化というテクニックがあります。

%%time
def fib(n):
    if n <= 1:
        return 1
    return fib(n-1) + fib(n-2)

for i in range(1,20):
    print(fib(i))

再帰に対して、配列や辞書型を用意して、使われる値をキャッシュして同じ計算を繰り返さずに計算量を減らすテクニックがメモ化です。

%%time
memo = {}

def fib_memo(n):
    if n <= 1:
        return 1
    if n in memo:
        return memo[n]
    
    memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

for i in range(1,20):
    print(fib_memo(i))

そうすることで、高速化を図るというものです。

f:id:rimever:20190205220700p:plain

このメモ化をやろうとなると、頭の中がゴチャゴチャして来るのは私だけ?

調べたところ、Pythonにはこのメモ化を機能として提供しているようです。

qiita.com

こんな便利な機構があることに驚きました。

from functools import lru_cache

@lru_cache(maxsize=1000)

とつけるだけ

%%time
from functools import lru_cache

@lru_cache(maxsize=1000)
def fib_cache(n):
    if n <= 1:
        return 1
    return fib_cache(n-1) + fib_cache(n-2)

for i in range(1,20):
    fib_cache(i)

f:id:rimever:20190205221158p:plain

それだけで速くなってしまいます。この手軽さには驚きました。

おかげでややこしいことを考えずに済んでしまいます。

硬派な方々からするとプログラミングの醍醐味が失われると思われるかもしれませんが。

累乗の実装で試してみる

せっかくなので、これを使って何か書いてみようということで、累乗の計算方法について紹介されていたので自分の手で書いてみることにしました。

  • 整数aとbを取るmy_pow(a,b)という関数を宣言する
  • もちろん「a**b」と「**」は使わないで計算
  • bが1の時はaを返す
  • bが1ではないときには、my_pow(a,b / 2) * my_pow(a,b/2) * (b % 2 == 1 ? a , 1) ※b/2はもちろん整数
%%time
from functools import lru_cache

@lru_cache(maxsize=1000)
def my_pow(a,b):
    if b <= 1:
        return a
    return my_pow(a,int(b/2)) * my_pow(a,int(b/2)) * (a if b % 2 == 1 else 1)

print(my_pow(2,100))

なるほど二つに分けて計算するという方法ですね。

といってもこれが最速の実装方法ではないので、単純に2**100と計算した場合には負けます。

追伸 2/16

誤字脱字などを修正しました。

  • "もちろん「ab」と「」は使わないで計算"が変に太字になっている点を修正(*のエスケープをする必要がありました)
  • "これに対して、配列や辞書型を用意して、使われる値をキャッシュして〜"の"これ"が曖昧とのことで再帰を指していることを明示するように表現を修正

ご指摘いただいたupuraさんに感謝します。

upuraさんのブログでは、良質な記事が並んでいます。

upura.hatenablog.com

まだご覧になられたことのない方は、是非ご参照ください!