在整數中循環遍歷，ruby

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位，直到它爲零。

例子：

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

紅寶石可能不適合你的項目一個不錯的選擇。 紅寶石的實力是不是它的性能而是它可以讓你做這樣的事情：

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

，而不是寫代碼的山區。如果您不介意編寫複雜的代碼（您似乎並不這麼認爲），那麼其他任何語言都可能會表現得更好。

Answer 4

如果您正在尋找性能，那麼構建查找表可能是最高效的方法。特別是如果你在一個緊湊的循環做這些：

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個值的loopup表，然後計算從那些最大的結果緩存的值。

你甚至可以結合的n.to_s(2).scan(/1+/).sort.last.length - 1更表現形式，而不是你的表初始化做逐位的邏輯，因爲它不再是瓶頸點 - 雖然我會按位數學堅持只是爲了表達清晰，而不是字符串解析。每個查找僅花費2個表查找窗口，一個加法和一個max

Answer 5

在Ruby，Integer S（即兩個Bignum S和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的漂亮Enumerable方法：

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

（或0b10111110.to_a.chunk … i如果您對性能感到擔憂，那麼您選擇的執行引擎會有很大的不同。例如，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