Le moyen le plus efficace de calculer la distance de Hamming dans Ruby?

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

  •  29-10-2019
  •  | 
  •  

Question

Dans Ruby, quel est le moyen le plus efficace de calculer la différence de bit entre deux entiers non signés (par exemple la distance de Hamming)?

Par exemple, j'ai entier A = 2323409845 et b = 1782647144.

Leurs représentations binaires sont:

a = 10001010011111000110101110110101
b = 01101010010000010000100101101000

La différence de bits entre l'A&B est de 17.

Je peux faire un XOR logique sur eux, mais cela me donnera un entier différent! = 17, je devrais alors itérer à travers la représentation binaire du résultat et compter le # de 1.

Quelle est la façon la plus efficace de calculer la différence de bit?

Maintenant, la réponse change-t-elle pour calculer la différence de bit de séquences de nombreux INT? Par exemple, compte tenu de 2 séquences d'entiers non signés:

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

Quelle est la façon la plus efficace de calculer la différence de bit entre les deux séquences?

Souhaitez-vous parcourir la séquence, ou y a-t-il un moyen plus rapide de calculer la différence à travers toute la séquence à la fois?

Était-ce utile?

La solution

Vous pouvez utiliser les fonctions de chaîne optimisées dans Ruby pour faire le comptage de bits, au lieu de l'arithmétique pure. Il s'avère que c'est environ 6 fois plus rapide avec une analyse comparative rapide.

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

H1 est le moyen normal de calculer, tandis que H2 convertit le XOR en une chaîne et compte le nombre de "1" S

Référence:

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

Autres conseils

Selon la suggestion de MU est trop courte, j'ai écrit une extension C simple pour utiliser __builtin_popcount, et l'utilisation de référence vérifiée qu'il est au moins 3x plus rapide que les fonctions de chaîne optimisées de Ruby.

J'ai regardé les deux tutoriels suivants:

Dans mon programme:

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

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

Ensuite, dans le DIR contenant mon programme, je crée un dossier "PopCount" avec les fichiers suivants.

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

Ensuite, dans le répertoire PopCount Run:

Ruby extconf.rb faire

Ensuite, exécutez le programme, et là vous l'avez ... le moyen le plus rapide de faire de la distance de Hamming dans Ruby.

Un algorithme 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 l'on a l'intention de suivre le chemin basé sur C, c'est une bonne idée d'ajouter le drapeau du compilateur -msse4.2 à votre makefile. Cela permet au compilateur de générer du matériel basé popcnt Instructions au lieu d'utiliser une table pour générer le popcount. Sur mon système, c'était environ 2,5 fois plus rapide.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top