再帰関数を高速化するには?

追記:
勘違いしていたけど,「Memorization」ではなく,「Memoization」なんだね.
文中の「memorize」は「memoize」の方が尤もらしい.

参考:
メモ化 – Wikipedia

 
 

How to make this recursive function faster in Python or Java? – StackOverflow

計算が繰り返される様な構造を持った処理系では,
「functools.lru_cache」がリーズナブルチョイス.
元のコードは一切弄らず,関数を「@lru_cache」とデコレートするだけ.

この位の計算であれば,一瞬で処理できる(筈).

関連:
キャッシュ構造(同値反復構造)では「functools.lru_cache」が感動的

 

「5時間掛かる」 とか怖い事を言っているので,自分のPC上で処理させたくない.
という事で,Colaboratoryを使ってVM上で走らせてみる.

「functools.lru_cache」はPython 3.2以降にしか無いので,
Python2系では使えない.ColaboratoryのカーネルはPython2.7.14なので,
そのままではColaboratory上で使えない.その為,今回は
Colaboratory上で「%%writefile」Magic commandを使って
「.py」ファイルに書き出してから,
Python 3.6.3でPythonプログラム(「.py」ファイル)を実行する.

関連:
Colaboratoryについて(まとめ)

 
 

%%writefile example.py
import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
    res = 0;
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        res=(4*(f(n-1)))+f(n-2)        
    return res


def main():
  sys.setrecursionlimit(10000)
  print(f(2424))


if __name__ == '__main__':
    main()

Overwriting example.py

!python3.6 example.py

12811645111887631525475128340409754383702010324654360624942154540228791340642173492088690105771256884654221447044702887147589907921153496166236437695939355252697103801778677462085188924098182725088076503022685270760387219787300737538930978100645525578032205449174673556667517367894515395044506363952919291724514494639967260603654321435026048162210374865422028485743476872381190036845593067721505484899641669193471741435203077087818965534970827237008861720546333776398691518094206301299430723362960542655592512483605052144449911147446383972761571180832477426059987410922498622599233890416001827659244246018252661317668176588876191524476644458278180175907595564089578464053541289889658353085449595345638114956277894377440265809187328746620700929660403607063956264728957200026182242546508904331365657393956953665405467709075021873746717301068844742812640804898358450341147006070992231114309620413797728305363944857231248633777215681178048714555960583285769423269577347092318452597959376442984898597806086880665642171452358839585066290931829822758230731077830945167265530809939378117473625279556317267462647249640436890625269088579237115076783934027795187388832606550708659435481536443442236758890740290467476423736762596428858930168539918890341426049891374123602486910741965206888619217749898476459891203923419562022513871112849590210261873642501502900252092855836815672262020860038323118100356786638630880435236412040943537555010407001968832788551740072702579610201398332444667655843894415660856081122556945790699471646832

どれ位,Performanceが異なるかチェック.

%%writefile example_time.py
import sys
import timeit
from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
    res = 0;
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        res=(4*(f(n-1)))+f(n-2)        
    return res


def f2(n):
    res = 0;
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        res=(4*(f(n-1)))+f(n-2)        
    return res


def main():
  sys.setrecursionlimit(10000)
  print(timeit.timeit('f(2424)', globals=globals()))
  print(timeit.timeit('f2(2424)', globals=globals()))


if __name__ == '__main__':
    main()

Overwriting example_time.py

!python3.6 example_time.py

0.1175575239999489
1.0737350889999107

デコレートするだけで,約10倍高速化されている事が分かる.

それにしても,「5時間掛かる」というから恐る恐るだったけど,
そのままのコードでも1秒で処理できるじゃん.
これは,ColaboratoryのVMが優秀なのか.
(スペック的には「n1-highmem-2 instance」相当;関連参照)

関連:
Colaboratoryについて(まとめ)

 
 
こっからは余談(Colaboratoryの話).

パフォーマンステストのグラフを表示したい時,
どういうやり方が一番リーズナブルなんだろう.

直接グラフを表示する方法が分からないので,一旦画像ファイルをアウトプットする.
(出力先を指定してあげればできそうな気はするんだけど)

