プログラミングのお題スレ Part22 (863ﾚｽ)
プログラミングのお題スレ Part22 http://mevius.5ch.net/test/read.cgi/tech/1691038333/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
700: デフォルトの名無しさん [] 2025/03/23(日) 23:00:51.13 ID:pi1bImlR >>680から1週間経ったので解答例を掲載 >>685を書いたときに作ってあった2つのC++プログラム https://ideone.com/KID2jR https://ideone.com/ysdd6b 1番目ではsolve関数の再帰呼び出しの対象とするx[p]の下限と上限を線形探索するが、 2番目では二分探索する。要素数10では二分探索の効果は薄いと思いきや、大分速くなった。 2番目を読み返していたらバグを発見してしまった。i = N - 1のとき63行目のa[i + 1]はa[N]となり 配列の添字範囲外アクセス。0との比較だけだし、if文の評価がどっちでも以降の処理は結局同じだから、 実害も解への影響もないが、厳格さが必要ならif ((i + 1 < N ? a[i + 1] : 0) >= 0) {と書き換えるべきだな。 実行時間への影響は無視できる。 それぞれのPowerShellへの移植版 https://ideone.com/vEGZ3D https://ideone.com/azzMa4 完全な逐語訳ではなく、PowerShellで書くと遅くなったり煩雑になったりする箇所は適宜改変した。 15桁以下の場合は64ビット整数でも桁溢れしないので、BigIntの代わりにInt64を使えば少し速くなる。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/700
702: デフォルトの名無しさん [] 2025/03/25(火) 15:25:56.57 ID:Yc/egiP0 >>699 > 実行時間はC++プログラムの数倍かかるようだが rustc -C opt-level=2 でコンパイルしたら g++ -O2 でコンパイルした ideone_KID2jR.cpp (>>700の一つめ) とほぼ同じ速度出たよ http://mevius.5ch.net/test/read.cgi/tech/1691038333/702
703: デフォルトの名無しさん [sage] 2025/03/25(火) 15:54:47.24 ID:GZ5kfx5g >>702 データ精度を揃えたアルゴリズム比較のために >>697-698をi128固定ではなくnum::BigIntにして計測して見ては？ あと出題者>>685は>>700の二つ目で(倍速以上に)短縮出来たと言っているよ http://mevius.5ch.net/test/read.cgi/tech/1691038333/703
705: デフォルトの名無しさん [] 2025/03/25(火) 17:30:47.40 ID:Yc/egiP0 >>697-698をBigIntに変えるのはどうしたらいいのか分かんなかったので >>700の方を boost::multiprecision::cpp_int から boost::multiprecision::int128_t に変えてみた 改変版 | オリジナル https://ideone.com/Ie0HhO 0.12s | https://ideone.com/KID2jR 0.43s https://ideone.com/np3p5h 0.11s | https://ideone.com/ysdd6b 0.23s http://mevius.5ch.net/test/read.cgi/tech/1691038333/705
707: デフォルトの名無しさん [] 2025/03/25(火) 23:43:24.86 ID:V/NXIH+S >>704 >>699では最適化オプションを付けてrustc -O a.rsでコンパイルした。最適化なしでは ありの4.6倍くらい掛かった。もしやと思ってコンパイラをアップデートしてみたら、 実行時間は約3分の1に激減し、>>700の1番目と大差ない1.3倍ほどに収まった。 Rustの古いコンパイラ（5年前のもの）がこんなに低性能だったとは… http://mevius.5ch.net/test/read.cgi/tech/1691038333/707
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.025s