0

それはhaskellに関する私の2番目の質問であり、私のアルゴリズムは悪くないと思いました.C ++とPythonでより速い結果が得られます.haskellには10 ^ 25を与えることができない問題があります(多分それは与えますが、私はそれほど待ちません)そしてこの質問は私にその価値を尋ねます、今からこの男のおかげで修正するように私を導いてください。

##Euler 169##
giveRes 0 _= 1
giveRes 1 _= 1
giveRes a x = if search a x
                then send a x
                else let res = if rem a 2 == 0
                                  then (giveRes (quot a 2) x)
                                        +
                                       (giveRes (quot a 2-1) x)
                                  else giveRes (quot a 2) x
                     in snd (head ((a,res):x))
search _ [] = False
search a (x:xs) = if a == fst x then True else search a xs
send a (x:xs) = if a == fst x then snd x else send a xs

コードはそれですが、時間を短縮するための私の記憶システムであるため、それだけ長いですが、haskeでは効率的ではありません

f 0 _ = 1
f a = if rem a 2 == 0
         then giveRes (quot a 2) + giveRes (quot a 2-1)
         else giveRes (quot a 2)

そのコードの最初の形式です

4

1 に答える 1

9
  1. 念のため、コードをクリーンアップして、人々が読めるようにします。たとえば、 を書き換えsnd (head ((a,res):x)) --> resます。別の提案: 型シグネチャを追加します。
  2. 共通部分式 ( quot) を名前付き let バインディングに抽出して、作業を大幅に削減します。
  3. GiveRes への呼び出しをメモします。これにより、最大のメリットが得られます。SO を検索する[haskell] memoと、多くの良い結果が得られるはずです。
  4. メンバーシップをテストするためのセットとしてリストを使用しないでください ( search)。その後にルックアップ用の部分関数を続けます ( send)。代わりに、コンテナ ライブラリまたは unordered-containers ライブラリのMapまたはを使用することを検討してください。HashMap
于 2013-05-15T01:44:56.190 に答える