CODEWITHSUNDEEP
haskellfunctional-programming
oknsnl
oknsnl

Reputation: 351

Haskell Time Issue

it is my second question about haskell and i thought my algorhythm is not bad and it gives faster results in c++ and python and there is some problem at haskell it cant give me 10^25 (maybe it gives but i dont wait that much) and this question ask me that value ,please guide me to fix this guy thanks from now.

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

code is that but its that long because it is my remembering system to shortening time but in haskell its not efficient

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)

is first form of that code

Upvotes: 0

Views: 184

Answers (1)

Thomas M. DuBuisson
Thomas M. DuBuisson

Reputation: 64740

  1. For goodness sakes, clean up your code so people can read it. For example, rewrite snd (head ((a,res):x)) --> res. Another suggestion: add type signatures.
  2. Extract your common subexpressions (quot) into named let bindings to significantly reduce work.
  3. Memoize your calls to giveRes. This will give you the largest benefit. If you search SO for [haskell] memo then you should get lots of good results.
  4. Don't use a list as a set to test membership (search) followed by a partial function for lookup (send). Instead consider using a Map or HashMap from the containers or unordered-containers libraries.

Upvotes: 9

Related Questions