プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
700(4): 03/23(日)23:00 ID:pi1bImlR(1) AAS
>>680から1週間経ったので解答例を掲載
>>685を書いたときに作ってあった2つのC++プログラム
外部ﾘﾝｸ:ideone.com
外部ﾘﾝｸ:ideone.com
1番目ではsolve関数の再帰呼び出しの対象とするx[p]の下限と上限を線形探索するが、
2番目では二分探索する。要素数10では二分探索の効果は薄いと思いきや、大分速くなった。
2番目を読み返していたらバグを発見してしまった。i = N - 1のとき63行目のa[i + 1]はa[N]となり
省8
702(1): 03/25(火)15:25 ID:Yc/egiP0(1/3) AAS
>>699
> 実行時間はC++プログラムの数倍かかるようだが
rustc -C opt-level=2 でコンパイルしたら
g++ -O2 でコンパイルした ideone_KID2jR.cpp (>>700の一つめ) とほぼ同じ速度出たよ
703: 03/25(火)15:54 ID:GZ5kfx5g(1) AAS
>>702
データ精度を揃えたアルゴリズム比較のために
>>697-698をi128固定ではなくnum::BigIntにして計測して見ては？
あと出題者>>685は>>700の二つ目で(倍速以上に)短縮出来たと言っているよ
705(1): 03/25(火)17:30 ID:Yc/egiP0(3/3) AAS
>>697-698をBigIntに変えるのはどうしたらいいのか分かんなかったので
>>700の方を boost::multiprecision::cpp_int から boost::multiprecision::int128_t に変えてみた
改変版 | オリジナル
外部ﾘﾝｸ:ideone.com 0.12s | 外部ﾘﾝｸ:ideone.com 0.43s
外部ﾘﾝｸ:ideone.com 0.11s | 外部ﾘﾝｸ:ideone.com 0.23s
707: 03/25(火)23:43 ID:V/NXIH+S(1) AAS
>>704
>>699では最適化オプションを付けてrustc -O a.rsでコンパイルした。最適化なしでは
ありの4.6倍くらい掛かった。もしやと思ってコンパイラをアップデートしてみたら、
実行時間は約3分の1に激減し、>>700の1番目と大差ない1.3倍ほどに収まった。
Rustの古いコンパイラ（5年前のもの）がこんなに低性能だったとは…
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.038s