Cách hiệu quả nhất để tính toán khoảng cách hamming trong ruby?

Question

Trong ruby, cách hiệu quả nhất để tính toán sự khác biệt bit giữa hai số nguyên không dấu (ví dụ như khoảng cách hamming) là gì?

Ví dụ, tôi có số nguyên a = 2323409845 và b = 1782647144.

đại diện nhị phân của họ là:

a = 10001010011111000110101110110101 
b = 01101010010000010000100101101000 

Sự khác biệt chút giữa một & b là 17 ..

tôi có thể làm một XOR hợp lý trên chúng, nhưng điều đó sẽ cho tôi một số nguyên khác! = 17, sau đó tôi sẽ phải lặp qua biểu diễn nhị phân của kết quả và kiểm đếm số của 1s.

Cách hiệu quả nhất để tính chênh lệch bit là gì?

Bây giờ, câu trả lời có thay đổi để tính toán sự khác biệt bit của các chuỗi của nhiều int không? Ví dụ. cho 2 chuỗi số nguyên không dấu:

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

Cách hiệu quả nhất để tính chênh lệch bit giữa hai chuỗi là gì?

Bạn có lặp lại qua chuỗi hoặc có cách nhanh hơn để tính chênh lệch trên toàn bộ chuỗi cùng một lúc không?

Answer 1

Bạn có thể tận dụng các chức năng tối ưu hóa chuỗi trong Ruby để làm đếm bit, thay vì số học thuần túy. Nó nhanh hơn khoảng 6 lần với một số điểm chuẩn nhanh chóng.

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

h1 là cách thông thường để tính toán, trong khi h2 chuyển đổi xor vào một chuỗi, và đếm số "1" s

Benchmark:

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

Một thuật toán của 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 

Answer 3

mỗi đề nghị của mu là quá ngắn, tôi đã viết một phần mở rộng C đơn giản để sử dụng __builtin_popcount, và sử dụng điểm chuẩn xác minh rằng nó là ít nhất 3X nhanh hơn chức năng chuỗi tối ưu hóa của ruby ​​..

Tôi đã xem sau hai hướng dẫn:

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

Trong chương trình của tôi:

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

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

Sau đó, trong dir chứa chương trình của tôi, tôi có thể tạo một thư mục "PopCount" với những điều sau các tập tin.

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

Sau đó, trong thời gian thư mục popcount:

ruby ​​extconf.rb làm

Sau đó chạy chương trình, và có bạn có nó .... Cách nhanh nhất để làm khoảng cách Hamming trong ruby.

Answer 4

Nếu có ý định đi theo đường dẫn dựa trên c, bạn nên thêm cờ trình biên dịch -msse4.2 vào tệp makefile của mình. Điều này cho phép trình biên dịch tạo ra các hướng dẫn dựa trên phần cứng dựa trên popcnt thay vì sử dụng một bảng để tạo ra số lượng popcount. Trên hệ thống của tôi, tốc độ này nhanh hơn khoảng 2,5 lần.