From: Daniel Fischer <[EMAIL PROTECTED]>
To: Haskell-Cafe@haskell.org
Subject: [Haskell-cafe] Substring replacements
Date: Mon, 12 Dec 2005 01:14:37 +0100
Okay, I have looked up KMP and implemented it.
Seems to work -- my first use of QuickCheck, too.
It's slower than Bulat's and Tomasz' for Branimir's test :-(,
but really fast for my test.
Strange I got completelly different results:
[EMAIL PROTECTED] ~/tutorial
$ time srchrep.exe
Working very long
True
Done
real 0m16.407s
user 0m0.015s
sys 0m0.015s
[EMAIL PROTECTED] ~/tutorial
$ ghc -fglasgow-exts -O2 srchrep.hs --make -o srchrep.exe
Chasing modules from: srchrep.hs
Compiling Main ( srchrep.hs, srchrep.o )
Linking ...
[EMAIL PROTECTED] ~/tutorial
$ time srchrep.exe
Working:seasearch replace able seaseasearch baker seasearch charlie
True
Done
real 0m10.156s
user 0m0.015s
sys 0m0.015s
[EMAIL PROTECTED] ~/tutorial
$ time replace1.exe
Working:seasearch replace able seaseasearch baker seasearch charlie
True
Done
real 0m11.672s
user 0m0.015s
sys 0m0.015s
Now your version is fastest according to my machine, but it is not faster
with your test it's slower in compariton to replace1.
I've corrected my code so it is fastest with your test,still less then a
second,
but slowest with mine.
Checked with your fail tests and compared results of these 2 tests.
Now should be ok.
I maintan now two lists one for successes and other for failures.
I also prettified code a bit .
searchReplace :: String->String->String -> String
searchReplace sr rp xs = searchr sr rp xs "" ""
where
searchr :: String->String->String->String->String -> String
searchr [] _ xs _ _ = xs
searchr _ _ [] _ _ = []
searchr sr rp xs retBack rollBack
| isFound $ fnd rollBack = rp
++ searchr sr rp (remaining $ fnd
rollBack )
( getRetBack $ fnd
rollBack)
( getRollBack $ fnd
rollBack)
| otherwise = reverse ((processed $ fnd rollBack) ++
rollBack)
++ searchr sr rp (remaining $ fnd rollBack)
( getRetBack $ fnd rollBack)
( getRollBack $ fnd
rollBack)
where fnd = searchr' sr sr (reverse retBack ++ xs) ""
isFound = fst . fst
remaining = snd . snd . fst
getRollBack = snd . snd
getRetBack = fst . snd
processed = fst . snd . fst
searchr' :: String->String->String->String->String
-> ((Bool,(String,String)),(String,String))
searchr' srch@(sr:srs) srch'@(sr':srs') xs fndSoFar rollBack =
searchr'' (drop (length rollBack) srch) srch' xs
fndSoFar
(False,"","") sr
searchr'' :: String->String->String->String->(Bool,String,String)->Char
-> ((Bool,(String,String)),(String,String))
searchr'' [] _ xs fnd _ _ = ((True,(fnd,xs)),("",""))
searchr'' _ _ [] fnd (_,retBack,rollBack) _ = ((False,(retBack ++
rollBack ++ fnd,[])),("",""))
searchr'' srch@(sr:srs) srch'@(sr':srs') xxs@(x:xs) fndSoFar
(cnt,retBack,rollBack) s
| sr == x = if cnt && sr' == x && isEmpty retBack
then searchr'' srs srs' xs fndSoFar
(True,"",x:rollBack) s
else if not (isEmpty retBack) || not (isEmpty
rollBack)
then searchr'' srs srch' xs fndSoFar
(True,(x:rollBack) ++
retBack,"") s
else searchr'' srs srch' xs (x:fndSoFar)
(True,"","") s
| otherwise = if isEmpty rollBack && isEmpty retBack
then if s == x
then ((False,(fndSoFar,xxs)),("",""))
else ((False,searchr''' s xs
(x:fndSoFar)),("",""))
else if sr' == x && isEmpty retBack
then ((False,(fndSoFar, xs)),
(retBack,x:rollBack))
else ((False,(fndSoFar, xxs)),
(retBack,rollBack))
searchr''' :: Char->String->String -> (String,String)
searchr''' sr [] fndSoFar = (fndSoFar,[])
searchr''' sr xxs@(x:xs) fndSoFar | sr/=x = searchr''' sr xs
(x:fndSoFar)
| otherwise = (fndSoFar,xxs)
isEmpty [] = True
isEmpty (a:as) = False
-------------------------------------------------------------------------------
Greetings, Bane.
_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE!
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
