circular-buffer - リング バッファ サイズが 2 の累乗でなければならないのはなぜですか?

Question

リング バッファ サイズが 2 の累乗でなければならないのはなぜですか?

Answer 1

以下に詳述する方法を使用するには、2 の累乗でなければなりません。それ以外である必要はありません。

一般的なアプローチは、"if (index >= size) { index = size - index; }" (サイズ 10、インデックス 10、結果のインデックスは 0) のようになります。これは、次のアプローチに比べて遅く、エラーが発生しやすくなります。

2 の累乗を使用すると、次の利点を活用できます。

size = 32
bin(size) => '00100000'

mask = size - 1;
bin(mask) => '00011111'

このマスクをビット単位の and で適用すると、インデックスが大きくなるにつれて、0 ～ 31 の範囲の数値を構成するビットのみを分離できます。

index = 4
bin(4 & mask) => '00000100' (4)

# index 32 wraps.  note here that we do no bounds checking, 
# no manipulation of the index is necessary.  we can simply 
# and safely use the result.
index = 32
bin(index & mask) => '00000000' (0)

index = 33
bin(index & mask) => '00000001' (1)

index = 64
bin(index & mask) => '00000000' (0)

index = 65
bin(index & mask) => '00000001' (1)

このアプローチは、比較や分岐を必要とせず、安全です (結果のインデックスは常に境界内にあります)。情報を破棄しないという追加の利点があります。インデックス 65 は要素 1 をアドレス指定しますが、インデックスが論理的に 65 であるという情報を保持しています (これは非常に有用です)。

また、これは、インデックスが 3456237 (バッファー内のアドレス 13) に成長した場合と、3 の場合と同じように効率的であることを付け加えたいと思います。

私はパーティーに遅れていることを知っています.どうやってこの質問を見つけたのかさえわかりません:-)これが役に立てば幸いです.