Hamming Distance

M

Martin Hansen

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//;
}



Cheers,



Martin
 
K

Kirk Haines

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=3D500235


Note the elegant and extremely fast Perl solution:

sub hd {
=A0 =A0return ($_[0] ^ $_[1]) =3D~ 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 =3D self
right =3D other

if left.length < right.length
n,r =3D right.length.divmod(left.length)
left =3D left * n + left[0, r]
elsif right.length < left.length
n,r =3D left.length.divmod(right.length)
right =3D right * n + right[0, r]
end

left_na =3D NArray.to_na(left, "byte")
right_na =3D 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


Kirk Haines
Software Engineer
Engine Yard
 
R

Robert Klemme

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
 
K

Kirk Haines

You can implement xor of two strings using pure ruby, but to get it
fast, you'll probably want to utilize an extension. =A0Here's one

Actually, I should revise that statement. To get it really fast with
MRI, you'll probably want to utilize an extension. I am guessing, as
I haven't benchmarked anything, but one may well be able to get much
faster pure ruby speeds with jruby or rubinius. When in doubt,
benchmark it!


Kirk Haines
 
B

botp

Actually, I should revise that statement. =A0To get it really fast with
MRI, you'll probably want to utilize an extension. =A0I am guessing, as
I haven't benchmarked anything, but one may well be able to get much
faster pure ruby speeds with jruby or rubinius. =A0When in doubt,
benchmark it!

am staying w your modest narray implem ;-)

$ ruby test_hamming_distance.rb
Rehearsal ------------------------------------------------
kirk narray 0.140000 0.030000 0.170000 ( 0.160551)
robert zip 1 22.570000 0.010000 22.580000 ( 22.589685)
robert zip 2 22.870000 0.020000 22.890000 ( 22.922881)
-------------------------------------- total: 45.640000sec

user system total real
kirk narray 0.050000 0.030000 0.080000 ( 0.080348)
robert zip 1 22.490000 0.090000 22.580000 ( 22.805407)
robert zip 2 22.900000 0.040000 22.940000 ( 22.963609)

wow, your narray scheme is immune to length of string...

thanks kirk and robert
best regards -botp
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top