プレゼン (差し替えました！が、まだ字が切れてる...再差し替え予定)


実験中動画


バルーン+照明の連動


バルーン同士別個で動く


twitterの反応

第二回　プログラムコンテスト企画　1000万個目の素数を超高速に出力せよ

どもまたまたやってきました。プログラムコンテスト企画、第二弾！
すごく盛り上がりましたので、またその内容をお伝えしたいと思います。

今回のルールは
「2」を1個目として、1000万個目の素数を出してください。
その値の正確さと出力までの処理時間で競い合います
環境：eclipseをインストールしただけのさらのＰＣです。
3時間以内でプログラムを完成させます。

素数とは、1とその数自身以外に正の約数がない
（つまり1とその数以外のどんな自然数によっても
割り切れない）、1 より大きな自然数のこと
（例） 2 3 5 7 11 13 17 ・・・
by wikipedia

例えば、素数判定アルゴリズムってどんなのがあるの？
「エラトステネスの篩（ふるい）」
がありますね。


参加者は社内のプログラマー11人です。
皆真剣にプログラムしてますね。



終わった後は・・・
ほかの人たちのプログラミングを拝見中！



結果測定中です。全員活目せよっ



懇親会　疲れた、、　本当にお疲れさまでした







**************
表彰式です
**************

1位　な、なんとっ　１秒４３　chkfjさんでした


彼はまだ学生、、すげー奴が現れたぞ！
前回のリベンジおめでと！あ、おめでてー研出身だ。

2位　これもすごいっ　7秒　nazokingさんでした
前回も2位。本物の実力見せつけますね。さすがです。

3位　うーん皆やるねぇ　38秒でyatoさんでした
前回は結果出ませんでしたが、リベンジおめでとーございます。
さすがアルゴリズム強いですね。


それではそれぞれのアルゴリズムについて、各人のコメントご紹介します。
1位　chkfjさん
「大学の授業でエラトステネスの篩をCで実装したことがあったので、
1000万個目の素数を出すのはすぐにできました。
さらに偶数を無視してみると6.8sになりました。
もっと速くなる方法がないものか検索していたら、
エロい人が書いたコードが落ちており、実行したら1.4sでした……
その後は確率的アルゴリズムを使った方法を試したりしましたが、
1000万個すべてを計算するには向いてないようで、
速度はそれほどでもありませんでした。
最後はインラインアセンブラを使ったコードを探していました。 」

2位 nazokingさん
「エラトステネスのふるいを忠実に実装しました。
やってる内に繰り返しやってることがあることに気づいて、
そこをつぶしていきました。
ふるいにかける配列にchar型配列を使おうとして
ヒープがあふれたので、BitSetをつかいました。
最後はBitSetを高速化しようとしてはまりました。
実際出来てもそんなに高速にならなかったと思います。
あらかじめググっておいて目標の数値以上は配列を
作らないようにしたのですが、もっと手を抜けたらしいです。 」

3位 yatoさん
「- スピード勝負なので残念ながら Perl はお蔵入り。
当然 C 言語が圧倒的に有利。わかってる。
でも Java でアルゴリズムを工夫して C 言語を打倒したい!
- でも「エラトステネスのふるい」と本質的に異なる、劇的に速い方法というのは確かなかったはず。
- というわけで「ふるい」を使いつつ、「boolean の配列としてビット配列を使い、
ビット配列を int でコピーすることによる高速化」を狙う。
- …だけど結局それに関してあまりいい方法が思いつかなかった（また企画倒れ orz ）。
- 結局、次のようなことを行った。
2～13 の素数に関して「ふるい」を実施した後の結果は P = 2・3・5・7・11・13 の周期をもった列となる。
従って、これを(int の操作で)コピーすることで2～13の処理を高速化できる。
ただし、int の配列として周期的になるように、実際には周期を 16・P とする。
- これだと 2～13 に関する計算の部分にしか効かないのであまり効果がなさそう。
- 特殊な操作が必要だから、ビット配列は自前実装にする。
- メインのクラスだけで、全部 static。
- 実行した結果、所要時間は 2 分。残念。
どうも Java がビット配列をあまり上手く扱えていないみたい。
- ダメ元でビット配列を扱うコードの
set[n / 32] |= (1 << (n % 32));
を
set[n >> 5] |= (1 << n);
に変えてみた。
下の式で、右辺の n には Java の言語仕様上自動的にビットマスクがかかる。
だから上と下は自明に同値だから、当然実行時最適化により、どちらを書いても同じ。
- と思ったら、何と下に変えたら 50 秒に縮まった。実行時最適化を信用してはいけない?
- 今考えたら、n は signed だから上と下は同じでなかった (+_+)
- 普通に boolean 配列を使った方が速いはずなので、そちらに書き直そうかとも考えたけど、
でもそれって「全く全然何の工夫のかけらもないプログラム」なので物凄くやる気が起こらないんだよなあ。
- ということで終了。
- ………、あれっ、これで3位なの!?
- 感想：スピード勝負の場合はやっぱり C 言語だね! 」


さあ次回はどんなお題にしましょうか？
リベンジ待ってますよー
もし社外から参加したいという希望者の方がいらっしゃったらぜひ声かけてください！！
チームラボのイベントの実況などtwitterで行ってます。
twitter teamlab_tech

@todesking が講師をしてくれたGit勉強会の録画を公開します。



途中でUstが切れて、ファイルが2つに別れています。
冒頭3分ぐらい

本編50分ぐらい（最初の3-4分後、音が大きくなります）

ドラッカーの本によると、ある時ヨーロッパの金銀細工士は気が付いた。



世間のみんなが持っている金銀を預かって、そのうちを8割くらい人に貸し、貸した分をまた自分たち金銀細工士に預け、それをまた、2割だけ残して、8割を貸す、これを繰り返す。



すると、金銀細工士の帳簿の上では、金銀が5倍に膨らむし、世間が金銀細工士に預けた金銀の量は5倍に増える。

どういう計算かというと、

1 + 0.8 + 0.8×0.8 + 0.8×0.8×0.8 + 0.8×0.8×0.8×0.8 + 0.8×0.8×0.8×0.8×0.8 + 0.8×0.8×0.8×0.8×0.8×0.8 + ...

= 1+0.8+0.64+0.512+0.4096+0.32768 + .... = 5 だからだ。



そうやって銀行が成立した。(注 : うろ覚えなので0.8と言う数は違うかも。)



この話はバグの収束の話にも使える。1日目にバグを100個みつけ、2日目に80個みつけ、3日目に64個みつけ、という具合に1日ごとに前日の8割のバグが見つかるような場合、結局全体でいくらのバグが見つかるかを考えると、100の5倍で500個だ。

なお、上のような計算は等比級数として知られている。たぶん高校で習ったはず。



1+R+R^2 + R^3 + .... + R^k = (1 - R^(k+1) ) / ( 1 - R )



上記の場合は、R = 0.2 を代入する。(そして k→∞としてR^(k+1)→0とする。)



他の例として、 R = 0.5 だと 2倍、R=0.9 だと 10倍になる。

先日941さんとライブドア社長である出澤様がいらっしゃいました。
2時間ほどラボの隅々を写真に収めて帰っていただきました。

941さんのブログにチームラボの紹介が掲載されましたけど、
ヤバイです。941さん的にはバイヤーです！
どのチームラボの紹介記事よりたくさん写真が載っていて、よく社内の様子や作ったものが
わかりますので、ぜひぜひご覧ください。

ブログはこちらから


下記では今後のチームラボのイベントや勉強会についてどんどん発言していこうと思いますので
よろしくお願いいたします。
twitter teamlab_tech