Зацикливание через биты в целое число, рубин

Ответ 1

Чтобы определить длину самой длинной последовательности последовательных 1, это более эффективно:

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

Метод просто подсчитывает, сколько раз вы можете "побитовое" число, которое само сдвинуло 1 бит вправо, пока оно не станет нулевым.

Пример:

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

Ответ 2

Помните, что o и "0" имеют логическое значение true в ruby, поэтому "if i" не даст результат, который вы намеревались.

Преобразование каждого числа в строку - это, конечно, то, чего следует избегать.

Fixnum имеет метод [] для доступа к битам числа, поэтому это может быть быстрее.

Если вы пробовали это с помощью

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

то num/2, вероятно, слишком большой, поэтому вы слишком часто зацикливаетесь.

Для 32-битных целых чисел вы должны использовать

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

Ответ 3

В Ruby Integer (то есть оба Bignum и Fixnum s) уже могут быть проиндексированы, как если бы они были бит-массивами. Они, однако, не Enumerable.

Но вы можете это исправить, конечно:

class Integer
  include Enumerable

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

Несколько менее интрузивным способом может быть представление Integer в виде массива:

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

Затем вы можете использовать методы Ruby nifty Enumerable:

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

(Или 0b10111110.to_a.chunk …, если вы предпочитаете менее интрузивный метод.)

Если вы беспокоитесь о производительности, механизм выполнения, который вы выбираете, имеет большое значение. Оптимизирующий компилятор Rubinius или JRuby может встраивать и оптимизировать многие вызовы методов, которые, например, YARV довольно простой компилятор. Специальное лечение YARV Fixnum может дать ему преимущество перед МРТ.

Как вы можете видеть из примеров, я являюсь большим поклонником бессмысленного стиля и функционального программирования. Если вы можете доказать с помощью профилирования, что у вас есть узкое место в определенной точке кода, вам может потребоваться заменить его чуть менее изящной или нечистой версией, или вы можете использовать предохранители map и 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

или

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

Ответ 4

Ruby не может быть хорошим выбором для вашего проекта. Сила рубина - это не производительность, а то, что он позволяет вам делать такие вещи, как:

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

вместо написания гор кода. На самом деле почти любой другой язык, скорее всего, будет работать лучше, если вы не возражаете писать сложный код (который вам кажется не так).

Ответ 5

Если вы ищете производительность, то построение справочной таблицы, вероятно, будет наиболее эффективным. Особенно, если вы делаете это в плотной петле:

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

И затем пример:

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

В основном это создает таблицу циклов для всех 16-битных значений, а затем вычисляет наибольший результат из этих кешированных значений.

Вы даже можете комбинировать более выразительную форму n.to_s(2).scan(/1+/).sort.last.length - 1, а не выполнять побитную логику в инициализации таблицы, поскольку она больше не является узким местом, хотя я бы придерживался побитовой математики только для ясности выражения, а не для строки разбор. Каждый поиск может стоить всего 2 таблицы, один добавочный и max

Ответ 6

Иногда использование строк является наиболее очевидным методом, и производительность допустима:

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