Recursion/dynamic programming optimization
Hi. I tried to solve one of the google code jam's problems using haskel http://code.google.com/codejam/contest/dashboard?c=90101#s=p2: w :: Eq a => [a] -> [a] -> Int w text str = w' (reverse text) (reverse str) w' :: Eq a => [a] -> [a] -> Int -- Init w' _ [] = 0 w' [] _ = 0 -- For one symbol string w' text [a] = if head text == a then w' (tail text) [a] +1 else w' (tail text) [a] -- General case w' text str = if head str == head text then w' (tail text) (tail str) + w' (tail text) str else w' (tail text) str and it worked great on small inputs, not on large: w "viwiwhiuwwwgxzseebneesgzxiekzeeyivrbbhzrlllccxczyurxfhhccghkzvxusfbcucyvncpzpvfvccxcvbqnqogobzoiorxrbikyzzbobpmmmmpmvrzyivpfmmuzxixhqpeebyekkxffeyexeiukuebgbrukzefeu rkxy z h x vkq fsyp iy tfyzbptygtsrkhbytvruztzbttnoxuquokipyyqoik ib xu gxchcnccuccyfcccccsczccskifcprgovryxuxoozqoozsvudyfkdpkkxyhdvfsrnvpnpzvrhqhbduidkdpdysinyxnuxnxipddevqhgeufxeepyyezbekyviieeeryiexynevbzfeezryizvepynefffy y v zuzrbpzn sz y vzirkxjniuqvjjbjgubnjkujhjpiyanaabrqagzqqvspqpkvqyuhrgupbaiaasxybiygmmfimyvykkmrzum" "welcome to code jam" Can you please advice how to optimize this solution? Thanks. Regards, Ivan Vovnenko
On Mar 19, 2010, at 16:41 , ivovnenko wrote:
w :: Eq a => [a] -> [a] -> Int w text str = w' (reverse text) (reverse str) w' :: Eq a => [a] -> [a] -> Int -- Init w' _ [] = 0 w' [] _ = 0 -- For one symbol string w' text [a] = if head text == a then w' (tail text) [a] +1 else w' (tail text) [a]
Couple of suggestions here:
w' (x:xs) s@[a] = w' xs s + (if x == a then 1 else 0)
-- General case w' text str = if head str == head text then w' (tail text) (tail str) + w' (tail text) str else w' (tail text) str
w' (x:xs) s@(a:as) = let next = w' xs s in if x == a then w' xs as + next else next
This will save some function calls by using pattern matching. Combining the common subexpressions probably won't count for much except in terms of elegance. The rest probably comes down to strictness but I'll let more knowledgeable people comment on that :) -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
On 19/03/10 20:41, ivovnenko wrote:
Hi. I tried to solve one of the google code jam's problems using haskel http://code.google.com/codejam/contest/dashboard?c=90101#s=p2:
w :: Eq a => [a] -> [a] -> Int w text str = w' (reverse text) (reverse str) w' :: Eq a => [a] -> [a] -> Int -- Init w' _ [] = 0 w' [] _ = 0 -- For one symbol string w' text [a] = if head text == a then w' (tail text) [a] +1 else w' (tail text) [a] -- General case w' text str = if head str == head text then w' (tail text) (tail str) + w' (tail text) str else w' (tail text) str
and it worked great on small inputs, not on large:
I suspect that a change of type for w' would improve things a bit. The base cases: w' n [] _ = n w' n _ [] = n w' n (t:ts) [a] = if t == a then w' (succ n) ts [a] else w' n ts [a] After reading the problem description though I think that thinking hard about the problem might reveal that there's a more clever way to solve it instead of the rather brute-force route you've taken so far. /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe
participants (3)
-
Brandon S. Allbery KF8NH -
ivovnenko -
Magnus Therning