ルビーのハミング距離を計算する最も効率的な方法は？

Question

ルビでは、2つの符号なし整数間のビット差（ハミング距離など）を計算する最も効率的な方法は何ですか？

例えば、Iは、整数A = 2323409845およびbを有する= 178264714​​4.

そのバイナリ表現は、次のとおり

a = 10001010011111000110101110110101 
b = 01101010010000010000100101101000 

& Bとのビット差は17である..

Iそれらの論理XORを行うことができますが、それは私に別の整数を与える！= 17、私は結果のバイナリ表現を反復し、＃の1を集計する必要があります。

ビット差を計算する最も効率的な方法は何ですか？

ここで、多くのintのシーケンスのビット差を計算する答えが変わるのですか？例えば。符号なし整数の2つのシーケンスを指定します。

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

2つのシーケンスのビット差を計算する最も効率的な方法は何ですか？

シーケンスを繰り返したり、シーケンス全体の差を一気に計算する方法はありますか？

Answer 1

あなたが代わりに純粋な算術、ビットカウントを行うにはRubyで最適化された文字列関数を使用することができます。いくつかの迅速なベンチマークによって約6倍の速さであることが判明しました。

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

H1はH2が文字列に排他的論理和を変換しながら、計算する通常の方法で、数をカウントする「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

ウェグナーのアルゴリズム：

def hamm_dist(a, b) 
    dist = 0 
    val = a^b 

    while not val.zero? 
    dist += 1 
    val &= val - 1 
    end 
    dist 
end 

p hamm_dist(2323409845, 1782647144) # => 17 

Answer 3

muが短すぎる場合は、__builtin_popcountを使用するシンプルなC拡張モジュールを作成し、ベンチマークを使用して、ルビの最適化された文字列関数より少なくとも3倍高速であることを確認しました..

私のプログラムで

• Extending Ruby With C
• Ruby Extension in C in 5 min

：2つのチュートリアル以下

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。ハミング距離を行うには

ルビーextconf.rbは 作る

その後、プログラムを実行し、そしてそこにあなたがそれを持っている....最速の方法：C：POPCOUNTディレクトリの実行で次に

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

ルビーで。

Answer 4

cベースのパスに従う場合は、コンパイラフラグ-msse4.2をメイクファイルに追加することをお勧めします。これにより、コンパイラは、テーブルを使用してポップカウントを生成する代わりに、ハードウェアベースのpopcnt命令を生成することができます。私のシステムでは、これは約2.5倍速かった。