プログラミングのお題スレ Part22 (831ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
282(16): ◆QZaw55cn4c 2024/02/24(土)14:25 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通りの組で三乗差が相等しい場合があるかも検討せよ
283(1): 2024/02/24(土)16:47 ID:KRWvIUHe(1) AAS
>>282
[(1134, 357), (1155, 504), (1246, 805), (2115, 2004), (4746, 4725)]
a^3 - b^3 == 1412774811
285(1): 2024/02/24(土)18:16 ID:O6Cw1j13(1) AAS
>>282 ruby
外部ﾘﾝｸ:ideone.com
・そのまま版
・5秒じゃ?
287(1): 2024/02/24(土)22:30 ID:mNVJyIZh(2/2) AAS
>>282
aが5000以下限定で>>283の解はRで5秒以内に求められた。8〜9行目は下三角行列の要素番号から
行番号と列番号を求めているだけで、>>282を解く特別なアルゴリズムというわけではない。
外部ﾘﾝｸ:ideone.com
288(2): 285 2024/02/25(日)08:52 ID:M1xmyD2F(1) AAS
>>282 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・285の無駄なループ回数を削減
・でも5秒じゃ?
289(1): 2024/02/25(日)21:06 ID:CUQUyFSy(1) AAS
>>282
>>287は下三角行列の要素番号から列番号を求めるのに2次方程式を解くのが分かりにくかったから、
各列の最下行の要素番号を計算しておいてそれを二分探索するように変更した。
外部ﾘﾝｸ:ideone.com
n = 25000で実行してみても、n = 5000ときの解のa, bを両方とも2, 3, 4, 5倍した解しか別に
見つからなかった。
290(2): 2024/02/26(月)22:18 ID:CjcYgBx5(1) AAS
>>282
>>289と似た手順でC++
外部ﾘﾝｸ:ideone.com
Rではソートする前に重複値だけを抽出しているが、C++のunique関数はソート済みデータにしか
使えないので使っていない。
291(1): 288 2024/02/27(火)21:45 ID:nu8aoj+0(1) AAS
>>282 c
外部ﾘﾝｸ:ideone.com
・288の移植
292(1): 2024/02/27(火)22:30 ID:BJV11H6M(1) AAS
>>282
下三角行列の各列内の要素は昇順で既に並んでいるのに、>>290は下三角行列の全要素を
ソートして無駄なので、列のマージに変更（要するにマージソートを途中段階から開始）
したら少し速くなった。
外部ﾘﾝｸ:ideone.com
n = 10000でも5秒以内に終わった。
外部ﾘﾝｸ:ideone.com
293: 288 2024/02/28(水)22:00 ID:7ZY4TL6q(1) AAS
>>282 c++
外部ﾘﾝｸ:ideone.com
・288の移植
>>282 rust
外部ﾘﾝｸ:ideone.com
・288の移植
294(1): 2024/02/28(水)23:21 ID:FCtvUtiC(1) AAS
>>282
>>292とは別の方法で>>290を高速化
外部ﾘﾝｸ:ideone.com
1³, 2³, 3³, …, 5000³をD = 5001で割った余りはすべて異なる値になるから、d = a³ − b³を
Dで割った余りはどれか1つの値に偏ることなく均等に分布する。dをDで割った余りによりdを
区分すれば、各区分に入る個数はどれも多すぎないのでソートに時間が余りかからない。
Dの値はconstexpr関数によりコンパイラに計算させている。n = 10000, 15000のときは
それぞれD = 10002, 15009になる。
295: 291 2024/02/29(木)22:20 ID:HlaTo1dC(1) AAS
>>282 c
外部ﾘﾝｸ:ideone.com
・291から省メモリ化
旧：unsigned int values[10];
新：unsinged short values[4];
296(4): 2024/03/01(金)22:22 ID:6k2oCbjk(1/3) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>294はa, bの二重ループ内でa³ − b³をD = 5001で割った余りrにより区分していたが、
rのループ内でa, bを変化させるように変更したら、2次元配列がなくなってすっきりした。
その結果、メモリ使用量が激減し、nが大きい場合でも実行できるようになった。
298(1): 2024/03/01(金)22:24 ID:6k2oCbjk(3/3) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>296のrのループ内でa³ − b³をD2 = 5003で割った余りr2により区分し、それぞれの区分ごとに
解を探すようにしたら速くなった。ただし、nが大きい場合にはかえって遅くなる。
300(1): 2024/03/03(日)22:19 ID:ZEDvt9uH(1) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>298でnを大きくするにつれ>>296に対する高速化効果が薄れていくのは、ABをvectorでなく
配列にしたらある程度改善された。n = 5000のときの実行時間は>>296の半分以下になった。
ただし、n = 1000000まで大きくすると、296よりやっぱり遅くなる。
>>299
どんなプログラムを書いたのか見せて。
301(3): 2024/03/06(水)22:35 ID:lIZep5aT(1) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>300の実行時間を分析すると、最も時間が掛かっているのは46〜と47行目だと判明した。
そこで配列ABの第1次元と第2次元を入れ替えてみると、n = 5000では変わらないが、
1万, 2万, 5万, 10万, 20万では35%前後高速になった。これは、改良前には第2次元の添字が
小さい要素に書き込みが集中しているため、改良後のように第1次元に入れ替えた方が
纏まったメモリ領域に書き込みが集中しキャッシュの効きが良くなるからだと考えられる。
一方、n = 100万で高速化しないのは、書き込み集中領域が大きすぎるからだろう。
外部ﾘﾝｸ:ideone.com
省5
303: 2024/03/09(土)22:13 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回しか
呼ばれないため、全体の実行時間への影響は無視できる。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 2.041s*