[Haskell-cafe] Substring replacements

[Daniel Fischer]

Sorry, but
Prelude SearchRep> searchReplace "abaaba" "##" "abababaaba"
"abababaaba"

I haven't analyzed the algorithm, so I don't know why exactly this fails.
I'll take a look sometime soon.

As for times: a complete stat is attached, all compiled with -O2, as well as 
the modified KMP-version and my transcript of Branimir's new version.
On my computer, KMP smashes everything else on my test (except Branimir's, 
only that doesn't yet work correctly), while Bulat's definitely is faster 
than anything for Branimir's test and faster than anything but KMP for mine.

Branimir, isEmpty is the Prelude function 'null', so you needn't define it 
yourself.

Cheers,
Daniel

Am Montag, 12. Dezember 2005 05:20 schrieben Sie:
> From: Daniel Fischer <daniel.is.fischer at web.de>
>
> >To: Haskell-Cafe at 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:
>
> maxa at MAXA ~/tutorial
> $ time srchrep.exe
> Working very long
> True
> Done
>
> real    0m16.407s
> user    0m0.015s
> sys     0m0.015s
>
> bmaxa at MAXA ~/tutorial
> $ ghc -fglasgow-exts  -O2 srchrep.hs --make -o srchrep.exe
> Chasing modules from: srchrep.hs
> Compiling Main             ( srchrep.hs, srchrep.o )
> Linking ...
>
> bmaxa at MAXA ~/tutorial
> $ time srchrep.exe
> Working:seasearch replace  able seaseasearch baker seasearch charlie
> True
> Done
>
>
> real    0m10.156s
> user    0m0.015s
> sys     0m0.015s
>
> bmaxa at MAXA ~/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/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Files.tar.gz
Type: application/x-tgz
Size: 1623 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20051212/20374e1b/Files.tar.bin