in reply to Is it possible to find the number of matching and non-matching positions in strings using perl code?

Finding characters where two string differs can be done with bitwise operations. If you binary XOR two strings, positions where both characters are the same come out as a null byte. When doing several comparisons, one can accumulate the differing positions using binary OR: 


use warnings;
use strict;
use 5.010; # for say()

my $a='AAATGCCTT';
my $b='AAAAGCGTC';
my $c='AAAGGCGTC';

my $mask = chr(0) x length $a;
for ($b, $c) {
    $mask |= $a ^ $_;
}

# just to illustrate what the mask looks like:
use Data::Dumper;
$Data::Dumper::Useqq = 1;


# count number of 0-bytes
my $matches =()= $mask =~ /\0/g;
say "Matches:     ", $matches;
say "Non-matches: ", length($a) - $matches;

[download]

This approach should scale well for longer strings, since the binary operations are faster than looping over all characters.

Perl 6 - the future is here, just unevenly distributed
  • Comment on Re: Is it possible to find the number of matching and non-matching positions in strings using perl code?
  • Download Code

Replies are listed 'Best First'.
Re^2: Is it possible to find the number of matching and non-matching positions in strings using perl code?
by BrowserUk (Patriarch) on May 11, 2012 at 07:29 UTC

    Nice explanation++.

    One minor change: s/binary operations are faster than looping over all characters/looping over the characters in C is faster than looping over the characters in Perl/

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

    The start of some sanity?
[reply]

      The question is whether or how much C-level looping is there actually. Some CISC processors include string operators so the XOR might actually be a single instruction.

      Jenda
      Enoch was right!
      Enjoy the last years of Rome.

[reply]
[reply]
        Some CISC processors include string operators so the XOR might actually be a single instruction.

        They still loop, just at the microcode level.

        There is always a conditional test; address register(s) get incremented; and often a count register gets decremented; for some number of repetitions or until some condition is met. It's still a 'loop' by any standard.

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

        The start of some sanity?
[reply]
Re^2: Is it possible to find the number of matching and non-matching positions in strings using perl code?
by sauoq (Abbot) on May 11, 2012 at 11:26 UTC
[reply]
[d/l]
      But the for loop just obfuscates things without adding anything at all.

      It adds generality beyond three strings to compare.

      Also, calling your variable $mask is questionable as you don't really intend to use it as a mask.

      So what do you suggest instead? Your usage of $bits isn't any better, because you don't care about bits, but bytes. But $bytes also wouldn't explain the purpose of the variable.

      Perl 6 - the future is here, just unevenly distributed
[reply]
[d/l]
[select]
        It adds generality beyond three strings to compare.

        I might give you that if you wrote it that way. for ($b, $c) isn't any more general than my single statement. We'd both have to go change our code if we suddenly had to compare 4 strings.

        So what do you suggest instead? Your usage of $bits isn't any better, because you don't care about bits, but bytes.

        I'm not suggesting it's a good name for anything more than a throwaway example, but I wouldn't say it isn't any better. I do actually care about bits as I'm using it with bitwise operators. And the real point is that calling it $mask implies that you intend to use it as a mask. When you don't, confusion results.

        -sauoq
        "My two cents aren't worth a dime.";
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom