とりとめのないことを書いております。
by tempurature
カテゴリ
全体
プログラミング
scheme
verilog
未分類
以前の記事
2016年 04月
2016年 03月
2016年 02月
2016年 01月
2015年 12月
2015年 11月
2015年 10月
2015年 09月
2015年 08月
2015年 07月
2015年 06月
2015年 03月
お気に入りブログ
PHPで競技プログラミング
メモ帳
最新のトラックバック
ライフログ
検索
タグ
その他のジャンル
ブログパーツ
最新の記事
情報処理技術者試験 お疲れ様..
at 2016-04-17 18:55
基本情報技術者試験 平成27..
at 2016-04-14 04:48
基本情報技術者試験 平成27..
at 2016-04-13 23:03
苦い薬(ハーブ、サプリメント..
at 2016-04-09 14:03
「おバカ度チェックリスト」を..
at 2016-03-24 09:54
外部リンク
ファン
記事ランキング
ブログジャンル
画像一覧
【racket】林先生が驚く初耳学! の結婚理論をシミュレーションで実証(したかったのだが…)
12/20の「林先生が驚く初耳学!」で林修さんが披露していた結婚に関する数学的考察について、シミュレーションで検証してみようと思いました。

この考察では、20歳から35歳の間に出会う人間のうち、一番自分とふさわしい相手と結婚するにはどうするのが最適か?という問題について扱っています。

ここでは、結論だけを書かせていただきますが、「20歳から35歳の間に出会う人間をn人とすると、最初に出会う(1/e)n人(つまり0.37n人)とのお付き合いでは結婚しないでおき、それ以降は、今までに付き合った人よりもいい人であれば結婚するのがよい」のだそうです。

さて、シミュレーションでは、集合{0, ..., n-1}の置換(permutation)を生成し、t人見送った時の自分と一番ふさわしい相手と結婚する確率、または自分が結婚するのが何番目の相手であるかということの期待値を算出してみます。

まず、(make-permutation n)関数を記述しました。置換のリストを出力する関数です。

>(make-permutation 3)
((0 1 2) (0 2 1) (1 0 2) (1 2 0) (2 0 1) (2 1 0))

しかし、この関数はnを多くした時にメモリを大量に消費するので、代わりに次のような関数を用意しました。

#lang racket
(require point-free)

(define (power-list l1 l2)
  (if (null? l2)
      l1
      (foldr append empty
             (map (lambda (x) (map (lambda (y) (append x y)) l2)) l1))))
   
(define (for-each-permutation proc n)
  (define (req header rest)
    (if (null? rest)
        (proc (reverse header))
        (for-each
         (lambda (n)
           (req (cons (list-ref rest n) header)
                (append (take rest n) (drop rest (add1 n)))))
         (range (length rest)))))
  (req empty (range n)))


しかし、この関数を持ってしても思った以上の計算効率が得られないようです。次のベンチマークを実行してみました。

(define (benchmark n)
  (time
   (let ((a 0))
     (for-each-permutation (lambda (x) (set! a (add1 a))) n)
   a)))


ベンチマークの実行結果です。
> (benchmark 5)
cpu time: 0 real time: 0 gc time: 0
120
> (benchmark 6)
cpu time: 0 real time: 0 gc time: 0
720
> (benchmark 7)
cpu time: 32 real time: 36 gc time: 32
5040
> (benchmark 8)
cpu time: 47 real time: 55 gc time: 31
40320
> (benchmark 9)
cpu time: 329 real time: 323 gc time: 62
362880
> (benchmark 10)
cpu time: 3141 real time: 3132 gc time: 690
3628800
> (benchmark 11)
cpu time: 36218 real time: 36340 gc time: 9431
39916800
n=10で3.1秒、n=11で36.2秒かかっています。置換の個数はn!(nの階乗)で与えられるので、n=12, 13, 14, 15のときはそれぞれ6分、78分、18時間、11日かかるものと考えられます。20歳から35歳の間に15人の相手と付き合う人もなかなかなものだと思いますが、このような場合は少し方法を変えたほうが良さそうです


[PR]
by tempurature | 2015-12-22 00:27 | scheme
<< コード効率と可読性について 【racket】lambda,... >>