哈斯克尔时间问题

Question

这是我关于haskell的第二个问题,我认为我的algorhythm并不坏,它在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

代码就是那么长,因为它是我记忆系统缩短时间但是在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)

是该代码的第一种形式

Answer 1

1. 为了善良,清理你的代码,以便人们可以阅读它.例如,重写snd (head ((a,res):x)) --> res.另一个建议是:添加类型签名.
2. 将常见的子表达式(quot)提取到命名的let绑定中,以显着减少工作量.
3. 记住你给GiveRes的电话.这将为您带来最大的利益.如果您搜索SO,[haskell] memo那么您应该获得很多好结果.
4. 不要使用列表作为集合来测试membership(search)后面跟着lookup(send)的部分函数.而是考虑使用容器或无序容器库中的一个Map或多个HashMap.