Il modo più efficiente per calcolare la distanza di Hamming in Ruby?

Question

In Ruby, qual è il modo più efficiente per calcolare la differenza di bit tra due numeri interi non firmati (ad esempio la distanza di keting)?

Ad esempio, ho un numero intero A = 2323409845 e b = 1782647144.

Le loro rappresentazioni binarie sono:

a = 10001010011111000110101110110101
b = 01101010010000010000100101101000

La differenza di bit tra A&B è 17 ..

Posso fare un logico XOR su di loro, ma questo mi darà un numero intero diverso! = 17, dovrei quindi iterare attraverso la rappresentazione binaria del risultato e calcolare il numero di 1.

Qual è il modo più efficiente per calcolare la differenza di bit?

Ora, la risposta cambia per il calcolo della differenza di bit di sequenze di molti INT? Ad esempio 2 sequenze di numeri interi non firmati:

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

Qual è il modo più efficiente per calcolare la differenza di bit tra le due sequenze?

Iterazione attraverso la sequenza o esiste un modo più veloce per calcolare la differenza nell'intera sequenza in una volta?

Answer 1

È possibile utilizzare le funzioni di stringa ottimizzate in Ruby per fare il conteggio dei bit, anziché aritmetica pura. Si rivela circa 6 volte più veloce con un rapido benchmarking.

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

H1 è il modo normale di calcolare, mentre H2 converte l'XOR in una stringa e conta il numero di "1" S

Prova delle prestazioni:

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

Per il suggerimento di MU è troppo breve, ho scritto una semplice estensione C per utilizzare __Builtin_PopCount e usando il benchmark verificato che è almeno 3x più veloce delle funzioni di stringa ottimizzate di Ruby.

Ho guardato i seguenti due tutorial:

• Estendendo Ruby con C
• Ruby Extension in C in 5 minuti

Nel mio programma:

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

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

Quindi nella Dir contenente il mio programma, creo una cartella "PopCount" con i seguenti file.

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

Quindi nella directory popcount:

Ruby ExtConf.rb Make

Quindi esegui il programma e il gioco è stato ... più veloce per fare la distanza di Hamming in Ruby.

Answer 3

Un algoritmo di 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 4

Se uno intende seguire il percorso basato su C, è una buona idea aggiungere il flag del compilatore -msse4.2 al tuo makefile. Ciò consente al compilatore di generare hardware basato su hardware popcnt Istruzioni invece di usare una tabella per generare il popcount. Sul mio sistema questo era circa 2,5 volte più veloce.