MapReduceとN体問題

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

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

最近にわかに注目を集めているHadoopはMapReduceという計算モデルに落とし込める計算に関しては，簡単に並列分散処理を行うプログラムを作ることができる．MapReduceは演算をMapとShuffleとReduceの３段階に分ける．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ジョブ１回が１ステップの計算となる．現実的には，HadoopではMap, ReduceでそれぞれN回JVMを立ち上げることになるので（JVMの再利用を行うならプロセス数分），1ステップで2N回JVMを起動して落とす．また，MapReduceの度にHDFSに書き込みが行われる．インメモリで計算すべきだが，HDFSのキャッシュ機能がどう働くかは分からない．MapReduceジョブはオーバーヘッドが大きいから，現実的ではないと思う．

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

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

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

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

コードはGitHubにある

ボックスカウント法

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

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

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

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

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

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

結論

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

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

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

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

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

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

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

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

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

タイムトラベルの分類 改定版

先日，タイムトラベルの分類についての記事で，歴史改変がなくて；かつ同一人物が同時代にいないタイプのタイムトラベルはないとした．しかし，『タイム・リープ　あしたはきのう』（電撃文庫　上下巻）が，まさにそのタイプであったので改定することにする．

---

タイムトラベルはSFでは一般的な仕掛けである．SF上のタイムトラベルにはいくつかの種類が存在する．そこで，SF物語上のタイムトラベルを分類していこう．

よくみられるように，２つの軸に分けて，４象限のマトリクスで分類していく．１つ目の軸は，歴史改変がある／ないの分類；２つ目の軸は同時代に同一人物がいる／いないの分類．

歴史改変がある／ないとは，時系列もしくは因果関係の系列が一本なのか；それともタイムトラベルによってそれらが変化するかどうかということである．設定で歴史改変が認めれていたとしても，物語の上で歴史改変がなされないものは，歴史改変がないに含める．

同時代に同一人物がいるこる／いないとは，昨日に飛んだときに，昨日の自分がそこにいるタイプなのか；いないタイプなのかという分類だ．意識のみが時間を越えるのか；もしくは，身体も含めて時間を越えるのかは問わない．この分類は『傾物語』で少し言及されていた．『傾物語』は最後まで見ていないので，まだ分類できない．

以下の表に具体的な作品を分類する．便宜上それぞれに[A],[B],[C],[D]とラベルをつける．

	歴史改変がある	歴史改変がない
同一人物が同時代にいる	[A] バック・トゥ・ザ・フューチャー ルーパー	[B] 夏への扉 涼宮ハルヒの憂鬱 ドラえもん(？)
同一人物が同時代にいない	[C] 時をかける少女 シュタインズゲート 魔法少女まどか☆マギカ	[D] タイム・リープ　あしたはきのう

[A]が映画ではもっとも一般的だ．タイムトラベルによる混乱が生じて，物語的に面白くなりやすい．

しかし，どうしても歴史改変による矛盾：タイムパラドックスが生じてしまう．タイムトラベルなんで存在しないのだから仕方がない．それを強引にどう解決するかもタイムトラベルものの面白さのひとつだ．有名なタイムパラドックスに親殺しのパラドックスというのがある．過去に戻って自分が生まれる以前に親を殺したら自分が存在できないというやつだ．これを表現するにはどうすればよいのか．

映画でよくあるのが，歴史的な時系列を無視して，物語の中での時系列で因果関係を表現するというものだ；『バック・トゥ・ザ・フューチャー』では，自分の存在が危うくなると，体が透けてくる；また，『ルーパー』では，現在の自分の体に傷をつけると，未来の自分にその傷あとが現れる．親を殺せば，存在自体が最初からなくなってしまうのだから，自分が過去に行くというイベントが成立しえないはずだ．しかし，この表現では過去にいくというイベントは存在するけど，親殺しの影響は受けるとするのである．過去での歴史改変の影響は，時間を越えて現れるのである．

[B]は，時間軸が完全に一本でタイムトラベルの結果が，タイムトラベルするまえに既に反映されている．登場人物が過去に行って，いくら頑張ってもすでに未来は決定していて変えようがない既定事項なのだ．親を殺ろそうといくら努力して，成功しない．パラドックスが生じないのが利点である．しかし，結果が分かっているので終着点の意外さは損なわれてしまう．また，結果が決まっているのに登場人物はなんで頑張っているのだろうと思ってしまう点もある．一方で，伏線を貼りやすいという利点もある．未来の情報を頼りにして，すでに分かっている結果に帰着するように工作する．結果でなくてプロセス重視のタイプである．

