English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
substring match like "strstr"
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2000-12-14 (18:22)
From: Julian Assange <proff@i...>
Subject: Re: substring match like "strstr"
eijiro_sumii@anet.ne.jp writes:

> Hi everyone,
> Thank you very much for a lot of kind advice!
> Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr> wrote:
> > I   missed  the   beginning  of   the  discussion,   but  implementing
> > Knuth-Morris-Pratt is quite easy. The  code is given below (26 lines),
> Actually, I found the (almost) same code on the web and tried it.  The
> results (again, execution time in seconds) were:
> 		SPARC	Pentium
> 	strstr	52.68	57.050
> 	kmp	111.52	143.490

All of these more sophisticated methods are only going to be a win
when you are searching for larger strings. strstr is brutally simple,
has little setup/cleanup time, and hence is hard to beat for short
strings. Additionally gcc, will replace various s* calls with in-line
assembly versions. I'm not sure if this includes strstr (it is a
little more complicated than most).