Re: diff (different enough)

I'd use XOR logic.

# $m      = 5
# $a      = "ABCDEFGHIJKL"
# $b      = "ACHDEFIHAJLK"
# $diff   = 0
# $xor_ed = "\000\001\013\000\000\000\016\000\010\000\007\007"

sub mdiff {
  my ($m,$a,$b) = @_;
  my ($la,$lb) = (length $a, length $b);
  my $xor_ed;
  my $diff = abs($lb - $la);

  return 1 if $diff >= $m;
  return 1 if ($diff + ($xor_ed = $a ^ $b) =~ tr/\0//c) >= $m;
}
[download]

Bitwise XOR in strings is a beautiful thing. The number of NULs in the XOR-ed string (\0) will be the number of same characters. The opposite is the number of different characters, so I tr/\0//c.

Comment on Re: diff (different enough) Download Code

Replies are listed 'Best First'.
RE: Re: diff (different enough) by jettero (Monsignor) on Jul 21, 2000 at 18:23 UTC
that is pretty cool, but for both length()s you have to go through the whole string, and for the tr//c, you have to compare many of the chars again. I tried this one... it's about 3 times slower than my naive string comparison in C. But it's still a bunch faster than Chromatic's solution up there.	[reply]
RE: RE: Re: diff (different enough) by japhy (Canon) on Jul 21, 2000 at 18:50 UTC
Um, if you mean doing length($str) requires a call to strlen(), you're wrong. From 'perlguts': You can get and set the current length of the string stored in an SV with the following macros: `SvCUR(SV) SvCUR_set(SV, I32 val)` [download] And checking with Devel::Peek: `jeffp@hut [10:44am] ~ #104> perl -MDevel::Peek $str = "something"; Dump($str); SV = PV(0xa3424) at 0xb4fc0 REFCNT = 1 FLAGS = (POK,pPOK) PV = 0xb9600 "something"\0 CUR = 9 LEN = 10` [download] So Perl determines the string length when it's set (which would be when you created the string originally), and uses that value when you call length(). But you're right that you have to go through the entire string when you use tr///. I admit that sucks a bit.	[reply] [d/l] [select]
RE: RE: Re: diff (different enough) by tye (Sage) on Jul 21, 2000 at 18:29 UTC
FYI, unlike C's <char *>, Perl has real strings that know how long they are. So <length> is as fast as getting the integer value of a scalar that already has its integer value cached.	[reply]


Clear questions and runnable code get the best and fastest answer
	PerlMonks