Re: [FWP] Quick hack for common length

["Abigail" <abigail@foad.org>]

On Mon, Jun 25, 2001 at 04:20:09PM -0700, Clinton A. Pierce wrote:
> >From fwp-l Mon Jun 25 15:26:34 2001
> 
> In #perl today, we were looking at a longest substrings problem,
> utilizing a suffix tree solution.  Part of the C code was:
> 
> int comlen(char *p, char *q)
> {
> 	i=0;
> 	while *p && (*p++ == *q++)
> 		i++;
> 	return i;
> }
> 
> A straight translation from C to Perl yeilded something slow.
> 
> The quickest solution I could come up with in perl looked like:
> 
> sub comlen_or {
> 	length((($_[0]^$_[1])=~m/^(\0+)/)[0]);
> }
> 
> Can anyone improve on that for speed?  I was actually happy with
> (and then disappointed) with the regular expression.  Is there a
> clever way to get rid of it, that list context and $1?
> (unpack and bretheren maybe?)


One should realize that $_[0]^$_[1] takes Omega (length ($_[0]) +
length ($_[1])) (that is, at least linear in the length of the
longest string), while the C code, and any straight translation
run in time linear to the length of the common prefix.

This means your "for speed improvement" requirement is tricky - what
the best algorithm will be strongly depends on the data.



Abigail

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe