- 追加された行はこの色です。
- 削除された行はこの色です。
[[サンタクロース問題]]
[[OCamlテクニック/サンタクロース問題]]
* 問題の定義 [#m10796f4]
[[今日の一行:http://karetta.jp/article/blog/oneline/030756]]より。
以下の動作をシミュレートするプログラムを作りたい。
> ねぼすけサンタがいる．休日が開けて，９頭いるトナカイ全員が戻ってくるか，１０人いるこびとさんのうち３人がやってきて起こしてくれるまでずっと寝てるというわけだ．
> ９頭組のトナカイに起こされたら，ハーネスをつけてソリを引かせてオモチャを配りに行く．配りおわったらトナカイたちのハーネスを外す．そしたらトナカイたちは休日だということでどこかにでかけてしまう．
> ３人組のこびとさんたちに起こされたら，会議をひらいて次期のオモチャをどうするかをこびとさんたちに伝授する．すんだらこびとさんたちは自分の仕事にもどっていく．
> トナカイ９頭組とこびとさん３人組が同時にサンタが起きるのを待ってる場合にはトナカイの方を優先する．トナカイもこびとさんもまたそのうちに三々五々やってくる．一旦やってきたトナカイは９頭揃ってオモチャを配り終えるまで、こびとさんは３人揃ってミーティングが終るまで勝手に帰ってしまうことはない．
* OCamlによる実装例 [#ye3f04e2]
(*
サンタクロース問題の実装例
to compile:
ocamlc -thread unix.cma threads.cma santa.ml
*)
open Event
(* 補助関数 *)
let (@@) f g = f g
let ($) f g x = f (g x)
let delay () =
Thread.delay (Random.float 3.)
let rec loop f =
let _ = f () in loop f
let forever f =
Thread.create loop f
(* トナカイがサンタの部屋に入った事を告げるチャンネル *)
let rch = new_channel ()
(* こびとがサンタの部屋に入った事を告げるチャンネル *)
let ech = new_channel ()
(* サンタにトナカイもしくはこびとが人数分集まったことを告げるチャンネル *)
let sch = new_channel ()
let actor ch n =
for i = 0 to n do
ignore @@ Thread.create (fun () -> delay (); sync @@ send ch ()) ()
done
let reindeer = actor rch
let elf = actor ech
let santa () =
wrap (receive sch) (function
`Reindeer ->
Printf.printf "santa deliver with reindeer\n";
flush stdout;
reindeer 9
| `Elf ->
Printf.printf "santa confer with elf\n";
flush stdout;
elf 3)
let wait ch n =
for i = 0 to n do
sync @@ receive ch
done
let _ =
Random.self_init ();
let t =
forever (sync $ santa)
in
ignore @@ forever (fun () -> wait rch 9; sync @@ send sch `Reindeer);
ignore @@ forever (fun () -> wait ech 3; sync @@ send sch `Elf);
reindeer 9;
elf 10;
Thread.join t
* ちょっと解説 [#v05db5d2]
サンタ、9頭のトナカイ、10人のこびと、9頭のトナカイを待つ人、3人のこびとを待つ人、それぞれがスレッドです。
トナカイとこびとは、それぞれランダム時間待つと、チャンネルを通じて仲介人に到着を知らせます。
トナカイの仲介人は、9頭集まるとサンタにトナカイが集まったことを知らせます。
こびとの仲介人は、3人集まるとサンタにこびとが集まったことを知らせます。
サンタは、トナカイかこびとが集まると指定の仕事をして、また待ちに入ります。
イベントを集約してまた別のイベントを発生させるという、簡素な例ですね。
トナカイとこびとにそれぞれ名前を付けてもよかったのですが、
問題に要請がなかったのでやめました。
名前のリストを持って回るだけで、本質的な仕組みは変わりません。
コメント抜いて53行です。ちょっと多いか...。
#comment
![[PukiWiki]](image/caml3.jpg "[PukiWiki]")
