计算红宝石汉明距离最有效的方法？

Question

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

例如,我有一个整数a = 2323409845和b = 178264714​​4.

他们的二进制表示是:

a = 10001010011111000110101110110101
b = 01101010010000010000100101101000

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

我可以对它们进行逻辑XOR,但这会给我一个不同的整数!= 17,然后我必须迭代结果的二进制表示并计算#s的1.

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

现在,答案是否会改变以计算许多整数序列的比特差异？例如,给定2个无符号整数序列:

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

计算两个序列之间的比特差异的最有效方法是什么？

你会迭代序列,还是有更快的方法来计算整个序列的差异？

Answer 1

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

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

h1是计算的常规方法,而h2将xor转换为字符串,并计算"1"的数量

基准测试:

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

Answer 2

根据mu的建议太短,我写了一个简单的C扩展来使用__builtin_popcount,并使用基准测试验证它至少比ruby的优化字符串函数快3倍.

我查看了以下两个教程:

• 使用C扩展Ruby
• 在5分钟内在C语言中进行Ruby扩展

在我的计划中:

require './FastPopcount/fastpopcount.so'
include FastPopcount

def hamming(a,b)
  popcount(a^b)
end

然后在包含我的程序的目录中,我使用以下文件创建一个文件夹"PopCount".

extconf.rb:

# Loads mkmf which is used to make makefiles for Ruby extensions
require 'mkmf'

# Give it a name
extension_name = 'fastpopcount'

# The destination
dir_config(extension_name)

# Do the work
create_makefile(extension_name)

popcount.c:

// Include the Ruby headers and goodies
#include "ruby.h"

// Defining a space for information and references about the module to be stored internally
VALUE FastPopcount = Qnil;

// Prototype for the initialization method - Ruby calls this, not you
void Init_fastpopcount();

// Prototype for our method 'popcount' - methods are prefixed by 'method_' here
VALUE method_popcount(int argc, VALUE *argv, VALUE self);

// The initialization method for this module
void Init_fastpopcount() {
    FastPopcount = rb_define_module("FastPopcount");
    rb_define_method(FastPopcount, "popcount", method_popcount, 1); 
}

// Our 'popcount' method.. it uses the builtin popcount
VALUE method_popcount(int argc, VALUE *argv, VALUE self) {
    return INT2NUM(__builtin_popcount(NUM2UINT(argv)));
}

然后在popcount目录下运行:

ruby extconf.rb make

然后运行程序,你就拥有它......在红宝石中做汉明距离的最快方法.