サイコロで同じ目が100回連続で実際に出るか

動機

とあるスレでこの問に対してプログラムで試せばいいというレスがあったので試してみた。

結論

単純にスペックが足りないというなんの面白みもない結果。
とはいえプログラミング的にいろいろ楽しかったのでまあ良い。

サイコロを振り続けるプログラム

試行１：PHP

一番使い慣れたPHPで書いてみる。

<?php
date_default_timezone_set('UTC+9');
set_time_limit(0);

$out = gmp_init(0);
$num = array();
$index = 0;
for($i=1 ; $i<101;$i++){
    $num[$i] = gmp_init(0);
}

while(true) {
    START:
    $out = gmp_add($out, 1);
    $base = mt_rand(1, 6);
    if($index == 10000){
        export($num,$out);
        $index = 0;
    }else{
        $index++;
    }

    for ($i = 0; $i < 100;) {
        $i++;
        $eye = mt_rand(1,6);
        if($base != $eye){
            $err = gmp_strval($out)."回目の挑戦は".$i. "回目で失敗"."\n\n";
            echo mb_convert_encoding($err,"SJIS");
            $num[$i] = gmp_add($num[$i],1);
            goto START;
        }
    }
    $tr =  "やったよ！！".gmp_strval($out)."回目でついに成功したよ！！"."\n"."ラッキーナンバーは：".$base."！！";
    echo mb_convert_encoding($tr,"SJIS");

    $str = "";
    foreach($num as $key=>$value){
        $str .= $key.",".gmp_strval($value)."\n";
    }
    $file = "dice_".date('YmdHis').".csv";
    file_put_contents($file,$str);
    break;
}

function export($arr,$num){
    $str = "";
    foreach($arr as $key=>$value){
        $str .= $key.",".gmp_strval($value)."\n";
    }
    $file = "dice_".date('YmdHis')."_". gmp_strval(gmp_div($num,10000)) .".csv";
    file_put_contents($file,$str);
}
?>

無駄な処理が多い？言い訳をさせて欲しい。
あ、そもそもGOTOを使うなという議論は無しでおなしゃす、一回使ってみたかったんですこれ以外思いつかなかったんです。
まずこれのファイルをどこで実行するかという問題があって、ConoHaのVPS(2Gプラン)じゃ絶対メモリ足りないなと。かと言ってWindows上でApache実行するのもめんどくさいなと。そこで出会ったのが下の記事です。

PHP7をEXEにコンパイルする方法

非常に便利、もう手放せない。しかしこれで実行するとcmd上で実行することになり、文字化けするのでそのためのmb_convert_encoding。いやまあiniから文字コード設定しろよって話なんですけどね。
あとは一応後で解析しようと思って（数学科の友人の要請もあり）、試行回数と連続回数をファイルに出力していたのでそのへんの処理が多いかな。

結果

遅い。なんというか、cmd上で流れてる文字列を見る限りくっそ速いけど試行回数的に見るとくっそ遅い。今見たら無駄な処理多すぎるし当然っちゃ当然。

試行２：Ruby

うちの大学は今年からRubyで教育すると聞いたので手を出してみた。

require 'bigdecimal'
require 'bigdecimal/util'

  class MAIN

    random = Random.new
    outside = BigDecimal("0")
    num = Array.new(100,BigDecimal("0"))
    _1 = BigDecimal("1")

    while(true) do
      base = random.rand(1..6)
      outside = outside + _1

      for inside  in (1..100) do
        eye = random.rand(1..6)
        if base != eye then
          printf "#{outside.to_s("F")}回目の挑戦は#{inside}回目の試行で失敗しました。"
          num[inside] = num[inside] + _1
        end
      end
    end
  end

Ruby処女作なのでこれがプログラム的にどうかもわからない。

結論

動かなかったです。Bigdecimal同士の足し算ができなかったような気がする。正直サイコロを振る以前の問題だった。

試行３：C++

これが一番速いのでは？という思いつき。三年ぶりぐらいにC系統触った。
まずは巨大整数を扱うgmpの導入から…と思ったけど早速つまずいた。
1. MPIR(2.7.2)をダウンロードし、build.vc14のmpir.slnを開いてdll_mpir_gcをビルド
2. VS2015のプロジェクトのプロパティからV/C++ディレクトリのインクルードディレクトリにgmp.hやgmpxx.h、mpir.dllなどがあるフォルダパスを追加
3. C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\binにvsyasm.exeを追加、\libにmpir.libとmpir.pdbをコピー
4. プロジェクトのプロパティ、リンカーの入力の追加の依存ファイルにmpir.libを追加
して

#include "stdafx.h"
#include <iostream>
#include "gmpxx.h"

int main() {
    mpz_class a = 0 ,b = 1;
    a = a + b;
    std::string c = a.get_str();
    std::cout << c;

    return 0;
}

