[Haskell-cafe] Substring replacements

[Branimir Maksimovic]

>From: Bulat Ziganshin <bulatz at HotPOP.com>
>Reply-To: Bulat Ziganshin <bulatz at HotPOP.com>
>To: "Branimir Maksimovic" <bmaxa at hotmail.com>
>CC: haskell-cafe at 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 at 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 at devel64 myhaskell]$ time ./KMP
Working:seasearch replace  able seaseasearch baker seasearch charlie
True
Done


real    1m58.066s
user    1m57.939s
sys     0m0.128s
[bmaxa at 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 at 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 at devel64 myhaskell]$ time ./KMP
Working:seasearch replace  able seaseasearch baker seasearch charlie
True
Done


real    0m10.546s
user    0m10.529s
sys     0m0.016s
[bmaxa at 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/