2014年6月1日日曜日

関数型とオブジェクト指向型プログラミング

近年、関数型言語というものが流行っている。関数型言語というのは、数学の関数を扱う感覚でプログラミングが行える言語だ。数学の関数は、インプットを与えると一意なアウトプットが得られるもののことである。

一般に、プログラムは数学の関数とは異なり、同じインプットに対しても内部の状態によって異なるアウトプットを返す。内部の状態とは、例えば、C言語の静的変数、オブジェクト指向言語のクラス変数、ディスク上のデータのことである。関数やメソッドが、内部の状態を変える場合には、その関数やメソッドは副作用を持つと言われる。プログラムはデータを保存したりしなければならないから、副作用はあって当然だ。今あるコンピュータは副作用があることを前提にできている。

しかし、副作用があるとプログラミングの難易度が上がる。インプットを網羅することは頑張ればできるが、状態を網羅することは難しい。テストですべての状態を作り出すことも大変だ。また、バグの発生条件が内部の状態にあれば、原因の特定も難しい。だれがその状態を作ったのかを見つけなければならないからだ。

そのため、なるべく副作用をなくしましょうというコンセプトで、関数型言語というのが最近注目されている。プログラミング言語は、書き方を制限してきれいな書き方に矯正しようというものだ。別に関数型言語を使わなくても、関数型プログラミングの目論見にあったコードはかけるが、関数型言語は関数型プログラミングがやりやすい。

最近の代表的なものは、Scalaだろう。Apache SparkがScalaで作られている。ただし、Scalaは純粋な関数型言語ではなく、オブジェクト指向型言語でもある。正直、関数型プログラミングだけではどういうふうに設計していいか分からない。人間の言葉はオブジェクト指向になっているので、人間の頭にはオブジェクト指向が馴染みやすく、設計も簡単だ。数学や論理学のように、記号を用いて表現した方が簡単な事柄には関数型がいい。なので、関数型とオブジェクト指向型をミックスするのは有用だと思う。

しかし、オブジェクト指向プログラミングは副作用を積極的にしましょうという技法とも言える。クラス変数にオブジェクトの状態変数を保存して、オブジェクトの状態を表現しようとしているのだから、当然だ。世の中のモノは、過去に受け取った入力を内部に保持して、それらを畳み込んだものを出力している。世の中のモノをコード上で表現しようとするオブジェクト指向は、副作用ありきだ。

そうすると、副作用が嫌いな関数型プログラミングと、副作用ありきのオブジェクト指向型プログラミングは食い合せが悪いようにも思える。

この問題を軽減する方法がないわけではない。思いつくのは以下のアイデアだ。要するにオブジェクト指向を関数型っぽく改変する。

  1. クラス変数は定数として、コンストラクタに与えられた値のみ保存する
  2. setterメソッドのようなオブジェクトの状態をの変えるメソッドは新しい値が入ったオブジェクトを返す
  3. getterメソッドのような値を返すメソッドは副作用を認めない

副作用があるメソッドとないメソッドを明確に区別することが大事だと思う。

1, 2は処理系の中では副作用をしていても構わないが、外からは副作用がないように見せて、状態変化を射影とするべきという考えである。

Obj obj = new Obj(val0)
obj = obj.setVal(val1)

こんな感じの書き方を強制しましょうということです。setValの中でreturn new Objみたいなことをするのを規定する。

obj .= setVal(val1)
あるいは
obj..setVal(val1)

みたいに省略可能なら冗長にもならない。実際古いobjなんて使わないから、処理系としてはreturn thisとすればいいんじゃないかな。古いobjを使う場合だけ、インスタンスのコピーを作っておけばよいのだ。

3はgetter的なメソッドも、オブジェクトを値に射影する関数と見せようという考えだ。ログ出力や標準出力、エラー出力は普通プログラムの動作に影響しないから副作用とみなさなくていいと思う;でないとデバッグにならない。

オブジェクトの状態を変えつつ、値を返す処理がしたいときは

obj.setVal(val0).method()

と書いたらよい。

Scalaとかこうなっていればよいのに。こういう風に決まっているプログラミング言語はあるのだろうか?

2014年5月18日日曜日

C-Python間のたらい回し

前回「C, Java, Pythonでのたらい回し関数」にて,C, Java, Pythonの生産性と性能を比較した.Cは面倒だが速い;一方でPythonは楽だが遅いということがわかった.
そうならば,全てCで書くのはだるいから,性能に影響しないところはPythonで書いてやれとなるかもしれない.あるいは,既存のCで書かれたプログラムを拡張するのに,Pythonを使うという場面もあるだろう.Pythonには,Javaと同じようにCと行ったり来たりするためのインターフェイスが用意されている.
そこで,CとPythonの間でたらい回しが行われるような,たらい回し関数の計算を行ってみた.
下の式のようなイメージで,Tarai_CをC,Tarai_PyをPythonで計算する.
tarai_func_equation2
ソースコードは以下のとおり.tarai.cとtaraiC.cからtaraiCmodule.soという名前の共有ライブラリをつくると,PythonからはtaraiCモジュールとして見える.上のTarai_C(x,y,z)がtaraiC.taraiToPython(x,y,z),Tarai_Py(x,y,z)がtarai.taraiToC(x,y,z)に相当する.

