関数型プログラミング言語Haskell Part33

[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part33 (1002ﾚｽ)
上下前次1-新
抽出解除ﾚｽ栞

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

208(3): 2020/04/13(月)13:06 ID:pEw+DEbK(1) AAS
タイムアウトのやつ
この問題やってて
外部ﾘﾝｸ:www.codewars.com

通らないコードがこれ
sumOfDivided :: [Integer] -> [(Integer, Integer)]
sumOfDivided xs = map (\x -> (x,foldr (+) 0 (filter ((==0).(flip rem x) ) xs)) ) $ prime_factors ( product xs) 2
where
prime_factors 1 _ = []
prime_factors m n
| rem m n == 0 = n : (prime_factors (quot m n) $ n+1)
| otherwise = prime_factors m $ n+1

こういう感じでコード組み立てるんだけど、他の問題でもしょっちゅうタイムアウト起こしてる
応答の速いコードにするにはどんなふうに変えていけばいいかを知りたい
cで言うと値コピーしてソートしないでポインタでソートすると速いみたいな

209: 2020/04/13(月)21:38 ID:tr0y4100(2/2) AAS
>>208
どう改善すればいいかはすぐにはわからないが
prime_factors関数は末尾再帰ではない再帰をしているから容易にスペースリークしそうな感じはする

211(1): 2020/04/14(火)01:34 AAS
>>208
prime_factorsだけど
quotRem なら一回で両方得られる
探索は3から+2ずつ探すべき
n　が√m を超えてしまったら探索を打ち切るべき

リストの整数全部に出てくる素因数を予めリストアップしたいんだろうけど
そのprime_factorsだと絶対に素因数が存在しない、（２を除く）偶数空間と√mの後の空間をmに達するまで探していてとてもとても無駄
この無駄はmが大きいほど酷いことになるが、見事に君のコードはproductなんてしてmを巨大化させている
例えば、1000000 の素因数は少なくとも1000 以降は存在しないのに1001, 1002, 1003, ... , 999998, 999999, 1000000 まで探すところを想像してみて

一目気づいたのはそんなところかね。先ずはそこを直してから一局といったところか

220: 2020/04/16(木)01:02 ID:6p+dWGIK(1) AAS
>>208
計算速度や使用メモリ量以前に、解が正しくないよ。
試しに sumOfDivided [8] やってみ。

もう少し言うと、prime_factors 関数がおかしい。
関数名に相応しくない計算をしていられる。

まずは、必要な個数の正しい素数列を作ることを考えた方がいいと思うぞ。

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.044s