Haskell时间问题

这是关于haskell的第二个问题，我认为我的算法并不坏，它在C++和python中给出了更快的结果，并且haskell有一些问题，它不能给我10^25（也许它给出，但我不要等那么多），这个问题问我这个价值，请从现在开始指导我解决这个问题。Haskell时间问题

##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

代码是如此，但它那长，因为它是我的记忆系统，以缩短时间，但在Haskell其效率不高

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)

是代码

来源

2013-05-14 oknsnl

顺便说一句 - 如果您为顶级函数提供明确的类型签名，其他人就会更容易阅读您的Haskell代码。 – isturdy

我无法读取'f'的最后一个定义 - 在第一种情况下，它有两个参数'0'和'_'，但第二个参数'a'只有一个参数。 – applicative

我把_意外地放在：D – oknsnl

对于善良的第一种形式清理你的代码，以便人们可以阅读它。例如，重写snd (head ((a,res):x)) --> res。另一个建议：添加类型签名。
将您常见的子表达式（quot）提取到命名的let绑定中，以显着减少工作量。
记下您的电话以giveRes。这会给你带来最大的好处。如果您搜索SO [haskell] memo那么你应该得到很多好的结果。
不要使用列表作为一个集合来测试成员资格（search），后跟部分查找函数（send）。请考虑使用容器或无序容器库中的Map或HashMap。

来源

2013-05-15 01:44:56

+1'snd（head（（a，res）：x））'是真正有趣的，确实 – Ingo

Haskell时间问题

回答

相关问题