13

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

たとえば、整数a=2323409845およびb=178264714​​4があります。

それらのバイナリ表現は次のとおりです。

a = 10001010011111000110101110110101
b = 01101010010000010000100101101000

aとbのビット差は17です。

それらに対して論理XORを実行できますが、それによって別の整数！= 17が得られます。次に、結果のバイナリ表現を反復処理して、1の数を集計する必要があります。

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

さて、多くのintのシーケンスのビット差を計算するための答えは変わりますか？たとえば、符号なし整数の2つのシーケンスが与えられた場合：

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

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

シーケンスを反復処理しますか、それともシーケンス全体の差を一度に計算するより高速な方法がありますか？

4

4 に答える 4

22

純粋な算術演算の代わりに、Rubyで最適化された文字列関数を使用してビットカウントを行うことができます。いくつかの迅速なベンチマークを行うと、約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>>
于 2011-06-18T15:47:53.957 に答える
5

muの提案が短すぎるため、__ builtin_popcountを使用する単純なC拡張機能を作成し、ベンチマークを使用して、rubyの最適化された文字列関数よりも少なくとも3倍高速であることを確認しました。

次の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.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

次に、プログラムを実行すると、ルビーでハミング距離を実行する最速の方法が得られます。

于 2011-06-19T01:29:24.253 に答える
3

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

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
于 2011-06-18T15:33:54.213 に答える
1

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

于 2017-08-14T14:13:17.047 に答える