Looping a través de bits en un número entero, ruby ​​

Question

Estoy haciendo un programa donde uno de los problemas es que tengo que hacer un análisis del patrón de bits en algunos enteros.

Debido a esto me gustaría ser capaz de hacer algo como esto:

#Does **NOT** work: 
num.each_bit do |i| 
    #do something with i 
end 

que era capaz de hacer algo que funciona, haciendo:

num.to_s(2).each_char do |c| 
    #do something with c as a char 
end 

Sin embargo, esto no tiene el rendimiento Me gustaría.

he encontrado que se puede hacer esto:

millones

0.upto(num/2) do |i| 
    #do something with n[i] 
end 

Esto tiene un rendimiento aún peor que el each_char método

Este circuito va a ser ejecutado de veces, o más, por lo que lo haría me gusta que sea lo más rápido posible.

Para referencia, aquí es la totalidad de la función

@@aHashMap = Hash.new(-1) 

#The method finds the length of the longes continuous chain of ones, minus one 
#(101110 = 2, 11 = 1, 101010101 = 0, 10111110 = 4) 

def afunc(n) 
if @@aHashMap[n] != -1 
    return @@aHashMap[n] 
end 

num = 0 
tempnum = 0 
prev = false 

(n.to_s(2)).each_char do |i| 
    if i 
     if prev 
      tempnum += 1 
      if tempnum > num 
       num = tempnum 
      end 
     else 
      prev = true 
     end 
    else 
     prev = false 
     tempnum = 0 
    end 
end 

@@aHashMap[n] = num 
return num 
end 

Answer 1

Para determinar la longitud de la secuencia más larga del consecutiva 1 de este es más eficiente:

def longest_one_chain(n) 
    c = 0 
    while n != 0 
    n &= n >> 1 
    c += 1 
    end 
    c 
end 

El método simplemente cuenta cuántas veces puede "Y a nivel de bit" el número consigo mismo desplazado 1 bit hacia la derecha hasta que sea cero.

Ejemplo:

    ______ <-- longest chain 
    01011011100001111110011110101010 c=0 
AND 0101101110000111111001111010101 
     1001100000111110001110000000 c=1, 1’s deleted 
AND  100110000011111000111000000 
      100000011110000110000000 c=2, 11’s deleted 
AND   10000001111000011000000 
        1110000010000000 c=3, 111’s deleted 
AND     111000001000000 
        110000000000000 c=4, 1111’s deleted 
AND     11000000000000 
         10000000000000 c=5, 11111’s deleted 
AND     1000000000000 
            0 c=6, 111111’s deleted 

Answer 2

Tenga en cuenta que O y "0" todos tienen un valor booleano de cierto en rubíes, por lo que "if i" no dará el resultado que se pretende .

La conversión de cada número a una cadena es, por supuesto, algo que uno debe evitar.

Fixnum tiene un método [] para acceder a los bits del número, por lo que esta tiene la oportunidad de ser más rápido.

Si ha intentado esto con

0.upto(num/2) do |i| 
    #do something with n[i] 
end 

continuación num/2 es probablemente demasiado grande, por lo que bucle con demasiada frecuencia.

Durante 32 bits enteros se debe utilizar

0.upto(31) do |i| 
    if n[i] == 1 
    ... 
    end 
end 

Answer 3

Rubí podría no ser una buena opción para su proyecto. La fuerza de rubí no es su rendimiento, pero que le permite hacer cosas como:

n.to_s(2).scan(/1+/).sort.last.length - 1 

en lugar de escribir código de montañas. Es probable que casi cualquier otro idioma funcione mejor si no te importa escribir código complejo (que no pareces).

Answer 4

Si está buscando rendimiento, la construcción de una tabla de consulta probablemente sea la forma más eficaz. Especialmente si usted está haciendo esto en un bucle estrecho:

