第二回 プログラムコンテスト企画 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
[カテゴリー:技術の最新記事10件]
どもまたまたやってきました。プログラムコンテスト企画、第二弾！
すごく盛り上がりましたので、またその内容をお伝えしたいと思います。
今回のルールは
「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
|
<<前のアイテムを見る!
初心者向けGit社内勉強会 録画公開します
|
次のアイテムを見る!!>>
2/6 Gadget1でプレゼンした チームラボボールの動画をアップしました！(インタラクティブボール・インタラクティブバルーン)
|