From: Bulat Ziganshin <[EMAIL PROTECTED]>
Reply-To: Bulat Ziganshin <[EMAIL PROTECTED]>
To: "Branimir Maksimovic" <[EMAIL PROTECTED]>
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
[EMAIL PROTECTED] ~/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:
[EMAIL PROTECTED] myhaskell]$ time ./KMP
Working:seasearch replace able seaseasearch baker seasearch charlie
True
Done
real 1m58.066s
user 1m57.939s
sys 0m0.128s
[EMAIL PROTECTED] 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
[EMAIL PROTECTED] ~/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:
[EMAIL PROTECTED] myhaskell]$ time ./KMP
Working:seasearch replace able seaseasearch baker seasearch charlie
True
Done
real 0m10.546s
user 0m10.529s
sys 0m0.016s
[EMAIL PROTECTED] 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/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