class BitCounter 
    def initialize 
     @lookup_table = (0..65535).map { |d| count_bits(d) } 
    end 

    def count(val) 
     a,b,c = @lookup_table[val & 65535] 
     d,e,f = @lookup_table[val >> 16] 
     [a,b,c+d,e,f].max 
    end 

private 

    def count_bits(val) 
     lsb = lsb_bits(val) 
     msb = msb_bits(val) 
     [lsb, inner_bits(val, lsb, msb), msb] 
    end 

    def lsb_bits(val) 
     len = 0 
     while (val & 1 == 1) do 
      val >>= 1 
      len += 1 
     end 
     len 
    end 

    def msb_bits(val) 
     len = 0 
     while (val & (1<<15) == (1<<15)) do 
      val <<= 1 
      len += 1 
     end 
     len 
    end 

    def inner_bits(val, lsb, msb) 
     lens = [] 
     ndx = lsb 

     len = 0 
     (lsb+1..(15-msb)).each do |x| 
      if ((val & (1<<x)) == 0) 
       if(len > 0) 
        lens << len 
        len = 0 
       end 
      else 
       len += 1 
      end 
     end 
     lens.max || 0 
    end 
end 

Y a continuación, un ejemplo:

counter = BitCounter.new 
p counter.count 0b01011011100001111110011110101010 // 6 

Básicamente, esto crea una tabla loopup para todos los valores de 16 bits y, a continuación, calcula el resultado más grande de las valores almacenados en caché Puede incluso combinar la forma más expresiva de n.to_s(2).scan(/1+/).sort.last.length - 1 en lugar de hacer lógica bit a bit en la inicialización de la tabla, ya que ya no es el cuello de botella, aunque me quedaría con las matemáticas bit a bit solo por claridad de expresión en lugar . Cada mirar hacia arriba sólo cuesta 2 sube la tabla de consulta, una suma y una max

Answer 5

en Ruby, Integer s (es decir, ambos Bignum s y Fixnum s) ya pueden ser indexados como si fueran las matrices de bits. Sin embargo, no son Enumerable.

Pero se puede arreglar eso, por supuesto:

class Integer 
    include Enumerable 

    def each 
    return to_enum unless block_given?  
    (size*8).times {|i| yield self[i] } 
    end 
end 

Una forma un poco menos intrusivo podría ser para representar el Integer como una matriz:

class Integer 
    def to_a 
    Array.new(size*8, &method(:[])) 
    end 
end 

continuación, puede utilizar ingeniosas Enumerable métodos de Ruby :

0b10111110.chunk {|b| true if b == 1 }.map(&:last).max_by(&:size).size - 1 

(O 0b10111110.to_a.chunk … i Si prefiere el método menos intrusivo)

Si le preocupa el rendimiento, el motor de ejecución que elija hace una gran diferencia. El compilador optimizador de Rubinius o JRuby puede ser capaz de alinear y optimizar muchas llamadas a métodos que el compilador simple de YARV no puede, por ejemplo. El tratamiento especial de YARV de Fixnum puede darle una ventaja sobre la MRI.

Como puede ver en los ejemplos, soy un gran admirador del estilo sin puntos y la programación funcional. Si puede probar a través del perfil que tiene un cuello de botella en un punto específico en el código, puede necesitar reemplazarlo con una versión ligeramente menos elegante o impura, o si lo desea, puede fusionar a mano el map y el max_by.

class Integer 
    def to_a 
    Array.new(size*8) {|i| self[i] } 
    end 
end 

0b10111110.chunk {|b| true if 1 == b }.map {|key, chunk| chunk.size }.max - 1 

o

0b10111110.chunk {|b| true if 1 == b }.max_by {|key, chunk| chunk.size }.last.size - 1 

Answer 6

A veces el uso de cadenas es el método más obvio, y el rendimiento es tolerable:

def oneseq(n) 
    n.to_s(2).split(/0+/).sort_by(&:length).last.to_s.length 
end