ルビ整数でビットをループする

Question

私はいくつかの整数のビットパターンの分析をする必要があるという問題の一つがあるプログラムを作っています。

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

私が行うことで、働く何かを作ることができました：

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

これが持っていない私は、このような何かをできるようにしたいと思います。このため

の性能私はしたいと思います。

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

これは、このループが実行数百万回、またはそれ以上であることを行っているので、私は希望each_char方法

よりもさらに悪いパフォーマンスを持っている：あなたがこれを行うことができますことを私が発見した

できるだけ速くなるように。参考のため、ここでの機能の全体

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

連続する1の最長シーケンスの長さを決定するために、このより効率的です：

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

このメソッドは、単純に何回右に1ビットシフトされた数をゼロになるまで「ビット単位でAND」することができるかを数えます。

例：

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

はOと「0」すべてがルビーで真のブール値を持っているので、「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 

Answer 3

はRubyがあなたのプロジェクトのための良い選択ではないかもしれません使用する必要があります。

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

代わりにコードの山々を書く：ルビーの 強さは、それがパフォーマンスだが、それはあなたがのようなものを行うことができますということではありません。あなたが複雑なコードを書くのを気にしないならば、他のどの言語についても、実際にはより良い結果を出すでしょう。

Answer 4

パフォーマンスを探している場合は、ルックアップテーブルを作成するのが最も効果的な方法でしょう。これは、基本的にすべての16ビット値のためloopupテーブルを作成し、それらからの最大の結果を計算

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

：特にあなたがタイトループ内でこれらを行っている場合：

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 

をそして例キャッシュされた値。

文字列の解析ではなく式の分かりやすさのために、ビットワイズの計算に固執しますが、表の初期化でビット論理を使用するのではなく、より表現力豊かな形式を組み合わせることもできます。各のみ2つのテーブル・ルックアップ、1つの添加およびRubyでmax

Answer 5

コストルックアップそれらはビット列であるかのように、Integer S（すなわちBignum sおよびFixnumの両方）が既に索引付けすることができます。しかし、それらはEnumerableではありません。

しかし、あなたは、もちろん、それを修正することができます。

class Integer 
    include Enumerable 

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

Aやや控えめな方法は、配列としてIntegerを表現するために次のようになります。

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

その後、あなたはRubyの気の利いたEnumerableメソッドを使用することができます：

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

（または0b10111110.to_a.chunk …あなたがより侵入の少ない方法を好む場合）

パフォーマンスが心配な人は、選択した実行エンジンが大きな違いになります。 RubiniusやJRubyの最適化コンパイラは、YARVの単純なコンパイラではできない多くのメソッド呼び出しをインライン化して最適化することができます。 YARVの特殊治療Fixnumは、MRIよりも優れているかもしれません。

例からわかるように、私はポイントフリーのスタイルと機能プログラミングの大ファンです。コードの特定のポイントでボトルネックが発生していることをプロファイリングで証明できる場合は、若干エレガントで不純なバージョンに置き換えるか、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 

Answer 6

時には文字列を使用すると、最も明白な方法であり、そしてパフォーマンスが許容される：

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