Am Mittwoch, 21. Dezember 2005 08:18 schrieb Branimir Maksimovic:
> 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.
I'm far less sure of that. If you have a really short search-pattern, I think
that probably straightforward search is indeed faster (at least, if the
search-pattern isn't supplied at compile-time). But if you have a pattern of
length 100, say, and lots of relatively long partial matches, chances are
that KMP will move on something like 50 chars at once, which would have to be
re-checked by straightforward. I've no idea, when that would outweigh the
extra time of building the KMP-arrays, though. In my test -- extremely
unrealistic, but provides a more or less worst case example --
straightforward must make roughly half a million character comparisons to
pass each 'c', while KMP does 2000 (+/-2) (one way through the array and
back), so there are situations where KMP definitely is faster. But
ordinarily, on my computer, your version of straightforward is 10-15% faster
than KMP (search-patterns are now supplied on the command line -- which has
no big impact; searched string is " able sea..."; all compiled with -O2;
NOINLINE makes no difference -- at least with optimisations on --; without
optimisations, KMP suffers far worse than straightforward).
>
> KMP is O(m) while straightforward is O(m*n).
Where m is the length of the input and n is the length of the searched-for
pattern, I think?
But these are worst-case complexities, I believe, ordinarily, straightforward
will be O(m), too.
>
> 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 results seem to witness against that.
>
> My test favors straightforward, in any other case KMP wins by order of
> magnitude.
Can you give example tests?
> 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
>
> Greetings, Bane.
>
Cheers,
Daniel
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
