素数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
Post by @shyouhei
とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、
Duff's device - Wikipedia
Duff's Device（ダフスデバイス）とは、C言語での可変長の連続的コピーをループ展開により最適化実装するときに直面する端数の問題を解決するための手法である。 C言語のswitch-case文が持つフォールスルーを利用して、アセンブリ言語で行われる技巧をC言語で実現している。1983年11月、ルーカスフィルムで働いていたトム・ダフが発見した。 ループ展開は、ループのための分岐回数を減らす技法である。指定されるループ回数が不明な場合、ループ展開すると回数が合わない場合が出てくるので、ループの途中にジャンプすることで調整する。例えば、8回ぶんのループを展開した場合、指定されたループ回数が8で割り切れないなら、その回数を8で割った剰余のぶんだけ処理を実行する位置にジャンプさせる。 ダフはそのような最適化を検討していてCでの技法を発見した。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
