¿La manera más eficiente de calcular la distancia de hamming en ruby?

Question

En ruby, ¿cuál es la forma más eficiente de calcular la diferencia de bits entre dos enteros sin signo (por ejemplo, la distancia hamming)?

Ej, tengo número entero a = 2323409845 y b = 1782647144.

Sus representaciones binarias son:

a = 10001010011111000110101110110101 
b = 01101010010000010000100101101000 

La diferencia poco entre la una & b es 17 ..

I puede hacer un XOR lógico en ellos, pero eso me dará un entero diferente! = 17, entonces tendría que iterar a través de la representación binaria del resultado y contar el número de 1s.

¿Cuál es la forma más eficiente de calcular la diferencia de bit?

Ahora, ¿cambia la respuesta para calcular la diferencia de bit de las secuencias de muchas ints? P.ej. dado 2 secuencias de enteros sin signo:

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

¿Cuál es la forma más eficiente para calcular la diferencia poco entre las dos secuencias?

¿Podrías repetir la secuencia, o hay una forma más rápida de calcular la diferencia a lo largo de toda la secuencia a la vez?

Answer 1

Usted puede hacer uso de las funciones de cadena optimizados en Ruby para hacer el recuento de bits, en lugar de la aritmética pura. Resulta ser aproximadamente 6 veces más rápido con un benchmarking rápido.

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

h1 es la manera normal para calcular, mientras que h2 convierte la XOR en una cadena, y cuenta el número de "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

Un algoritmo de 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

por la sugerencia de mu es demasiado corto, escribí una extensión C simple para usar __builtin_popcount, y al usar benchmark verifiqué que es al menos 3 veces más rápido que las funciones de cadena optimizadas de ruby ​​..

Miré el siguientes dos tutoriales:

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

En mi programa:

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

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

A continuación, en el directorio que contiene mi programa, crear una carpeta "PopCount" con la siguiente archivos.

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

A continuación, en el directorio de ejecución popcount:

rubí extconf.rb hacer

A continuación, ejecute el programa, y ​​ahí lo tienes .... manera más rápida de hacer distancia de Hamming en ruby

Answer 4

Si se tiene la intención de seguir la ruta basada en c, es una buena idea agregar la bandera del compilador -msse4.2 a su archivo MAKE. Esto permite que el compilador genere instrucciones basadas en hardware popcnt en lugar de usar una tabla para generar el conteo popcount. En mi sistema, esto fue aproximadamente 2.5 veces más rápido.