[過去ﾛｸﾞ]
関数型プログラミング言語Haskell Part33 (1002ﾚｽ)
関数型プログラミング言語Haskell Part33 http://mevius.5ch.net/test/read.cgi/tech/1581326256/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
208: デフォルトの名無しさん [sage] 2020/04/13(月) 13:06:48 ID:pEw+DEbK タイムアウトのやつ この問題やってて ttps://www.codewars.com/kata/54d496788776e49e6b00052f/train/haskell 通らないコードがこれ 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で言うと値コピーしてソートしないでポインタでソートすると速いみたいな http://mevius.5ch.net/test/read.cgi/tech/1581326256/208
209: デフォルトの名無しさん [sage] 2020/04/13(月) 21:38:04 ID:tr0y4100 >>208 どう改善すればいいかはすぐにはわからないが prime_factors関数は末尾再帰ではない再帰をしているから容易にスペースリークしそうな感じはする http://mevius.5ch.net/test/read.cgi/tech/1581326256/209
211: デフォルトの名無しさん [sage] 2020/04/14(火) 01:34:33 >>208 prime_factorsだけど quotRem なら一回で両方得られる 探索は3から+2ずつ探すべき n が√m を超えてしまったら探索を打ち切るべき リストの整数全部に出てくる素因数を予めリストアップしたいんだろうけど そのprime_factorsだと絶対に素因数が存在しない、（２を除く）偶数空間と√mの後の空間をmに達するまで探していてとてもとても無駄 この無駄はmが大きいほど酷いことになるが、見事に君のコードはproductなんてしてmを巨大化させている 例えば、1000000 の素因数は少なくとも1000 以降は存在しないのに1001, 1002, 1003, ... , 999998, 999999, 1000000 まで探すところを想像してみて 一目気づいたのはそんなところかね。先ずはそこを直してから一局といったところか http://mevius.5ch.net/test/read.cgi/tech/1581326256/211
220: デフォルトの名無しさん [sage] 2020/04/16(木) 01:02:59 ID:6p+dWGIK >>208 計算速度や使用メモリ量以前に、解が正しくないよ。 試しに sumOfDivided [8] やってみ。 もう少し言うと、prime_factors 関数がおかしい。 関数名に相応しくない計算をしていられる。 まずは、必要な個数の正しい素数列を作ることを考えた方がいいと思うぞ。 http://mevius.5ch.net/test/read.cgi/tech/1581326256/220
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.036s