すると警告を吐いてビルドできない。
ここで詰まって二、三日放置していたが、そもそも任意精度演算が必要な回数までサイコロを振るのに何年かかるのかということに思い当たり普通にintでいいやとなった。（後日警告は無視できると教えていただいた。）
というわけで組んでみたのが下

#include "stdafx.h"
#include <iostream>
#include <random>
#include <fstream>
#include <string>

int main() {
    std::random_device rnd;
    std::mt19937 mt(rnd());
    std::uniform_int_distribution<> rand6(1, 6);

    int out = 0;
    int index = 0;
    std::string str;
    int first = 0;
    int eye = 0;

    std::string filename = "stats.csv";
    std::ofstream file;

    while (true) {
        start:

        out++;
        std::cout << out << std::endl;
        first = rand6(mt);
        str += std::to_string(first);
        str += ",";

        if (index == 9999) {
            file.open(filename, std::ios::out | std::ios::app);
            file << str;
            file.close();

            str = "";
            index = 0;
        }
        else {
            index++;
        }

        for (int i = 0; i < 100; i++) {
            eye = rand6(mt);
            str += std::to_string(eye);
            str += ",";
            if (first != eye) {
                str += "\n";

                goto start;
            }
        }
        break;
    }
}

randのところは下を参考にした。

C++11 乱数 std::random 入門

簡単に言えばPHPの移植である。Cを触っていたことはあれどC++はほぼ初挑戦だったので、学ぶことは非常に多かった。とても勉強になった。Rubyとの差はどこで生まれたのか。

結論

PHPよりはましになったが依然として遅い。あと一つのファイルに出力したから余裕の10億行超えで開けない。

試行４：マルチスレッド

試行３のC++は、１コアしか使っていない。せっかく４コアあるのにもったいないにゃあということで、マルチスレッド化した。

#include "stdafx.h"
#include <iostream>
#include <thread>
#include <vector>
#include <random>
#include <fstream>
#include <string>

void worker(int num) {
    int out = 0;
    int index = 0;
    std::string str;
    int first = 0;
    int eye = 0;
    int flag = 0;

    std::random_device rnd;
    std::mt19937 mt(rnd());
    std::uniform_int_distribution<> rand6(1, 6);

    std::ofstream file;

    while (true) {
    start:
        if (index == 9999) {

            std::string filename = "stats";
            filename += std::to_string(num);
            filename += "_";
            filename += std::to_string(flag);
            filename += ".csv";

            file.open(filename, std::ios::out);
            file << str;
            file.close();

            str = "";
            index = 0;
            flag++;
        }
        else {
            index++;
        }

        out++;
        first = rand6(mt);
        str += std::to_string(first);
        str += ",";

        for (int i = 0; i < 100; i++) {
            eye = rand6(mt);
            str += std::to_string(eye);
            str += ",";
            if (first != eye) {
                str += "\n";

                goto start;
            }
        }
        break;
    }
}

int main()
{
    int thread = std::thread::hardware_concurrency();
    std::vector<std::thread> ths(thread);
    int i = 0;

    for (auto& th : ths) {
        i++;
        th = std::thread(worker,i);
    }

    for (auto& th : ths) {
        th.join();
    }

    getchar();
    return 0;
}

これでできるの！？って感じだった。最適化とかできるのかもしれないけどまあ、今回はこんなところで十分でしょう。この頃にはすでに100回連続出るかという目的を忘れて、とりあえずたくさんサイコロを振るということしか考えていない。

結論

とても早かった。10億試行に15分ぐらい。出た目をすべて記録したとはいえ、ファイルを小分けにしたので開けないということは無かった。それでも7GBぐらいのデータ量にはなった。

データを解析する

データは集まったので解析しなければならない。

どういう形にするか

僕にはこのデータの扱い方がさっぱりわからなかったので、先ほどの友人に尋ねたところ、何回連続が何試行目までに何回起きたみたいなデータが欲しいと言われた。
データは下のように保存していた。

5,4
6,3,
6,6,6,5,
1,4,
4,4,5

あ、ここからは基本PHPオンリーでいきます。
まずはこれを回数に直そうとした。上記の例なら、上から順に0,0,2,0,1回というふうに。要は(文字数-6)/2ですね。ここで懲りずに一つのファイルに纏めてしまいました。
そのプログラムは超絶簡単なので略。
階段グラフにする予定だったので、まあデータ解析といえばRだよねと思って挑戦→ファイルがおもすぎて開けない。

とりあえずプロットできる形式にしようねということで、目標は以下の形式

1,0,
2,0,
3,1,
4,1,
5,1,
6,2,
7,3,

これも簡単ですね、行数とインクリメントを組み合わせるだけです。しかしまあいかんせん10億行あったので、ファイルI/Oが問題になりました。最初はfile_put_contentsを使っていたのですがこれいちいちファイル閉じて開いてするからとても重たい。だから結局手動でfopenとfcloseでした。あと上記の形式だとファイルサイズが膨大になったので、結果以下の形式に落ち着きました。