计算红宝石中汉明距离的最有效方法? [英] Most efficient way to calculate hamming distance in ruby?

问题描述

在ruby中，计算两个无符号整数(例如汉明距离)之间的位差的最有效方法是什么?

In ruby, what is the most efficient way to calculate the bit difference between two unsigned integers (e.g. the hamming distance)?

例如，我有整数a = 2323409845和b =178264714​​4.

Eg, I have integer a = 2323409845 and b = 1782647144.

它们的二进制表示形式是:

Their binary representations are:

a = 10001010011111000110101110110101
b = 01101010010000010000100101101000

a&之间的位差b是17 ..

The bit difference between the a & b is 17..

我可以对它们执行逻辑XOR，但这会给我一个不同的整数！= 17，然后我必须遍历结果的二进制表示并计算1的数目.

I can do a logical XOR on them, but that will give me a different integer != 17, I would then have to iterate through the binary representation of the result and tally the # of 1s.

计算位差的最有效方法是什么?

What is the most efficient way to calculate the bit difference?

现在，计算许多整数序列的位差的答案是否改变?例如.给定2个无符号整数序列:

Now, does the answer change for calculating the bit difference of sequences of many ints? E.g. given 2 sequences of unsigned integers:

x = {2323409845,641760420,509499086....}
y = {uint,uint,uint...}

计算两个序列之间的位差的最有效方法是什么?

What is the most efficient way to calculate the bit difference between the two sequences?

您是要遍历整个序列，还是有一种更快的方法来一次计算整个序列的差异?

Would you iterate through the sequence, or is there a faster way to calculate the difference across the entire sequence at once?

推荐答案

您可以使用Ruby中优化的String函数来进行位计数，而不是使用纯算术.有了一些快速的基准测试，结果大约快了6倍.

You can make use of the optimized String functions in Ruby to do the bit counting, instead of pure arithmetic. It turns out to be about 6 times faster with some quick benchmarking.

def h2(a, b)
  (a^b).to_s(2).count("1")
end

h1是正常的计算方式，而h2将xor转换为字符串，并计算"1"的数量

h1 is the normal way to calculate, while h2 converts the xor into a string, and counts the number of "1"s

基准:

ruby-1.9.2-p180:001:0>> def h1(a, b)
ruby-1.9.2-p180:002:1*> ret = 0
ruby-1.9.2-p180:003:1*> xor = a ^ b
ruby-1.9.2-p180:004:1*> until xor == 0
ruby-1.9.2-p180:005:2*> ret += 1
ruby-1.9.2-p180:006:2*> xor &= xor - 1
ruby-1.9.2-p180:007:2*> end
ruby-1.9.2-p180:008:1*> ret
ruby-1.9.2-p180:009:1*> end
# => nil
ruby-1.9.2-p180:010:0>> def h2(a, b)
ruby-1.9.2-p180:011:1*> (a^b).to_s(2).count("1")
ruby-1.9.2-p180:012:1*> end
# => nil
ruby-1.9.2-p180:013:0>> h1(2323409845, 1782647144)
# => 17
ruby-1.9.2-p180:014:0>> h2(2323409845, 1782647144)
# => 17
ruby-1.9.2-p180:015:0>> quickbench(10**5) { h1(2323409845, 1782647144) }
Rehearsal ------------------------------------
   2.060000   0.000000   2.060000 (  1.944690)
--------------------------- total: 2.060000sec

       user     system      total        real
   1.990000   0.000000   1.990000 (  1.958056)
# => nil
ruby-1.9.2-p180:016:0>> quickbench(10**5) { h2(2323409845, 1782647144) }
Rehearsal ------------------------------------
   0.340000   0.000000   0.340000 (  0.333673)
--------------------------- total: 0.340000sec

       user     system      total        real
   0.320000   0.000000   0.320000 (  0.326854)
# => nil
ruby-1.9.2-p180:017:0>> 

这篇关于计算红宝石中汉明距离的最有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！