プログラミングのお題スレ Part22 (858ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
301(3): デフォルトの名無しさん [] 2024/03/06(水) 22:35:52.23 ID:lIZep5aT(1) AAS
>>282282(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の実行時間を分析すると、最も時間が掛かっているのは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より25%速くなった。
(原理的には>>300より非効率なのでn = 5000では>>300より当然遅い)
302: デフォルトの名無しさん [sage] 2024/03/08(金) 19:02:53.21 ID:oHHhAfhn(1) AAS
>>301
ハズレが多いから2passは効果ある？
303: デフォルトの名無しさん [] 2024/03/09(土) 22:13:47.64 ID:C74EWG6S(1/2) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
関数mainのループで配列A, B, Pに書き込まずdにだけ書き込むようにし、関数FindDuplicatesで
dの添字Pではなくdそのものをソートするように変えて、n = 1000000の場合に>>301より10%高速化。
関数PrintSolutionでa, bをmainでと同じ方法で再計算するのは非効率だが、PrintSolutionは僅か12回しか
呼ばれないため、全体の実行時間への影響は無視できる。
309(1): デフォルトの名無しさん [sage] 2024/03/10(日) 20:08:55.20 ID:6qxPF4Wx(1) AAS
2pass案は多少工夫したらかなり速い
n ␣␣m ␣296␣ ␣301-1 ␣301-2 ␣303␣ ␣2pass
5k␣␣5 ␣ 0.5s ␣ 0.1s ␣ 0.5s ␣ 0.4s ␣ 0.1s
25k ␣5 ␣12.7s ␣ 2.5s ␣13.9s ␣11.1s ␣ 1.7s
100k␣5 ␣3m52s ␣49.3s ␣4m13s ␣3m26s ␣38.9s
1M* ␣6 ␣8h23m ␣2h50m ␣8h51m ␣6h43m ␣1h11m
*n=100万は1万サンプルの部分ループ500k≦r＜510kから100倍
>>301の296と301-2の比較記述と違う傾向があるのはキャッシュ階層の違いだと思う
2passは301-1に近いけど1pass目でのランダムアクセスサイズを落としながらも
誤判定率を低く抑える(0.2%～2%)工夫をするのがお楽しみだと思う
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.635s*