『ドラえもん』を（？）をつけてここに入れたのは，設定が一貫していないからだ．[A]にも思えるが，タイムパトロールが頑張っているので，結果として[B]となっているのだろうか？ドラえもんがやっていくる未来は一定だ．昔話題になった同人作品のドラえもん最終話は[B]に分類される．

[C]は『時をかける少女』に代表されるタイプだ．過去の自分に戻ることができる．このタイプも，意識が過去の自分に飛ぶだけならタイムパラドックスが生じない．なぜなら，歴史が改変されて，時間軸が分岐することはあっても，[A]のように時間軸がループすることはないからだ．タイムパラドックスは，本来一方向であるはずの因果関係が，過去と未来がくっつくことで輪になってしまうために生じるのだ．また，自分の生前にタイムリープしたらどうなるのだという問題は残る．生前にタイムリープしたら，タイムパラドックスが生じてしまう．間宮千昭もしくは深町一夫はどうやって未来に帰るのだろうか？

『魔法少女まどか☆マギカ』の暁美ほむらの能力も[C]に分類される．世界の時間軸を分岐させるという相当すごい能力である．（2013/11/3）

[D]は一般には成立しない．過去の自分にタイムリープしただけで，必然的に歴史が改変されるからだ．『ドラえもん』の『人生やりなおし機』は[D]に近い．今の頭で過去に戻っても，結局同じことになるというオチ．『ドラえもん』はいろんなパターンを含んでいる興味深い作品だ．

『タイム・リープ　あしたはきのう』は，同じ時間を繰り返さないという制約を付け加えることで，[D]を実現している．[D]は成立しないと思っていたが，この作品で[D]のタイプが成立することが証明された．作中で[A][B][C]それぞれのタイプの作品について言及されていたので，この作品はあえて[D]の位置を狙っていると思われる．『タイム・リープ』はタイムトラベルものの中でも，特異な位置にある重要な作品である．

一様なライフゲームの統計的性質３

生存／死滅のセルの定義

ライフゲームの挙動を観察すると，不規則な動きのある部分と静止，または周期的な振動する部分に分かれていることがわかる．この不規則な挙動を示す箇所を生存している（Alive），静止・振動の部分を死滅している（Dead）と呼ぶことにする．

以下の１，２，３のいずれか場合のセルを死滅していると定義する．死滅でないセルを生存していると定義する

1. 自セルおよび周囲８セルが全てfalse
2. ２ステップ連続で自セルおよび周囲８セルが同じ値をとる
3. 自セルおよび周囲８セルが周期２の振動を２サイクルする

過去の状態を参照して生存か死滅を決定する．条件２の場合は２ステップ，条件３の場合は４ステップを参照する．周期３以上は，ほとんど存在しないので無視することにする．

また，過去の状態を参照するため，死んだ状態になってから判別するまでに遅れが生じる．条件１の場合は，その傾向を防止し，生存と死滅の境界を明確にするためである．前々回に示した動画は条件１を加えていない．

例として，以下のGIFアニメを示す．赤・ピンクが生存するセル．白・黒が死滅したセルでる．赤・黒がtrue，ピンク・白がfalseである．不規則な挙動を示す場所を区別できていることが分かる．

---

条件

セル数は8192x8192とした．初期条件は確率p0=0.364でtrueとなるような乱数を一様に与えた．

---

生存のセルの割合の時間変化

以下に生存のセルの割合の時間変化を示す．横軸は前回示したグラフとは異なり，対数軸とはなっていない．

時間とともに生存セルは減少してゆく．とくに，２０００ステップから１００００ステップにて10^(-2.5E-4 x step)に比例して減少していることがわかる．この範囲では，ステップ毎に一定の確率でセルが死滅してゆく．この事実は，ライフゲームの挙動を統計的に議論できることを示している．

図１　生存のセルの割合の時間変化

---

追記　6/23/2013

p0=0.192の場合も追加した．対数グラフなので，8000ステップから異なった値をとっているように見えるが，10^-4のオーダーしか異ならないので実際にはほとんど一緒である．

一様なライフゲームの統計的性質２

条件

初期条件として，確率p0=0.074, 0.098, 0.133, 0.192, 0.364, 0.564でtrueとなる7ケースの一様な乱数を与えたときの挙動について調べてみる．

領域の大きさは4096x4096で，境界は周期境界条件とする．乱数にはc++のrand関数を用いた．貧弱な乱数かもしれないが，特に問題ないだろう．

---

真のセルの確率の変化

図１は真のセルの確率P(true)の時間変化である．

p0=0.192の場合は前回示したように，もしライフゲームが完全にランダムな挙動をするのであれば一定値をとる．しかし，ライフゲームではP(true)は時間と共に減っていき，約10000ステップで定常となる．

