モンキーはシェイクスピアになる夢を見る

昨日に書いた「モンキーはシェイクスピアになりうるか」で、モンキーがシェイクスピアになるには無限不可能性ドライブよりも通常進化を行ったほうが確実で幾分も早いということが予想できた。

それどころか、いくらランダムにコンピュータに計算されたところで「42」と言われるのが落ちに決定している。

ということでもう一度挑戦してみることにした。

asin:4102020039asin:4396113498asin:4826901771asin:4272420097asin:4309462553

====
まず昨日に書いたPythonのシングルスレッドのコードを現在もぶん回しているが、自前のPCより幾分も遅いVPS環境のためかまだMONKEYは発見されていない。24時間経過してもまだダメだ。宝くじは当たらない。

昨日のPythonコードはリストをジョインして文字列を起こすなど結構無駄な処理が入っているので、少しでも時間的資源とコンピュータリソースを開放するためにC言語のバージョンも書いた。

C言語は10年以上書いていないので全くわからず、乱数の発生どころか文字列を返す方法すら調べなければわからなかったほどだ。Python便利、超便利。

ということで、C言語で書いたバージョンがこちら。

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

const char* TEXT = "MONKEY";

const char* CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()_+|-=\\{}[];:\'\"";

void match(int len, int chars_len){
    char rand_text[7];

    for(int i = 0; i < len; i++){
        rand_text[i] = CHARS[rand()%chars_len];
    }

    if (strcmp(TEXT, rand_text) == 0) {
        printf("match!!\n");
        printf("%s", rand_text);
        exit(1);
    }
}

int main(void){
    int len = strlen(TEXT);
    int chars_len = strlen(CHARS);

    while(1){
        match(len, chars_len);
    }
}

 かなり効率が悪いコードかも知れないが、だがコレでもPythonの何十倍も早い。

実際にコードにカウンタを持たせてベンチマークを取ってみると、while()を1000万回回すのにコレほどの時間差が存在する。

言語

時間(3回平均)

gcc 4.8 -O3

0.71秒

gcc 5.1 -O3

0.66秒

Python 2.7.6

30.25秒

Python 3.4.0

68.11秒

やはりC言語は素晴らしい。たまにC言語を書くとその便利さが実感できる。いや、それよりも昨今のコンピュータが早すぎる。

Python3.4がPython2.7と比べて倍以上遅くなっているのが気になる。コレもそのうち調べてみよう。

そしてこのコードも昨晩にぶん回しておいたのだが(VPSが3コアなので2コアはMONKEYを見つけるためにぶん回していた)、朝起きてみるとなんとMONKEYが発見されていた。

$ time ./a.out
match!!
MONKEY
real    260m5.455s
user    259m48.098s
sys     0m9.239s

VPSなので自前のPCよりは何倍も遅いが、それでも約4時間。ということは、自前のPCで回せば1時間もかからないだろう。

どれくらいの回転でマッチしたのか表示させていなかったことが後悔されるが、rand()で乱数を発生させているのでみなさんもお試しあれ。

是非MONKEYの発見を目の前で確認したい。

ということでもう一度ぶん回そうと思ったのだが、1時間もPCをぶん回していたら爆発するかも知れない。折角4コアHTもあるのだから、是非8スレッドでぶん回して10分以内に確認したい。

ということで、OpenMPとOpenACCを試みた。本当はCUDAを使って計算させたかったのだが、CUDAを1時間ほど調べてみると理解するまでにシェイクスピアが写経出来るという結論を得てOpenACCで妥協した。

だがOpenACCとなると、GCCでは5.1にならないと使えない。UbuntuLinux 14.04の私はGCC4.8なので、GCC5.1をビルドして使わなければならない。

[image:id=386]

ということでビルドした。まぁ先に書いておくと、「make -j8」としてもビルドには1時間以上かかるので、確認が目的であれば素直にシングルスレッドでぶん回したほうが早いだろう。

ということで、OpenMPとOpenACCでどれほどの時間差が出るか実験。しようと思ったのだが、なんせOpenMPもOpenACCも使ったことがないので結局CUDAと同じように並列化やGPGPUの知識が必要だ。

ということで今回もコレはスキップした。

だがVPSで回した実験で、やはり時間をかければMONKEYはシェイクスピアの夢を見ることがわかった。

確率論としては確実に存在する些細なことであるが、それを実験して実証するのはやはり意味が有る。これからもそんな無駄なことをしていこう。