I've found one remaining bug, and this is corrected version.
Now it is fastest with your test (still 0.25 seconds), but undoubtly slowest
with mine:0)
But I crafted this test to be really rigorous to mine implementation. Lot of
replaces, repated
patterns and so. In real world situtaion it will perform much better, I
hope.
so here it is:
---
main :: IO ()
main =let src = replicate 1000 'r'
dst = #
str = replicate 999 'r' ++ 'c': replicate 1000 'r'
out = searchReplace src dst $ concat $ replicate 500 str
out1 = searchReplace src dst $ concat $ replicate 500 str
in do putStrLn $ Working very long
putStrLn $ show (out == out1) ++ \nDone
---
searchReplace :: String-String-String - String
searchReplace sr rp xs = searchr sr rp xs
where
searchr :: String-String-String-String - String
searchr [] _ xs _ = xs
searchr _ _ [] _ = []
searchr sr rp xs rollBack
| fst $ fst $ fnd = rp
++ searchr sr rp (snd $ snd $ fst $
fnd )
( snd fnd )
| otherwise = reverse ((fst $ snd $ fst $ fnd ) ++
rollBack)
++ searchr sr rp (snd $ snd $ fst $ fnd)
( snd fnd)
where fnd = searchr' (drop (length rollBack) sr) xs
searchr' :: String-String-String - ((Bool,(String,String)),String)
searchr' (sr:srs) xs fndSoFar = searchr'' (sr:srs) xs fndSoFar
(False,False,) sr
searchr'' :: String-String-String-(Bool,Bool,String)-Char
- ((Bool,(String,String)),String)
searchr'' [] xs fnd _ _ = ((True,(fnd,xs)),)
searchr'' _ [] fnd (_,_,rollBack) _ = ((False,(fnd,[])),rollBack)
searchr'' (sr:srs) (x:xs) fndSoFar (cnt,f,rollBack) s
| sr == x = if cnt (f || s == x)
then searchr'' srs xs fndSoFar (True,True,x:rollBack) s
else searchr'' srs xs (x:fndSoFar) (True,False,) s
| otherwise = if not f
then if s == x
then ((False,(fndSoFar,x:xs)),)
else ((False,searchr''' s xs
(x:fndSoFar)),)
else if s == x getFst rollBack == s
then ((False,(fndSoFar, xs)),x:rollBack)
else ((False,(fndSoFar,x:xs)),rollBack)
searchr''' :: Char-String-String - (String,String)
searchr''' sr [] fndSoFar = (fndSoFar,[])
searchr''' sr (x:xs) fndSoFar -- | sr/=x = searchr''' sr xs (x:fndSoFar)
| otherwise = (fndSoFar,x:xs)
getFst (a:as) = a;
---
From: Branimir Maksimovic [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: [Haskell-cafe] RE: Substring replacements (was: Differences
inoptimisiation ...)
Date: Sun, 11 Dec 2005 02:19:22 +
After seeing your test, I've implemented full KMP algorithm, which
is blazingly fast with your test. It is slower in mine test due excessive
temporaries
I guess, but perhaps you can help me to make it better as I'm just Haskell
newbie.
You can see that by my code :0)
Especially I'm clumsy with passing parameters around.
main :: IO ()
main =let src = replicate 1000 'r'
dst = #
str = replicate 999 'r' ++ 'c': replicate 1000 'r'
out = searchReplace src dst $ concat $ replicate 500 str
out1 = searchReplace src dst $ concat $ replicate 501 str
in do putStrLn $ Working very long
putStrLn $ show (out == out1) ++ \nDone
---
searchReplace :: String-String-String - String
searchReplace sr rp xs = searchr sr rp xs
searchr :: String-String-String-String - String
searchr [] _ xs _ = xs
searchr _ _ [] _ = []
searchr sr rp xs rollBack | fst $ fst fnd = rp
++ searchr sr rp (snd $ snd $
fst fnd)
(snd fnd)
| otherwise = reverse ((fst $ snd $ fst $ fnd) ++
rollBack)
++ searchr sr rp (snd $ snd $ fst fnd)
(snd fnd)
where fnd = searchr' (drop (length rollBack) sr) xs
searchr' :: String-String-String - ((Bool,(String,String)),String)
searchr' (sr:srs) xs fndSoFar = searchr'' (sr:srs) xs fndSoFar
(False,False,) sr
searchr'' :: String-String-String-(Bool,Bool,String)-Char
- ((Bool,(String,String)),String)
searchr'' [] xs fnd _ _ = ((True,(fnd,xs)),)
searchr'' _ [] fnd _ _ = ((False,(fnd
