From: Robert Klemme <shortcutter@...>
Date: 2011-03-08T05:12:49+09:00
Subject: Re: Hamming Distance

On 07.03.2011 18:11, Kirk Haines wrote:
> On Mon, Mar 7, 2011 at 8:47 AM, Martin Hansen<mail@maasha.dk>  wrote:
>> What is the fastest way to calculate the Hamming Distance between two
>> equally long strings in Ruby? A have looked at the amatch gem, but I was
>> wondering what can be done with Ruby only?
>>
>> Here is a very interesting discussion on the subject:
>>
>> http://www.perlmonks.org/?node_id=500235
>>
>>
>> Note the elegant and extremely fast Perl solution:
>>
>> sub hd {
>>     return ($_[0] ^ $_[1]) =~ tr/\001-\255//;
>> }
>
> There are a bunch of ways. There isn't a built in xor of strings in
> Ruby, but it's easy to define one.  Once you have that, you can do it
> pretty similarly to the Perl example:
>
>    def hd(l, r)
>      l.xor(r).tr("\x00",'').length
>    end
>
> You can implement xor of two strings using pure ruby, but to get it
> fast, you'll probably want to utilize an extension.  Here's one
> approach using a technique that, I believe, was in the mailing list
> several years ago:
>
>
> require "narray"
>
> class String
>    def xor(other)
>      if other.empty?
>        self
>      else
>        left = self
>        right = other
>
>        if left.length<  right.length
>          n,r = right.length.divmod(left.length)
>          left = left * n + left[0, r]
>        elsif right.length<  left.length
>          n,r = left.length.divmod(right.length)
>          right = right * n + right[0, r]
>        end
>
>        left_na = NArray.to_na(left, "byte")
>        right_na = NArray.to_na(right, "byte")
>
>        (left_na ^ right_na).to_s
>      end
>    end
>
>    def hamming_distance(other)
>      self.xor(other).tr("\x00",'').length
>    end
> end

I'll throw in two other solutions for whoever wants to do a benchmark.

class String
   def hd_1(s)
     c = 0

     each_codepoint.zip(s.each_codepoint) do |l, r|
       c += 1 unless l == r
     end

     c
   end

   def hd_2(s)
     each_codepoint.zip(s.each_codepoint).select {|l, r| l != r}.length
   end
end

Cheers

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/