プログラミングのお題スレ Part22 (857ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
301(3): デフォルトの名無しさん [] 2024/03/06(水) 22:35:52.23 ID:lIZep5aT(1) AAS
>>282
282(16): ◆QZaw55cn4c [sage] 2024/02/24(土) 14:25:41.40 ID:NZEL8Kud(1) AAS
異なる自然数 a, b (a > b) における a^3 - b^3 を「a, b の三乗差」と呼ぶことにする。
異なる5通りの組(a, b) (c, d) ... (j, k) について三乗差がすべて相等しいとき
その組(a, b)...(j, k) および三乗差自体を求めよ
異なる6通りの組で三乗差が相等しい場合があるかも検討せよ
C++
外部ﾘﾝｸ:ideone.com
>>300
300(1): デフォルトの名無しさん [] 2024/03/03(日) 22:19:54.92 ID:ZEDvt9uH(1) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com

>>298でnを大きくするにつれ>>296に対する高速化効果が薄れていくのは、ABをvectorでなく
配列にしたらある程度改善された。n = 5000のときの実行時間は>>296の半分以下になった。
ただし、n = 1000000まで大きくすると、296よりやっぱり遅くなる。

>>299
どんなプログラムを書いたのか見せて。
の実行時間を分析すると、最も時間が掛かっているのは46〜と47行目だと判明した。
そこで配列ABの第1次元と第2次元を入れ替えてみると、n = 5000では変わらないが、
1万, 2万, 5万, 10万, 20万では35%前後高速になった。これは、改良前には第2次元の添字が
小さい要素に書き込みが集中しているため、改良後のように第1次元に入れ替えた方が
纏まったメモリ領域に書き込みが集中しキャッシュの効きが良くなるからだと考えられる。
一方、n = 100万で高速化しないのは、書き込み集中領域が大きすぎるからだろう。

外部ﾘﾝｸ:ideone.com
n = 100万の場合にはr2の値によってデータを多数の列へ振り分けるのをやめ、列を1つにして、
その内部でr2の値により2種類に区分し、それぞれの内部で2種類にさらに区分し、…と再帰的に
区分していけば（要するにクイックソートの変形版）、1つの配列内での要素のスワップだけで済み、
キャッシュの効きが改善されるとの予想通り、n = 100万で実行速度は>>296
296(4): デフォルトの名無しさん [] 2024/03/01(金) 22:22:26.10 ID:6k2oCbjk(1/3) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>294はa, bの二重ループ内でa³ − b³をD = 5001で割った余りrにより区分していたが、
rのループ内でa, bを変化させるように変更したら、2次元配列がなくなってすっきりした。
その結果、メモリ使用量が激減し、nが大きい場合でも実行できるようになった。
より25%速くなった。
(原理的には>>300より非効率なのでn = 5000では>>300より当然遅い)
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.033s