12

我正在制作一个程序，其中一个问题是我需要对某些整数中的位模式进行一些分析。

因此，我希望能够做这样的事情：

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

8 回答 8

12

要确定连续 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
于 2012-06-06T21:23:36.060 回答
4

Ruby 可能不是您项目的好选择。ruby 的优势不在于它的性能，而在于它可以让您执行以下操作：

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

而不是编写堆积如山的代码。如果您不介意编写复杂的代码（您似乎不介意），那么几乎任何其他语言都可能表现得更好。

于 2012-06-06T10:42:04.080 回答
3

请注意，o 和“0”在 ruby​​ 中都有一个布尔值 true，因此“ if i”不会给出您想要的结果。

将每个数字转换为字符串当然是应该避免的。

Fixnum有一种[]访问数字位的方法，因此有机会更快。

如果你试过这个

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

thennum/2可能太大了，所以你循环太频繁了。

对于 32 位整数，您应该使用

0.upto(31) do |i|
   if n[i] == 1
     ...
   end
end
于 2012-06-06T10:19:28.480 回答
3
于 2012-06-06T14:59:42.597 回答
1

有时使用字符串是最明显的方法，性能尚可：

def oneseq(n)
  n.to_s(2).split(/0+/).sort_by(&:length).last.to_s.length
end
于 2012-06-06T16:14:30.213 回答
1

如果您正在寻找性能，那么构建查找表可能是最高效的方式。特别是如果您在一个紧密的循环中执行这些操作：

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

于 2012-06-06T14:48:18.897 回答
0

算法

人们可能会考虑使用二分搜索。我已经实现了以下算法来确定给定非负整数中最长 1 位字符串的长度n。计算复杂度为 O(· n)，但对于许多值，n它将接近 O(log 2 ( · n))。

该算法的步骤如下，但许多读者发现它们更容易通过首先阅读以下部分（“插图”）来理解。

  1. 设置longest为0。
  2. 设置等于( )len中的位数。nlen = n.bit_length
  3. 如果len <= 2，则返回答案（0，1或2）。
  4. 确定(或)mid中间位的索引。nmid = len/2mid = len >> 1
  5. 设置ri = mid+1和li = mid-1。
  6. 如果中间位 ( n[mid]) 的值为零，则转到步骤 10。
  7. （n[mid] = 1达到这一步。）确定最大索引li >= mid和最小索引ri <= mid，使得n[i] = 1所有ri <= i <= li.
  8. 设置和。longest = [longest, ri-li+1].max_li += 1ri -= 1
  9. 如果li == len转到步骤 10；否则设置ln等于​​由索引li（最低有效）到len-1（最高有效）处的位组成的数量。递归设置为n并ln转到步骤 2。这将返回数字ln( cand) 中最长的 1 位字符串。设置longest = [longest, cand].max。
  10. 如果ri < 0进行步骤11；否则设置rn等于​​由索引0（最低有效）到ri（最高有效）处的位组成的数量。递归设置为n并rn转到第 2 步。这将返回第一个数字中最长的 1 位字符串rn (candlonglong ). Set= [longest, cand].max`。
  11. longest在递归中返回。

插图

认为

n = 0b1010011011101011110
  #=> 341854

然后

len = n.bit_length
  #=> 19
mid = len >> 1
  #=> 9
n[mid]
  #=> 1
longest = 0

我们可以n如下图

101001101 1 101011110

中间位1突出的地方。因为它是 a 1，所以我们向左和向右寻找 1 的序列。我们得到以下。

10100110 111 01011110

当我们找到三个 1 时，我们更新longest.

longest = [longest, 3].max
  #=> [0, 3].max => 3

我们现在必须检查0b10100110和0b1011110（第二个数字中的前导零丢失）。

对于左边的数字，我们计算如下。

n = 0b10100110
len = n.bit_length
  #=> 8
mid = len >> 1
  #=> 4
n[mid]
  #=> 0

所以我们有

101 0 0110

（注意n[0]是最不重要的位）。我们可以排除0b101和0b110，因为两者都有3位，不超过 的当前值longest，即3。

现在我们考虑右半部分，

n = 0b1011110
len = n.bit_length
  #=> 7
mid = len >> 1
  #=> 3
n[mid]
  #=>1

所以我们有

101 1 110

作为n[mid] #=> 1，我们左右查找 1 的字符串并获得

10 1111 0

由于我们发现了一个41 的刺，我们设置

longest = [longest, 4].max
  #=> [3, 4].max = 4

2最后我们看到左边 ( ) 和右边 ( )的位数1都小于3，所以我们完成了，返回longest #=> 4。（OP 实际上想要longest - 1 #=> 3，我们认为这是一个侧面计算。）

代码

def longest_run(n, longest=0)
  len = n.bit_length
  return [longest, (n & 1) + (n >> 1)].max if len <= 2
  mid = len >> 1
  ri = mid-1
  li = mid+1
  if n[mid] == 1
    until n[ri] == 0
      ri -= 1
    end
    until n[li] == 0
      li += 1
    end
    cand = li-ri-1
    longest = cand if cand > longest
  end
  if ri >= 0
    shift = ri+1
    m = n ^ ((n >> shift) << shift)
    if m.bit_length > longest 
      cand = longest_run(m, longest) 
      longest = cand if cand > longest
    end
  end
  if li <= len - 1
    m = n >> li
    if m.bit_length > longest 
      cand = longest_run(m, longest) 
      longest = cand if cand > longest
    end
  end
  longest
end

例子

longest_run 341854
  #=> 4
longest_run 0b1011110011111000000111100011101111011110
  #=> 5
longest_run 0b101111001111100000011110001110111111011111
  #=> 6
longest_run 2**500_000-1
  #=> 500000
longest_run ("10"*100_000).to_i(2)
  #=> 1
于 2018-10-08T06:08:31.153 回答
0

这里有几个更直接的方法（尽管我希望@Steven 的回答和我的其他回答会更有效）。

#1

def max_string_of_ones(n)
  max_length = 0
  cand = 0
  (0..n.bit_length).reduce(0) do |max_length, i|
    if n[i] == 1
      cand += 1
    else
      max_length = cand if cand > max_length
      cand = 0
    end
    max_length
  end
end

注意n[n.bit_length] #=> 0。

#2

第二种方法使用 Ruby 的触发器操作符。另外，我想，“如果Integer有一个each_bit返回枚举数的方法不是很方便吗？”，所以我添加了一个。

class Integer
  def each_bit
    Enumerator.new do |yielder|
      if block_given?      
        bit_length.times { |i| yielder << yield(self[i]) }
      else
        bit_length.times { |i| yielder << self[i] }
      end
    end
  end
end

def max_string_of_ones(n)
  n.each_bit.slice_before { |b| true if b==0 .. b==1 }.max_by(&:size).size
end

max_string_of_ones(0b1100011101111011100)
  #=> 4

请注意以下中间计算。

def max_string_of_ones(n)
  n.each_bit.slice_before { |b| true if b==0 .. b==1 }
end

enum = max_string_of_ones(0b1100011101111011100)
  #=> #<Enumerator: #<Enumerator::Generator:0x00000000019a2f80>:each>
enum.to_a
  #=> [[0], [0], [1, 1, 1], [0], [1, 1, 1, 1], [0],
  #    [1, 1, 1], [0], [0], [0], [1, 1]]
于 2018-10-08T20:32:59.023 回答