元ネタ
サイコロで同じ目が100回連続で実際に出るか - Qiita
並列プログラミングの題材に丁度いいかなと思って。
仕様
試行: 1度サイコロを振って目を決める、その後サイコロを振りその目が最初の目と同じならばまたサイコロを振る、のステップを最大100回繰り返す
試行の結果: 試行にて振ったサイコロの回数。最初のものを除く。0~100の範囲を取る。
プログラム: 試行の結果が100になる、あるいは10億回試行を行ったら停止する。また、停止するまでに行った試行において、何回試行を行ったかと試行の結果がnである回数がi回であったかを記録する
まあ、確率的に10億回程度の試行じゃ試行の結果が100になることなんてほとんどないと思うけど。
実装
方針
- タスクを小分けにしてnum_ths個のスレッドに投げる
- 1試行毎に投げていてはコミュニケーションコストが嵩むのでbatch_size個まとめて投げる
- スレッド全てにタスクを投げてスレッド全てから結果を受け取り、結果を検査するの流れを10億/(num_thsbatch_size)回行なう((num_thsbatch_size)は10億の約数になるように調整する)
コード
乱数を用いるので rand = "0.3" をCargo.tomlに追記しておく。
extern crate rand;
use rand::thread_rng;
use rand::Rng;
use std::thread::spawn;
use std::sync::mpsc::channel;
const NUM_SAME: usize = 100;
fn main() {
let num_ths = 10;
let batch = 10000;
let mut txs = Vec::new();
let mut rxs = Vec::new();
let mut table = [0;NUM_SAME+1];
let mut tries = 1;
for _ in 0..num_ths {
let (com_tx, rx) = channel();
let (tx, res_rx) = channel();
txs.push(com_tx);
rxs.push(res_rx);
spawn(move||{
let mut rng = thread_rng();
loop {
match rx.recv() {
Err(_) => return,
Ok(0) => return,
Ok(tries) => {
let res = (0..batch).map(|_| {
let base = rng.gen::<usize>() % 6;
for i in 0..NUM_SAME {
let eye = rng.gen::<usize>() % 6;
if eye != base {
return i;
}
}
return NUM_SAME;
}).collect::<Vec<_>>();
let _ = tx.send((tries, res));
}
}
}
});
}
'outer2: for _ in 0..10000 {
for i in 0..num_ths {
txs[i].send(tries).unwrap();
tries += batch;
}
for i in 0..num_ths {
let (tries, res) = rxs[i].recv().unwrap();
for (j, n) in res.iter().enumerate() {
table[*n] += 1;
if *n == NUM_SAME {
println!("suceeded after {} tries", tries + j);
break 'outer2;
}
}
}
}
for i in 0..(NUM_SAME+1) {
println!("{}:{}", i, table[i]);
}
for i in 0..num_ths {
txs[i].send(0).unwrap();
}
}
結果
$ time cargo run --release
Compiling 100dices v0.1.0 (file:///home/kim/Rust/100dices)
Running `target/release/100dices`
0:833318652
1:138900235
2:23150884
3:3858697
4:642567
5:107421
6:17943
7:3019
8:489
9:77
10:13
11:3
12:0
13:0
14:0
15:0
16:0
17:0
18:0
19:0
20:0
21:0
22:0
23:0
24:0
25:0
26:0
27:0
28:0
29:0
30:0
31:0
32:0
33:0
34:0
35:0
36:0
37:0
38:0
39:0
40:0
41:0
42:0
43:0
44:0
45:0
46:0
47:0
48:0
49:0
50:0
51:0
52:0
53:0
54:0
55:0
56:0
57:0
58:0
59:0
60:0
61:0
62:0
63:0
64:0
65:0
66:0
67:0
68:0
69:0
70:0
71:0
72:0
73:0
74:0
75:0
76:0
77:0
78:0
79:0
80:0
81:0
82:0
83:0
84:0
85:0
86:0
87:0
88:0
89:0
90:0
91:0
92:0
93:0
94:0
95:0
96:0
97:0
98:0
99:0
100:0
cargo run --release 34.20s user 449.97s system 637% cpu 1:15.99 total
Intel(R) Core(TM) i7-4910MQ CPU @ 2.90GHzの4コア8スレッドのマシンで実行。1分ちょっと。
どんぶり勘定する時は単純な処理なら1億ループに1秒らしいけど(10スレッド使って)10億ループに1分なので1回の処理が60倍くらい複雑だったっぽい？試行の結果によって重さが変わるので平均するとそんなもんか。
11まで届いたものが3回。まあ、こんなものかな。nが1上がると回数が1/6になってるのが見てとれる。
おわりに
最初に見た時にRustなら簡単に書けそうって思ってやってみたはいいものの1試行毎にチャネル使ってやりとりしてたらそこがボトルネックになっちゃってCPUに対して全然スケールしなかった。
こういうのは実際に手を動かしてみないと分からないことが多い。
追記 2016-04-21
コードはここ。ここに掲載したものから若干いじってある。
https://github.com/KeenS/100dices