Re: [Haskell-cafe] Substring replacements

From: Bulat Ziganshin Reply-To: Bulat Ziganshin To: "Branimir Maksimovic" CC: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Substring replacements Date: Tue, 20 Dec 2005 23:55:22 +0300

Hello Branimir,

Tuesday, December 20, 2005, 9:48:48 PM, you wrote:

BM> I've finally performed test on amd64 and result is a same as on intel. BM> KMP always wins. So KMP is best suited for non indexed strings BM> and I guess should be used in library as prefered search/replace method. BM> This test favors straightforward search.

i'm 90% sure that straightforward method must be faster for one-time searches.

KMP is O(m) while straightforward is O(m*n). your test may give better results with KMP algorithm just

because you repeat the same search many times and it was automatically "run-time compiled" as described on the wiki page about KMP

My test favors straightforward, in any other case KMP wins by order of magnitude. I think that straightfoirward is better then KMP with optimisations off is due more complex program.

try to add

{-# NOINLINE replace #-}

to both programs and repeat comparision

These are tests: No optimisations (no -O): Intel hyperthreaded,windows $ time ./KMP Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m34.766s user 0m0.015s sys 0m0.000s bmaxa@MAXA ~/tutorial $ time ./straightforward Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m14.719s user 0m0.031s sys 0m0.000s AMD 64 bit: [bmaxa@devel64 myhaskell]$ time ./KMP Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 1m58.066s user 1m57.939s sys 0m0.128s [bmaxa@devel64 myhaskell]$ time ./straightforward Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m41.565s user 0m41.527s sys 0m0.040s with optimisations (-O): Intel hyperthreaded,windows $ time ./KMP Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m8.625s user 0m0.015s sys 0m0.015s bmaxa@MAXA ~/tutorial $ time ./straightforward Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m11.735s user 0m0.015s sys 0m0.000s AMD 64 bit, linux: [bmaxa@devel64 myhaskell]$ time ./KMP Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m10.546s user 0m10.529s sys 0m0.016s [bmaxa@devel64 myhaskell]$ time ./straightforward Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m11.796s user 0m11.785s sys 0m0.012s Greetings, Bane. _________________________________________________________________ FREE pop-up blocking with the new MSN Toolbar - get it now! http://toolbar.msn.click-url.com/go/onm00200415ave/direct/01/