Version française
Home     About     Download     Resources     Contact us    
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: -- (:)
From: eijiro_sumii@a...
Subject: Re: substring match like "strstr"
> Any ideas why strstr blows the others away?  What's the libc strstr
> look like?

I have no idea, unfortunately...

> I just looked in the MSVC source and it's a braindead while loop
> (copied below), so it's not like it's doing a fancy Boyer-Moore or
> anything.

I don't know anything about strstr in Sun's strstr, but I checked
strstr in GNU libc.  It is a quite complicated program, but look like
a brute-force algorithm (that is, no Knuth-Morris-Pratt or anything
like that).

> This is exactly the kind of problem on which I'd expect caml to come
> within 10% of c.

That was what I expected, too.

> I'd say I'd do the tests myself, but I don't have a bunch of gene
> sequences laying around.  :)

I've put the current version of my application program at:

  http://www.yl.is.s.u-tokyo.ac.jp/~sumii/tmp/hc.tar.gz

If you like, you're welcome to check it yourself, of course.:) You can
run it as "make ; time ./hc".  The output should look like:

  score = 0.348672
  score = 0.391356
  (snip)
  score = 0.630415

The OCaml function "strstr" is in the file "strstr.ml".

> 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?

Sure, but please give me a little time.  This is a kind of part-time,
weekend job for me, and I can't tell when I have time to do it next...

Eijiro