%%writefile example_time.py
import sys
import timeit
from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
    res = 0;
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        res=(4*(f(n-1)))+f(n-2)        
    return res


def f2(n):
    res = 0;
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        res=(4*(f(n-1)))+f(n-2)        
    return res


def main():
  import matplotlib.pyplot as plt

  sys.setrecursionlimit(10000)
  res1, res2 = [], []
  for i in range(1, 10001, 100):
    res1.append(timeit.timeit(f'f({i})', globals=globals()))
    res2.append(timeit.timeit(f'f2({i})', globals=globals()))

  fig = plt.figure(figsize=(20, 13))
  ax = fig.add_subplot(111)
  ax.plot(res1, label='memorize')
  ax.plot(res2, label='default')
  ax.set_xlabel('Num')
  ax.set_ylabel('Time [sec]')
  plt.legend(loc='best')
  plt.savefig('example2.png')

if __name__ == '__main__':
    main()

後はColaboratory上から画像を開く方法を考えるだけ.
まず,ぱっと思いつくのはやはりmatplotlib.

import matplotlib.pyplot as plt
import numpy as np
from PIL import Image

img = Image.open('example2.png')
np_img = np.asarray(img)
fig = plt.figure(figsize=(25, 18))
ax = fig.add_subplot(111)
ax.imshow(np_img)

FireShot Capture 787 - Untitled30.ipynb - Colaboratory_ - https___colab.research.google.com_

でも,綺麗ではない.画像サイズやdpiを調整するのも面倒.

「IPython.display.Image」を使うのがリーズナブルかな.

from IPython.display import Image

Image('example2.png')

ダウンロード

まーでも,どうせColaboratoryで結果をグラフ化したいなら,
Python3の方では結果だけだしてpickle化して,
Colaboratory上でグラフを書いた方がリーズナブルか.

メモ:
Python2/Python3間でpickleを渡す時
「protocol=2」(3未満)を指定しないと
2側で読み込めない.

%%writefile example_time.py
import sys
import timeit
from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
    res = 0;
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        res=(4*(f(n-1)))+f(n-2)        
    return res


def f2(n):
    res = 0;
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        res=(4*(f(n-1)))+f(n-2)        
    return res


def main():
  import pickle

  sys.setrecursionlimit(10000)
  res1, res2 = [], []
  for i in range(1, 10001, 100):
    res1.append(timeit.timeit(f'f({i})', globals=globals()))
    res2.append(timeit.timeit(f'f2({i})', globals=globals()))

  with open('res1.pickle', 'wb') as f:
    pickle.dump(res1, f, protocol=2)
  with open('res2.pickle', 'wb') as f:
    pickle.dump(res2, f, protocol=2)

  print('Done')


if __name__ == '__main__':
    main()

Overwriting example_time.py

!python3.6 example_time.py

Done

import pickle
import matplotlib.pyplot as plt

with open('res1.pickle', 'rb') as f:
  res1 = pickle.load(f)
with open('res2.pickle', 'rb') as f:
  res2 = pickle.load(f)

num = [i for i in range(1, 10001, 100)]

fig = plt.figure(figsize=(20, 13))
ax = fig.add_subplot(111)
ax.plot(num, res1, label='memorize')
ax.plot(num, res2, label='default')
ax.set_xlabel('Num')
ax.set_ylabel('Time [sec]')
plt.legend(loc='best')

FireShot Capture 790 - Untitled30.ipynb - Colaboratory_ - https___colab.research.google.com_

細かい修正もできるし.
(気付いていなかったけど,グラフちょっと間違っていた)

 
 
関連:
キャッシュ構造(同値反復構造)では「functools.lru_cache」が感動的

Colaboratoryについて(まとめ)

広告
カテゴリー: 未分類 パーマリンク

再帰関数を高速化するには? への1件のフィードバック

  1. ピンバック: Colaboratory便利なのに…… | 粉末@それは風のように (日記)

コメントを残す

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

WordPress.com ロゴ

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

Google フォト

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

Twitter 画像

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

Facebook の写真

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

%s と連携中

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