0

次のアルゴリズムを使用してストリームからデータを読み取る必要があります。

-ストリームからのすべての連続するセットビット（「1」）をカウントします。

-次に、ストリームからさらにkビットを読み取ります。Kは可変であり、プログラム全体で変化します。読み取ったデータを「m」と呼びましょう

デコードされた番号は次のようになります

number = (consecutive_set_bits << k) + m;

このアルゴリズムは非常に多くの回数実行されます。このため、このコードをできるだけ高速にすることが重要です。

主な問題は、1バイト、2バイト、4バイトなどのセットのコード化された数値の数が可変であるため、簡単な実装（現在頭にある唯一の実装）では、単一の読み取りを行うループが必要になることです。ストリームからのビット。最悪の場合、1つのコード化された係数に対してループ全体で14回の反復があります。

どういうわけかこのループを回避できますか？

4

1 に答える 1

0

シングルビットを順番に抽出するという考え方はそれほど悪くありません。正しく実行されれば、他のソリューションとほぼ同じくらい高速になる可能性があります。

粒度gのストリーム内の任意の位置にあるビットシーケンス（たとえば、 （16ビット）wordsのストリームの場合はg = 16）は、サイズgのブロックでブロック単位で処理できます。

sストリームからe（を使用して）の位置にあるビットを(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、最終結果に含めるだけです。

（データのエンディアンに注意してください:)）

これが本当に物事をスピードアップするかどうかは、一般的に決定することはできません。（処理されるデータ、基盤となるコンピューティングハードウェア、使用されるコンパイラによって異なります。＆c。いくつかの除算と1つのモジュロ演算が必要であり、アルゴリズムの速度が大幅に低下する可能性があることに注意してください。）

ビットを1つずつ抽出することは、同じ方法で非常に効率的に行うことができます。例えば：

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

もちろん、これを最適化して、の再計算を回避しblockIndex、が常に1だけインクリメントされる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

まとめると、次のようになります。

一般的なケースでは、ソリューションはビット読み取りごとに1回のループ反復よりも効率的であり、最適化によってパフォーマンスが一方向または他方向にわずかに変化するだけだとは思いません。

于 2012-12-12T14:39:49.380 に答える