また，p0=0.564の場合は，１ステップでのP(true)（以後p1と呼ぶ）がp0=0.192のときと一致するように選んだ値である．両者は互いに一致する．したがって，一様な乱数の初期条件を与えても，密度以外の影響はないといえる．

p0=0.133, 0.192, 0.364, 0.564の場合は時間とともにP(true)は漸近していく．初期のP(ture)が大きい場合初期条件の影響は時間と共に失われていくことがわかる．p0=0.098, 0.074の場合も他の場合に近づいていく傾向にあるが，一致する以前に定常状態に達してしまう．

p0=0.074, 0.098, 0.133は一旦減少したのち，増加する．これらも初期条件の影響が時間と共に失われて，一般的な状態に近づく結果と思われる．

図１　真のセルの確率

---

一様ライフゲームの４つの挙動モード

一様ライフゲームの時間的に変化する挙動を４つのフェーズに分類する．

1. 立ち上がり
2. 漸近
3. 普遍
4. 定常

立ち上がり

立ち上がりは初期の分布の影響が強く現れている状態である．ランダムな初期条件を与えたが，ライフゲームではそのような状態になることはない．初期のランダムな状態は，ライフゲームにおいては「不自然」な状態なのである．そのため，数ステップを要して「自然」な状態に遷移する．

図２，図３は，それぞれ真および偽のセルのが次のステップで真になる確率P(true|true), P(true|false)である．とくにp0が小さい場合に顕著に現れているように，６ステップまでが立ち上がりフェーズである．

p0=0.192, 0.564は立ち上がりフェーズで値が異なっている．この２ケースはp1の値が一致するようにp0を選んだものである．p1が一致していても，分布の傾向は当然異なっている．しかし，立ち上がりフェーズによりこの２ケースの差異は吸収されてしまう．

漸近・普遍

立ち上がりのモードの後はp0=0.364のケースに漸近していく．p1が大きいケースほど早くp0=0.364と一致する．p0=0.364はp1が最大となるケースである．つまり，p0=0.364のケースが最も早く普遍フェーズに遷移し，p1が大きいケースから順に普遍フェーズに遷移していく．

普遍フェーズがどのような状態かは定かではないが，ライフゲームの一般的な性質をもつ状態と予想される．P(true)の変化曲線がべき乗則にしたがい始めた以降の部分が普遍フェーズである．

遷移フェーズとは，立ち上がりフェーズの後，普遍フェーズに遷移するまでの状態である．p1が小さいケース（p0=0.074）は漸近フェーズから普遍フェーズに遷移することなしに次の定常フェーズに遷移してしまう．

定常

定常フェーズとは，すべてのセルが一定値または周期的な挙動をするようなった，つまり死んだ状態になったフェーズである．どのケースでも約10000ステップで定常フェーズに達する．漸近・普遍フェーズから定常フェーズに突然達するわけではない．徐々に死んだセルが増えていき，すべてのセルが死んだときを定常フェーズと呼んでいる．したがって，普遍フェーズも定常フェーズに漸近しているのだが，便宜上，漸近と普遍フェーズの呼び方を区別している．

図2　真のセルから真のセルになる確率

図3　偽のセルから真のセルになる確率

一様なライフゲームの統計的性質１

ライフゲームとは

ライフゲームとは２次元セルオートマトンの一つであり，生命の繁殖死滅を模したシミュレーションモデルである．自らの値cと周囲８セルを参照として，以下のように次ステップでの値c’が決定される．s2は周囲8セルでtrueの値のセルが2，s3は3であることを示す．

この法則にしたがって時間ステップを進めて行くと，下の動画のようなうねうねとした興味深い挙動を示す．赤色のセルは変化の起こっているセル，すなわち生きているセルを示しているが，それについては今後述べていく．

ライフゲームの性質は，過去によく調べられている．しかし，グライダーやブリンカーといった具体的なパターンを見つけるものが多く，統計的な性質についてはあまり知られていないようである．そこでちょっと調べてみようと思う．

一様でランダムなときの挙動

あるステップで，一様に確率pでtrueのとなるような分布をしているとき，次ステップがtrueとなる確率p’は

となる．グラフに示すと以下のようになる．

特徴的な点は次の4点である．p’が最大値をとるp=(14-sqrt(115))/9=0.364，およびp=p’となるp=0.0, 0.192, 0.370である．

もし，分布がつねに一様でランダムであり，上式にしたがってtrueのセルの密度（確率）が変化するとすると，以下のグラフのように数ステップで密度はp=0かp=0.37に漸近する．p(0)=0.192の場合のみ例外でp=0.192を保つ．

もちろん実際のライフゲームでは上記のようにはならない．そこにライフゲームというものの特徴が現れているのである．今後，実際のライフゲームがどのような性質を持っているかを統計的に議論していく．