プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
700(4): デフォルトの名無しさん [] 03/23(日)23:00 ID:pi1bImlR(1)
>>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を使えば少し速くなる。
702(1): デフォルトの名無しさん [] 03/25(火)15:25 ID:Yc/egiP0(1/3)
>>699
> 実行時間はC++プログラムの数倍かかるようだが
rustc -C opt-level=2 でコンパイルしたら
g++ -O2 でコンパイルした ideone_KID2jR.cpp (>>700の一つめ) とほぼ同じ速度出たよ
703: デフォルトの名無しさん [sage] 03/25(火)15:54 ID:GZ5kfx5g(1)
>>702
データ精度を揃えたアルゴリズム比較のために
>>697-698をi128固定ではなくnum::BigIntにして計測して見ては？
あと出題者>>685は>>700の二つ目で(倍速以上に)短縮出来たと言っているよ
705(1): デフォルトの名無しさん [] 03/25(火)17:30 ID:Yc/egiP0(3/3)
>>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
707: デフォルトの名無しさん [] 03/25(火)23:43 ID:V/NXIH+S(1)
>>704
>>699では最適化オプションを付けてrustc -O a.rsでコンパイルした。最適化なしでは
ありの4.6倍くらい掛かった。もしやと思ってコンパイラをアップデートしてみたら、
実行時間は約3分の1に激減し、>>700の1番目と大差ない1.3倍ほどに収まった。
Rustの古いコンパイラ（5年前のもの）がこんなに低性能だったとは…
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.034s