Tarai_C(12, 6, 0)とTarai_Py(12, 6, 0)の計算時間をグラフに示す(それぞれ項目C-Python, Python-C).参考として,通常のたらい回し関数をCのみ,Pythonのみで実行した場合の時間も示す.
cpuTimeC-Py
Tarai_C(12, 6, 0)とTarai_Py(12, 6, 0)の計算時間はほぼ同じであった.
Pythonのみより遅くなっているのは,Tarai_Cにて関数の呼び出し毎にモジュールのインポートを行っているからである.最初の1回のみ呼び出す方法もあるのだろうけど,ちょっと分からなかった.通常CとPythonを組み合わせるときにこんな使い方はしないだろうけど,非常に頻繁にPythonとCでやりとりをさせるのは,高速化という観点からはよくないようだ.
モジュールを独立させれるなら,プロセス間で通信した方がいいのだろうか?

2014年5月17日土曜日

C, Java, Pythonでのたらい回し関数

CとJavaとPythonを業務で使ってみて,同じことをさせるプログラムを書くのに労力が全然異なる.Cと比べたらJavaはすごく楽で,Javaと比べたらPythonは楽だ.コーディングに要する時間が大きく変わる.特に,C言語はエラーチャックから全て行わなければならないし,標準ライブラリも貧弱で使いにくい.処理速度の問題さえ解決できれば,CなんてOS専用言語でアプリケーションには使用するべきではないと思う.

と思ったものの,実際CとJavaとPythonの性能がどの程度違うのか良く知らない.そこで,同じ処理をするプログラムを3種類の言語で作って性能を比較した.

たらい回し関数を計算するプログラムを作った.たらい回し関数は,

tarai_func_equation

と定義される.計算に時間がかかるだけの特に意味のない関数だ.

x, y, zの引数と試行回数を入力すると平均の計算時間を表示するプログラムを以下に示す.上から順にC, Java, Pythonである.エラー処理は最低のみで,異常があったら停止するようにしている.わざわざコードを貼るのは,ソースコードの分量の違いを示したいからである.なお,CはLinux環境用である.



C, Java, Pythonでそれぞれ行数は44, 24, 10行と開発規模が大きく異なる.実際作成にかかった時間もかなり異なる.

特に,Cのエラー処理は非常に面倒で,異常があったらとりあえず止まる,いわゆる「自働化」をさせるのにも工数を割かなければならない.今回はメモリを解放する必要がなかったが,メモリの管理を加えたらCのコードはさらに肥大化する.

Pythonが非常に簡潔なのは,timeitという実行時間測定のモジュールがあったことが大きい.また,Javaと比較して,いちいちクラスを作らなくてもいいということや,整数もクラスなので,Integerクラスのようなわかりにくいクラスがないことが規模を小さくしている.また,関数の引数や返り値の型を決めていないので,doubleでもそのまま使えるというメリットがある.逆に動かしてみないと動くかどうかわからないという問題はあるが,どうせテストするので大した欠点ではない.

Tarai(16, 8, 0)の10回の計算時間の平均値を比較すると,グラフのようになった.ちなみにJava, Pythonの環境はそれぞれOracle JDK7, Python 2.7である.

cpuTimeTarai16,8,0

結果を見ると,Cが最も速く,Pythonが非常に遅い.JavaとCを比較すると4倍程度の差なので,CPUがボトルネックになる場合以外はJavaを使用するべきだ言える.Pythonに関してはやはり遅すぎるので速度が問題になるのであれば,避けるべきだろう.しかし,速度が問題になるのでなければ,開発効率だけでなく,教育や保守に要する費用を考えるとPythonは積極的に使用するべきだろう.

2014年3月23日日曜日

MapReduceとN体問題

天体や分子動力学(MD)といったN体問題は計算量が多い問題としてよく知られている.近年流行しているHadoopのMapReduceの計算モデルがN体問題にも適用できると気づいたので,記録しておく.

N体問題とは,複数の質点が各々相互に作用して運動する系について解く問題である.この問題がやっかいなのは,位置と運動量が与えられた1個の質点に関して,次の瞬間の位置と運動量を求めるためには,他のN-1個の質点の位置を知る必要があることだ.1個の質点に関してN-1個の質点との作用を計算しなければならないので,全体ではN*(N-1)回の計算を行う必要がある.計算量の多い問題は,複数のマシンで並列に計算をしたいが,1ステップの計算に全ての質点の情報が必要なので,マシン間の通信が問題となる.こういったプログラミングをするのは非常に面倒だ.

最近にわかに注目を集めているHadoopはMapReduceという計算モデルに落とし込める計算に関しては,簡単に並列分散処理を行うプログラムを作ることができる.MapReduceは演算をMapとShuffleとReduceの3段階に分ける.Map,ReduceフェイズにもちいるMap関数とReduce関数はユーザーが独自にプログラミングできる.

Map関数は,KeyとValueのデータの組から,異なるKeyとValueの組のリストを作成する.

