安定結婚問題（ Gale-Shapley アルゴリズム）
クリスマスだし、有名なマッチングアルゴリズムぐらい書いておこうと思って書いた。
安定結婚問題
安定結婚問題（あんていけっこんもんだい、英: stable marriage problem）とはデイヴィッド・ゲールと ロイド・シャプレイによって1962年に提示された問題である。 安定結婚問題は {\displaystyle n} n人の男性と {\displaystyle k} k人の女性、および、各個人の選好順序からなる。選好順序とは各個人の好みに基づき異性全員と自分自身を全順序で並べたリストである。ここで、「自分自身」とは誰とも結婚せずに独身のままでいることを意味し、「参加者全員が独身であるよりも望ましい相手と結婚している」マッチングは個人合理性（英: individuality rationality）を満たすと定義される。安定結婚問題の解は安定なマッチングである。安定結婚問題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在せず、全員が個人合理性を満たすマッチングを安定マッチング（英: stable matching）という。
シミュレーション
python3, numpy でやってみた。 無駄とバグはあるかもしれません。
n 人どうしのマッチングを考慮しており、各行ごとに 0 〜 n-1 をシャッフルした n 次正方行列を ndarray で生成し、ペアとなった結果を表示します。
n次正方行列による優先順位行列を用いて安定結婚問題を解くシミュレーション
結果
4人同士のマッチング
$ python3 gale_shapley.py 4 [[2 1 0 3] [0 2 3 1] [1 2 3 0] [2 0 3 1]] [[1 2 0 3] [1 3 0 2] [0 2 3 1] [0 2 1 3]] Engaged (0, 2) Engaged (1, 0) Engaged (2, 1) Already engaged (0, 2) Already engaged (1, 0) Engaged (3, 3) [[0 2] [1 0] [2 1] [3 3]]
5人同士のマッチング
$ python3 gale_shapley.py 5 [[3 4 2 0 1] [1 0 4 3 2] [0 4 3 1 2] [1 4 2 0 3] [0 4 2 1 3]] [[3 2 4 1 0] [3 1 2 4 0] [2 1 4 0 3] [2 1 0 4 3] [0 1 3 4 2]] Engaged (0, 3) Engaged (1, 1) Engaged (2, 0) Already engaged (1, 1) Discard (1, 1) Engaged (3, 1) Already engaged (2, 0) Engaged (4, 4) Already engaged (3, 1) Already engaged (2, 0) Already engaged (4, 4) Discard (4, 4) Engaged (1, 4) Already engaged (2, 0) Already engaged (1, 4) Engaged (4, 2) [[0 3] [1 4] [2 0] [3 1] [4 2]]
モンティホール問題シミュレーション
Python の勉強も兼ねて投稿。
モンティホール問題
「プレーヤーの前に閉まった3つのドアがあって、1つのドアの後ろには景品の新車が、2つのドアの後ろには、はずれを意味するヤギがいる。プレーヤーは新車のドアを当てると新車がもらえる。プレーヤーが1つのドアを選択した後、司会のモンティが残りのドアのうちヤギがいるドアを開けてヤギを見せる。
ここでプレーヤーは、最初に選んだドアを、残っている開けられていないドアに変更してもよいと言われる。プレーヤーはドアを変更すべきだろうか？」
シミュレーションコード
実際にシミュレーションしてみる。 コードは Python の3系。
結果
出力の一例。
$ python3 ./montyhall.py No change: 0.33271 Change: 0.66709
ドアは変更しましょう。
- 作者: 平岡和幸,堀玄
- 出版社/メーカー: オーム社
- 発売日: 2009/10/20
- メディア: 単行本（ソフトカバー）
- 購入: 10人 クリック: 133回
- この商品を含むブログ (31件) を見る
DataNodeのConfigured Capacity
CDH4.2.0で。
HDFSのWebUIみたり、コマンドラインで
hdfs dfsadmin -report
したときに表示されるDataNodeごとのConfigured Capacity。
どうやら計算方法がdfs.datanode.data.dirに指定したディレクトリそれぞれに対してFile#getTotalSpace()を取得した値の合計をとっているらしい。
なので例えば、本番ではパーティション4つに分けるつもりでhdfs-site.xml設定したとして
それをテスト環境でも使いまわしたいときに同じパーティションに
ディレクトリを4つ作っただけだとConfigured Capacityは本来の4倍のサイズになる。
Used(GB)については単にduした値を合計しているらしく
こちらは本来の利用容量と変わりないため、その他の項目の計算に狂いが出てくる。
当然WebUIのUsed(%)のゲージもおかしくなり、パッと見での判断が辛い。
