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 TAA15105 for caml-red; Thu, 14 Dec 2000 19:28:46 +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 EAA04283 for <caml-list@pauillac.inria.fr>; Thu, 14 Dec 2000 04:37:19 +0100 (MET)
Received: from dynabook (h12-001.tokyu-net.catv.ne.jp [202.221.12.1])
	by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id eBE3bIL15652
	for <caml-list@inria.fr>; Thu, 14 Dec 2000 04:37:18 +0100 (MET)
Received: from dynabook
	([127.0.0.1] helo=localhost ident=sumii)
	by dynabook with esmtp (Exim 3.12 #1 (Debian))
	id 146PC8-0000Gd-00; Thu, 14 Dec 2000 12:36:36 +0900
To: checker@d6.com
From: eijiro_sumii@anet.ne.jp
Cc: caml-list@inria.fr, gerd@gerd-stolpmann.de, sumii@venus.is.s.u-tokyo.ac.jp
Subject: Re: substring match like "strstr"
In-Reply-To: <4.3.2.7.2.20001211103237.00c12100@shell16.ba.best.com>
References: <00120814135508.00625@ice>
	<20001210221657W.sumii@yl.is.s.u-tokyo.ac.jp>
	<4.3.2.7.2.20001211103237.00c12100@shell16.ba.best.com>
X-Mailer: Mew version 1.94.2 on Emacs 20.7 / Mule 4.1 (AOI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-Id: <20001214123635H.sumii@yl.is.s.u-tokyo.ac.jp>
Date: Thu, 14 Dec 2000 12:36:35 +0900
X-Dispatcher: imput version 991025(IM133)
Sender: weis@pauillac.inria.fr

> Okay, I'm curious, so I'll port the code to caml and include it
> below as well (as practice for myself).  Can you try it in your test
> harness?

I tried the optimized version of the imperative strstr, along with an
optimized version of the functional strstr (attached at the end).  The
results (on the SPARC machine) were:

	strstr_imp2	90.57
	strstr_fun2	89.64
	C strstr	53.76

So the imperative version and the functional version were comparable,
though both were slower than the C version.  My guess is that they
actually compile into rather similar code, because all recursive calls
are in tail positions.

Anyway, for my application, the libc version seems the most reasonable
choice, as far as I use a strstr-like function at all...

// Eijiro Sumii (http://www.yl.is.s.u-tokyo.ac.jp/~sumii/)
// 
// Ph.D. Student at Department of IS, University of Tokyo
// Visiting Scholar at Department of CIS, University of Pennsylvania

let strstr_fun2 pat str =
  let patlim = String.length pat - 1 in
  let strlim = String.length str - 1 in
  let rec sub patpos strpos =
    (* compare pat[0..patpos] and str[(strpos-patpos)..strpos] *)
    if patpos < 0 then true else
    if pat.[patpos] <> str.[strpos] then false else
    sub (patpos - 1) (strpos - 1) in
  let rec search strpos =
    (* compare pat[0..patlim] and str[(strpos-patlim)..strpos] *)
    if strpos > strlim then raise Not_found else
    if sub patlim strpos then strpos - patlim else
    search (strpos + 1) in
  search patlim
;;