本文介绍了计算红宝石中汉明距离的最有效方法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

在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>>

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

09-06 06:16