Map(<K1, V1>) -> list <K2, V2>

Shuffleのフェイズで同じKeyをもつ組が集められ,<K2, list V2 >の形になる.

Reduce関数で,Valueが一つの値になる.

Reduce(<K2, list V2>) –> <K2, V3>

この一連のMapReduceの流れをN体問題に置き換える.iが質点の番号,xi, piが質点iの位置と運動量である.

Map関数で,質点iの位置を全てのj = 0…N-1に対して割り当てる.

Map(<i, xi>) -> list <j, xi> (0<j<N-1, j != i)

そうするとShuffleで全ての質点の位置が集まるので,Reduce関数で質点jの次のステップでの位置と運動量を求めることができる.

Reduce(<j, list xi>, xj, pj) –> <j, x’j, p’j>

Reduce関数の入力値には,当然質点jの現在の位置と運動量が必要とされる.

MapReduceジョブ1回が1ステップの計算となる.現実的には,HadoopではMap, ReduceでそれぞれN回JVMを立ち上げることになるので(JVMの再利用を行うならプロセス数分),1ステップで2N回JVMを起動して落とす.また,MapReduceの度にHDFSに書き込みが行われる.インメモリで計算すべきだが,HDFSのキャッシュ機能がどう働くかは分からない.MapReduceジョブはオーバーヘッドが大きいから,現実的ではないと思う.

2014年3月22日土曜日

一様なライフゲームの統計的性質4:フラクタル解析

高エントロピーなライフゲームにフラクタル分析を適応してみる.

ビットマップを用いた高速計算

1セルに8ビット割り当てて,セルごとに次のステップの値を計算するのは時間が非常にかかるので,ビットマップを用いて,高速に計算できるコードを新たに作成した.また,4x4セルの取りうる全て場合について,次の値をキャッシュすることで,4セル毎に同時に計算している.マルチスレッド計算も行っている.

コードはGitHubにある

ボックスカウント法

対象は8192セルx8192セルで周期境界条件のフィールド.最もエントロピーの高いと思われる,確率0.364でtrueとなる一様にランダムな配置を初期値とする.

フラクタル解析にはボックスカウント法という方法を用いる.ライフゲームのtrue/falseの値と,一様なライフゲームの統計的性質3で定義した生存/死滅の値について調べる.

図1に,ボックスサイズとtrueセル(上のGIF動画で黒と赤のセル)を含むボックス数の関係を示す.16x16セル以上のボックスサイズでは,傾きは-2でありフラクタル次元は2となっている;のっぺりとしているということ.16x16セルがあれがライフゲームの特徴が現れているといえる.16セル以下のでは傾きが一定となっておらずフラクタル性は見出せない.

図1 ボックスサイズと真セルを含むボックス数
black

図2に,ボックスサイズとaliveセル(下のGIF動画で赤とピンクのセル)を含むボックス数の関係を示す.この場合は16セルに収まらない.ステップ数が大きくなるほど,フラクタル次元が2となるボックスサイズは大きくなる.ボックスサイズが小さい領域でも,傾きがほぼ一定となっておりフラクタル性を持っているといえる.グラフの読み取り方にもよるが,フラクタル次元はおよそ1.2である.

図2 ボックスサイズと生セルを含むボックス数
alive

結論

生存/死滅でみると,ライフゲームもフラクタル性を持っている.

2014年1月12日日曜日

安定結婚問題を解くAndroidアプリ

2013年末にNHK教育の『オイコノミア』という経済学の番組で,合コンにてGale-Shapleyアルゴリズムを用いて最適なカップルを求めるということをしていた.是非,これを私もやってみたいと思ったので,簡単にできるAndroidアプリを作った.

ここからインストーラ: StableMatching.apkをダウンロードできる.

Android端末にて「サードパーティアプリケーションのインストールを許可する」と設定すれば,インストール可能.

2014-01-13 追記
せっかくつくったので$25払ってAndroidマーケットに出品しました

MainActivitySetPreferenceActivityResultActivity

いわゆる安定結婚問題というもので,「実は今の彼女よりお前のほうが好きやってん」「え!?私も##」という悲劇がなくなる組み合わせを探してくれる.参加者全てに,好みを入力して貰って,Arrangeボタンを押すと,みんなが幸せになるカップルをつくる.

用途は合コンに限る必要はないが,合コン以外の用途は思いつかない.しかし,こんなアプリをおもむろに取り出したら,引かれないかというおそれはある.また,こういうのに興味してしてくれる素敵過ぎる人は,そもそも合コンなんかに来ないという問題もある.

ただ,安定結婚問題なんてものは,全員が好みの順位をつけることができて,かつ,それを教えてくれる(一応人の好みは見れないようになっているが)という特殊な状況を想定している.しかし,そういう状態になった段階,すでに問題の9割は解決している.それぞれの嗜好がわからないから人間関係はやっかいなものだと思う.まあ,数学者の考えそうな現実を無視した理想的な問題ということか.嗜好を推論してくれる機能とかがあれば,画期的な発明になるのだろうけど,まだアイデアはない.