루비에서 해밍 거리를 계산하는 가장 효율적인 방법은 무엇입니까?

https://stackoverflow.com/questions/6395165

29-10-2019
|

문제

Ruby에서 부호 없는 두 정수 사이의 비트 차이를 계산하는 가장 효율적인 방법은 무엇입니까(예:해밍 거리)?

예를 들어, 정수 a = 2323409845 및 b = 1782647144가 있습니다.

이진 표현은 다음과 같습니다.

a = 10001010011111000110101110110101
b = 01101010010000010000100101101000

a와 b의 비트 차이는 17입니다.

논리적 XOR을 수행할 수 있지만 그러면 다른 정수(!= 17)가 제공됩니다. 그런 다음 결과의 이진 표현을 반복하고 1의 개수를 계산해야 합니다.

비트 차이를 계산하는 가장 효율적인 방법은 무엇입니까?

이제 많은 정수 시퀀스의 비트 차이를 계산하는 답이 바뀌나요?예:부호 없는 정수의 2개 시퀀스가 주어졌습니다.

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

두 시퀀스 간의 비트 차이를 계산하는 가장 효율적인 방법은 무엇입니까?

시퀀스를 반복하시겠습니까, 아니면 전체 시퀀스의 차이를 한 번에 계산할 수 있는 더 빠른 방법이 있습니까?

해결책

순수한 산술 대신에 비트 카운팅을 수행하기 위해 루비에서 최적화 된 문자열 기능을 사용할 수 있습니다.그것은 빠른 벤치마킹으로 약 6 배 빠른 것으로 밝혀졌습니다.

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

h1은 계산하는 정상적인 방법이며, H2는 XOR을 문자열로 변환하고 "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>>

다른 팁

MU의 제안이 너무 짧아서 __builtin_popcount를 사용하기위한 간단한 C 확장자를 썼고 벤치 마크를 사용하여 Ruby의 최적화 된 문자열 함수보다 적어도 3 배 빠른 것으로 확인되었습니다.

다음 두 자습서를 보았습니다.

C로 루비 확장

내 프로그램에서 :

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

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

다음 내 프로그램이 들어있는 디렉토리에서 다음 파일을 사용하여 폴더 "팝콘"폴더를 만듭니다.

exconf.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)));
}

그런 다음 팝콘 디렉토리가 실행됩니다.

Ruby Extconf.rb. 만들기

그런 다음 프로그램을 실행하고 있습니다. 루비에서 캠핑 거리를 캠핑 할 수있는 가장 빠른 방법입니다.

wegner의 알고리즘 :

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

C 기반 경로를 따르려는 경우 컴파일러 플래그를 추가하는 것이 좋습니다. -msse4.2 귀하의 메이크 파일에.이를 통해 컴파일러는 하드웨어 기반의 생성을 수행할 수 있습니다. popcnt popcount를 생성하기 위해 테이블을 사용하는 대신 지침.내 시스템에서는 약 2.5배 더 빨랐습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow