0

我需要使用以下算法从流中读取数据：

-从流中计算所有连续的设置位（“1”）。

- 然后，从流中读取更多位。K 是可变的，并且在整个程序中都会发生变化。让我们将读取的数据称为“m”

解码后的数字是

number = (consecutive_set_bits << k) + m;

这个算法被执行了很多次。正因为如此，这段代码尽可能快是至关重要的。

主要问题是 1 字节、2 字节、4 字节等集合中的编码数字的数量是可变的，因此一个简单的实现（我现在脑子里只有一个）需要一个读取单字节的循环来自流的位。在最坏的情况下，对于一个编码系数，我在循环中进行了 14 次迭代。

我能以某种方式避免这个循环吗？

4

1 回答 1

0

顺序提取单个位的想法还不错。如果做得好，它可能几乎与任何其他解决方案一样快。

粒度为g的流中任意位置的位序列，例如对于（16 位）words 的流，g=16，可以在大小为 g 的块上逐块处理。

s要从流中提取通过e(with )位置的位(e - s) <= g作为“右对齐”数字，示例实现可能是：

shift = s % g

lowerBits = data[ floor( s / g ) ] >> shift
upperBits = data[ floor( e / g ) ] << (g - shift)

bitSequence = (lowerBits | upperBits) & ( (1 << (e-s)) -1 )[*]

[*] 这最后一项只是掩盖了我们可能得到的任何不需要的高位，并将它们0放在最终结果中。

（注意数据的字节顺序:)）

这是否真的会加快速度通常无法确定。（取决于正在处理的数据、底层计算硬件、使用的编译器等。请注意，需要一些除法和一次模运算，这可能会显着减慢算法速度。）

可以以相同的方式非常有效地逐个提取位。例如：

blockIndex = floor( bitPosition / g )
bitIndex = bitPosition % g
nextBit = (data[ blockIndex ] >> bitIndex) & 1

这当然可以优化以避免重新计算blockIndex以及bitIndex如果和何时bitPosition总是只增加 1。

另一种常见的方法是使用变量“掩码”来提取单个位：

mask = 1
index = 0
while ( not all bits read ) { 
  block = data[index]
  if ( mask & block != 0 ) {
    // a 1 was encountered
  } else {
    // a 0 was encountered
  }
  mask = mask << 1
  if ( mask == 0 ) {
    mask = 1
    index = index + 1
  }
}

请注意如何mask使用它来屏蔽当前位并跟踪何时前进到下一个数据块。为此mask，当然必须与g数据块具有相同的宽度。

总结一下：

我认为，在一般情况下，该解决方案不会比每次读取一次循环迭代更有效，并且任何优化只会稍微改变一个方向或另一个方向的性能。

于 2012-12-12T14:39:49.380 回答