¿La forma más eficiente de calcular la distancia de Hamming en Ruby?

StackOverflow https://stackoverflow.com/questions/6395165

  •  29-10-2019
  •  | 
  •  

Pregunta

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 de Hamming)?

Por ejemplo, tengo el número entero a = 2323409845 y b = 1782647144.

Sus representaciones binarias son:

a = 10001010011111000110101110110101
b = 01101010010000010000100101101000

La diferencia de bits entre a y b es 17.

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

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

Ahora bien, ¿cambia la respuesta para calcular la diferencia de bits de secuencias de muchos enteros?P.ej.dadas 2 secuencias de enteros sin signo:

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

¿Cuál es la forma más eficaz de calcular la diferencia de bits entre las dos secuencias?

¿Repetirías la secuencia o hay una forma más rápida de calcular la diferencia en toda la secuencia a la vez?

¿Fue útil?

Solución

Puede utilizar las funciones de cadena optimizadas en Ruby para hacer el conteo de bits, en lugar de la aritmética pura. Resulta ser aproximadamente 6 veces más rápido con una nueva evaluación comparativa.

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

H1 es la forma normal de calcular, mientras que H2 convierte el XOR en una cadena, y cuenta el número de "1" S

Punto de referencia:

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>>

Otros consejos

Según la sugerencia de mu es demasiado corta, escribí una extensión C simple para usar __builtin_popcount y, usando el punto de referencia, verifiqué que es al menos 3 veces más rápido que las funciones de cadena optimizadas de Ruby.

Miré los siguientes dos tutoriales:

En mi programa:

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

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

Luego, en el directorio que contiene mi programa, creo una carpeta "PopCount" con los siguientes 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)));
}

Luego, en el directorio popcount, ejecute:

ruby extconf.rb make

Luego ejecuta el programa y ahí lo tienes... la forma más rápida de realizar distancias de Hamming en Ruby.

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

Si uno tiene la intención de seguir la ruta basada en C, es una buena idea agregar la bandera del compilador -msse4.2 a tu makefile. Esto permite que el compilador genere hardware popcnt Instrucciones en lugar de usar una tabla para generar el PopCount. En mi sistema, esto fue aproximadamente 2.5 veces más rápido.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top