【モリタポ有償】C/C++の問題を片付けます(2)

[過去ﾛｸﾞ] 【モリタポ有償】C/C++の問題を片付けます(2) (1001ﾚｽ)
上下前次1-新
抽出解除ﾚｽ栞

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

582(3): 581 ◆QZaw55cn4c [qzaw55cn4c@a.email.ne.jp] 2011/04/27(水)03:11 AAS
そうですね。
>>564 の「あほなところの指摘」うんぬんについては主観も混じることでしょうし、明確な線引きはできないでしょうから、これは今回の引退条件からは除きましょうか。
（たとえば配列ですべてを処理して速度を上げるだけのコードを持ち出してきてくるのであれば、私サイドでは異議も申し立てるでしょうね。）

>>518 の「10倍以上の速度」については、codepad で一応の結果が出ますから、そこで判断しましょう。

>>518 の私の実装 >>549 について、codepad 上で反復させた結果は次のとおりです。
外部ﾘﾝｸ:codepad.org
私のコードでは 14回実行できます。

codepad で 100 回以上実行できるソースコードがあれば、このスレを閉じ、私は一介の名無しに戻ります。

591(4): 2011/04/27(水)04:49 AAS
codepadだとあんまり差がでないなぁ
外部ﾘﾝｸ:codepad.org

592(10): 581 ◆QZaw55cn4c [PhenomII x6 が放置状態‥‥] 2011/04/27(水)05:53 AAS
>>591
＞for(i = 2, max_len = 0; i * max_len < N; i++) {
を説明していただけませんでしょうか。
ベルトランの仮説（チェビシェフにより証明）を利用していると思われるんですが、
i から 2i の間に素数があっても、2i から 3i の間に素数があるかどうかはわかりません。

もっともここを
for (i = 2, i < N; i++)
にしてみたところで、
外部ﾘﾝｸ:codepad.org
爆速なんですけれども。（それか、codepad を速度判定に用いるのは精度がよくないですね。）
省3

599(4): 2011/04/27(水)06:58 AAS
>>592
横フォローだけど。
連続する素数の最初の数字が、今のところの最大の個数繰り返したとしても、最大数を超えるってことは吟味する意味がないってことかと。
そういう数学の証明とか仮説とかは苦手だけど、詳しいならもっと減らせるんでない？
最初の数字より大きいものしか続かないわけだから、i * max_len < N よりも少なくていいはず。

602(3): 2011/04/27(水)07:06 AAS
>>599
それに該当するのが
>for(j = i, k = sum = 0; k < max_len; j++) if(sieve[j]) sum += j, k++;
>if(sum >= N) break;
この部分

641(4): 2011/04/28(木)01:02 AAS
>>597
篩を差し替えて、さらに2倍ちょい
外部ﾘﾝｸ:codepad.org

672(4): 2011/04/29(金)04:44 AAS
>>516
和を再利用して、計算回数減らしてみた
篩のところの時間が大部分だから、ほとんど効果ないのがビミョー
#include <stdio.h>
#include <stdlib.h>
#define N 1000000

int main(void)
{
char sieve[N] = {0, 0, 1};
int i, j, k, head, tail, Ans, length, sum, tail_indx, sum_t;
省17

752(4): 2011/05/09(月)02:55 AAS
>>749 >>750
なるほど、確かにまだいい方法がありました。一度作った素数表を潰す発想はありませんでした。
お付き合いいただきありがとうございました。

>>518
>>549 の改良です。
外部ﾘﾝｸ:codepad.org

速度はそんなには速くなっていないようです。大きな配列をコピーする分だけ負担が大きいのかもしれません。
外部ﾘﾝｸ:codepad.org

756(6): ◆XEE2zLj0dE 2011/05/09(月)06:58 AAS
>>752
単にコードを貼ってもいいんだけど、意図も書いといてみる。

>>752の枠組みで改善していくとして。
こちらの環境で20回ループさせた時の速度内訳はこんな感じ。
　トータル 1.95sec
　素数テーブル作成(maketable) 1.37sec
　その後の処理 0.58sec
仕事であれば、maketableの改善を最優先するのが当然だけど、
スレの流れ的に不適当だと思い、その後の処理を対象にした。

ネックとなっている部分が、枝刈りの不十分さとfoundpにあると思われ、かつ
省15

761(4): 2011/05/09(月)14:23 AAS
QZaw55cn4cさん？のコードを多分１万倍くらい加速しました。
外部ﾘﾝｸ:codepad.org

764(4): 2011/05/09(月)15:13 AAS
>>672をちょっと改良

#include <stdio.h>
#include <stdlib.h>
#define N 1000000
int main(void)
{
char sieve[N] = {0, 0, 1};
int i, j, k, head, tail, Ans, length, sum, tail_indx, sum_t;
int *prime, prime_cnt, prime_max;
for(i = 3; i < N; i += 2) sieve[i] = 1;
省17

820(3): 2011/05/14(土)23:58 AAS
モリタポを対価として得る以上、一定の品質をクリアしなければならない義務が生じます。
（それがたとえネット上の軽いノリだったとしても）
その縛りを自らに課す点で、一概に「自分に甘い」と切り捨てることはできないと思います。

＞タダでやると他人に甘くなるからね
意味不明。この一節を説明できますか？

896(4): ◆QZaw55cn4c 2011/05/15(日)22:57 AAS
なんだか盛況ですね。これはいよいよ次スレをつくって楽しまなければw

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.062s