Re: substring match like "strstr"

[eijiro_sumii@anet.ne.jp]

> 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