素数10億まで3秒 - ita’s diary
404 Blog Not Found: C - で素数を数え直したら、範囲10億で10秒切ったお むむ、以前自分が書いた奴だと、ホットスポットでやってる事はほとんど同じなのに30秒ほどだった。 for (p=2, 3, 5, 7, 11, ...) for(i=istart; i<size;i += p*2) pflag[i]=0; danさんの場合, 1bit でフラグを記憶してるのでメモリが1/8 で済む。そこでメモリアクセスの時間が効いてるんだろう。それならキャッシュに収まる位のブロックに計算を分割しその内側で素数pのループ回せばもっと速くなるかも？と思いやってみた。見事3秒で終わった! 以下コード danさんのbitmap.cに以下を追加 bitmap *bitmap_block(bitmap *parent, size_t offset, size_t size){ if (!s
in-place merge sort - 鍋あり谷あり
http://blog.livedoor.jp/dankogai/archives/50957658.html に 現代では一時メモリーを使わないin-place merge sortが開発されている と書いてある。そういえば、STLの stable_sort の計算量が O( N (log N)**2 )だったよなぁと思い、どうやったらそうなるのか調べてみたら http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html に実装があるのを発見した（いやその前にSTLのソースを見たんだが、とても読みにくかったので断念した）。 で。ソースから計算内容を理解し、ああなるほどそうするのかと思ってみた。 というわけで、どんな計算なのかを私なりに説明してみる： 左半分と右半分を整列する。 左半分と右半分をマージする。 こ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
