From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA02907 for caml-red; Mon, 11 Dec 2000 18:38:56 +0100 (MET) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA07650 for ; Sun, 10 Dec 2000 16:46:39 +0100 (MET) Received: from moutvdom01.kundenserver.de (moutvdom01.kundenserver.de [195.20.224.200]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id eBAFkdT22720 for ; Sun, 10 Dec 2000 16:46:39 +0100 (MET) Received: from [195.20.224.204] (helo=mrvdom00.kundenserver.de) by moutvdom01.kundenserver.de with esmtp (Exim 2.12 #2) id 1458g6-0007iB-00; Sun, 10 Dec 2000 16:46:18 +0100 Received: from drms-3e364b1e.pool.mediaways.net ([62.54.75.30] helo=ice.gerd-stolpmann.de) by mrvdom00.kundenserver.de with esmtp (Exim 2.12 #2) id 1458g1-0008S6-00; Sun, 10 Dec 2000 16:46:13 +0100 Received: from localhost (localhost [[UNIX: localhost]]) by ice.gerd-stolpmann.de (8.9.3/8.9.3) id QAA30680; Sun, 10 Dec 2000 16:46:09 +0100 From: Gerd Stolpmann Reply-To: gerd@gerd-stolpmann.de Organization: privat To: eijiro_sumii@anet.ne.jp, caml-list@inria.fr Subject: Re: substring match like "strstr" Date: Sun, 10 Dec 2000 16:39:12 +0100 X-Mailer: KMail [version 1.0.28] Content-Type: text/plain Cc: gerd@gerd-stolpmann.de, sumii@venus.is.s.u-tokyo.ac.jp References: <20001208150443I.sumii@yl.is.s.u-tokyo.ac.jp> <00120814135508.00625@ice> <20001210221657W.sumii@yl.is.s.u-tokyo.ac.jp> In-Reply-To: <20001210221657W.sumii@yl.is.s.u-tokyo.ac.jp> MIME-Version: 1.0 Message-Id: <0012101646090G.00625@ice> Content-Transfer-Encoding: 8bit Sender: weis@pauillac.inria.fr On Sun, 10 Dec 2000, eijiro_sumii@anet.ne.jp wrote: >OK, I benchmarked the following 4 implementations for the purpose of >comparison. > > strstr > stub to call "strstr" in libc > > regexp > combination of "Str.regexp_string" and "Str.search_forward" > > OCamlA > the simple implementation in OCaml given in the previous message, > a little tuned for more efficiency > > OCamlB > another straightforward implementation in OCaml, attached at the > end of this message > >The results (execution time in seconds) were as follows. > > strstr 55.74 > regexp 154.37 > OCamlA 302.57 > OCamlB 129.23 I did not expect that OCamlB performs so well; so I suggested OcamlA and regexp (which are both fast for the bytecode interpreter, too). I think it depends also on the problem size (especially on the length of the substring). Gerd -- ---------------------------------------------------------------------------- Gerd Stolpmann Telefon: +49 6151 997705 (privat) Viktoriastr. 100 64293 Darmstadt EMail: gerd@gerd-stolpmann.de Germany ----------------------------------------------------------------------------