2021年6月19日土曜日

Google Colaboratoryでのpythonファイル(.py)の利用について

 Google Colaboratoryはpythonを動かすのに便利な環境ですが、Jupyterの環境ですのでJupyterファイル(.ipynb)を動かすことになります。クラスやライブラリを作成してpythonファイル(.py)にしたときに、取り込みをできるようにしていきます。

(1) pythonファイルを用意する

今回は、下記のような2点を与えてその2点間距離と中点を求めるクラスのプログラムを作成してあるとします。これを自分のPCで「PointDrive.py」として保存して下さい(Colab上でやるのではなく、自分のローカルPC上でやる)。

[PointDrive.py]

(2) pythonファイル(PointDrive.py)をGoogle Driveの指定場所にアップロード

作成したPointDrive.pyをGoogle Drive上の決められた場所にアップロードします。

(3) Google ColaboratoryでJupyterファイルを開き、PointDrive.pyを利用する
Colab上でJupyterファイルを開きます。Jupyterファイルの保存場所はどこでも良いです。
(i) Google Driveをマウント

from google.colab import drive
drive.mount('/content/drive')

最初マウントを許可するための認証が入るかもしれません。

マウントができると、Jupyter上からDriveのファイルが見えます。

(ii) PointDrive.pyのパスを設定
PointDrive.pyが入っているディレクトリ(今回の例ではlibrary)を右クリックして、Copy pathをクリックします。そのパスを使って、下記のようにパスの設定をします。パスを設定後、PointDriveをインポートしてmdlとして使えるようにしています。

import sys
sys.path.append('/content/drive/MyDrive/public/python/library')
import PointDrive as mdl

(4) PointDriveクラスのインスタンスを作成して、実行する。

次のように座標を2つ与えてインスタンスを生成します。

x1 = [5, 7]
x2 = [2, 3]
p = mdl.PointDrive(x1,x2)

print('Distance = {0}, MidPoint = {1}'.format(p.get_distance(), p.get_midpoint()))

このように、クラスを利用して実行ができました。

main全体のコード

2021年6月8日火曜日

動的計画法(2) M/M/1の計算

 数式で漸化式で表現されれば、再帰関数を利用して動的計画法で計算できるということでした。今回は待ち行列のM/M/1の定常分布を動的計画法で求めていきます。

(1) 待ち行列 M/M/1の表現

式の表現は、[1]やhttps://www.win.tue.nl/~iadan/que/h4.pdfを見て欲しいのですが、リンクの式(2), (3), (4)がM/M/1の定常分布を出すための平衡方程式です。これをDPで解いていくのですが、その前にこの平衡方程式を解けば、定常分布の理論解が得られます。理論解は式(6)です。要するにここでは、理論解で得られた値とDPで得られた結果を比較して精度を確認していきます。

(2) 理論解の導出

この条件で、系内人数が10人となる確率は0.014078378677368164となります。

(2) DPでの算出
次に漸化式を利用して、再帰関数を作り、DPで同じ確率を算出します。漸化式を整理すると、3項間漸化式になり、pi(0)とpi(1)を初期値で設定します。
これをプログラムにします。
それなりの精度で出てきます。0.014078378677368164です。

このように漸化式であらわされているものは、再帰関数を用いて動的計画法として解いていくと便利です。

参考

[1] Bolch, G., Greiner, S., De Meer, H., & Trivedi, K. S. (2006). Queueing networks and Markov chains: modeling and performance evaluation with computer science applications. John Wiley & Sons.   (P105 Birth Death(λ_i、μ_i) P214でMM1(λ、μ)を与えている)


2021年6月6日日曜日

動的計画法(1)

 プログラムで再帰関数を利用することで、プログラムを簡略して書くことができます。特に漸化式で表されている数式をプログラミングする場合は、非常に簡単にプログラムができます。ここでは再帰関数が動的計画法で利用する場面を紹介します。プログラムの環境はGoogle Colabです。

(1) フィボナッチ数列をプログラムする ([1]参照)

フィボナッチ数列は前の2項(n-1とn-2)の和を現在の項(n)にするという数列です。これをプログラミングすると、下記になります。

これはフィボナッチ数列の第10項までを実行したものですので簡単に終わります。しかし、40項まで実行してみると、1分程度かかってしまいます。下記は3回の実行結果です。
40項 = 102334155 calclation_time:62.73430848121643[sec]
40項 = 102334155 calclation_time:62.58229374885559[sec]
40項 = 102334155 calclation_time:63.6257905960083[sec]

再帰計算を行うとき、同じ計算過程を何度も行う場合があり、計算上無駄が多くなっています。

(2) メモ化を利用する ([2参照])
メモ化は既に計算した値を確保しておき、必要になったときに利用していきます。既に計算されたものは値があるので、計算が驚くほど早くなります。下記は100000件を動かした結果です。
calclation_time:1.049574851989746[sec]
100000件でも1秒程度で計算できています。1,000,000件にするとメモリエラーになりました。

(3) 課題
メモ化でかなりの高速化ができるということがわかったが、メモリも消費する。MPIで並列計算を行い、メモリ分散ができるようにしてみたい。

[参考]
[1] 大和田 勇人, 金盛 克俊, Pythonで始めるプログラミング入門, コロナ社, (2015)
[2] Python言語によるプログラミングイントロダクション第2版 (著者省略), (2017)