From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id IAA02603; Wed, 11 Jul 2001 08:44:14 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id IAA02599 for ; Wed, 11 Jul 2001 08:44:13 +0200 (MET DST) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f6B6iC906902 for ; Wed, 11 Jul 2001 08:44:12 +0200 (MET DST) Received: from pc803.lri.fr (IDENT:root@pc803 [129.175.8.114]) by ext.lri.fr (8.11.1/jtpda-5.3.2) with ESMTP id f6B6iB510421 ; Wed, 11 Jul 2001 08:44:11 +0200 (MET DST) Received: by pc803.lri.fr (8.9.3/feuille) id IAA31557 ; Wed, 11 Jul 2001 08:44:11 +0200 X-Authentication-Warning: localhost.localdomain: filliatr set sender to filliatr@pc803 using -f From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <15179.62907.650110.606283@pc803> Date: Wed, 11 Jul 2001 08:44:11 +0200 (MEST) To: Markus Mottl Cc: Berke Durak , caml-list@inria.fr Subject: Re: [Caml-list] String.unescaped and some other little pitiful laments In-Reply-To: <20010710205534.B29850@fichte.ai.univie.ac.at> References: <20010710200734.B10265@localhost.localdomain> <20010710205534.B29850@fichte.ai.univie.ac.at> X-Mailer: VM 6.49 under Emacs 20.4.1 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Markus Mottl writes: > If somebody wants to give it a try, the SML-entry in the language shootout > implements a regexp-library with NFAs and DFAs. I haven't given it a > closer look yet, but performance looks excellent: > > http://www.bagley.org/~doug/shootout/bench/regexmatch/regexmatch.mlton I tried Claude Marché's Regexp library instead of Pcre on that particular example and there is a speedup of 5 % approximatively. Note that the Regexp library compiles regular expressions into deterministic finite automata using a very different algorithm than the SML entry, from this article: G. Berry and R. Sethi From Regular Expressions to Deterministic Automata Theoretical Computer Science 48 (1986) 117-126 This is a very nice and concise algorithm and I encourage anybody interested in regexp and automata to have a look at it (again, the url for the code is http://www.lri.fr/~marche/tmp/regexp-0.1.tar.gz) -- Jean-Christophe Filliatre mailto:Jean-Christophe.Filliatre@lri.fr http://www.lri.fr/~filliatr ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr