固定サイズの循環バッファーのインデックスを効率的にラップする方法

Question

固定サイズの循環バッファー（配列として実装されています）：初期化時に、バッファーには指定された最大数の要素が入れられます。円内の現在の位置を追跡するために単一の位置インデックスを使用します。

循環バッファ内の要素に効率的にアクセスするにはどうすればよいですか？ここに私の現在のソリューションされています

int GetElement(int index) 
{ 
    if (index >= buffer_size || index < 0) 
    { 
     // some code to handle the case 
    } 
    else 
    { 
     // wrap the index 
     index = end_index + index >= buffer_size ? (index + end_index) - buffer_size : end_index + index; 
    } 

    return buffer[index]; 
} 

いくつかの定義：
end_indexはすぐにサークル内の最後の要素の後の要素のインデックス（それも中START_INDEXと同じと考えられる、またはの最初の要素でありますサークル）。
buffer_sizeは、バッファの最大サイズです。

Answer 1

バッファの長さが常に2の累乗で、トップビットがマスクされていることを確認します。

Answer 2

int GetElement(int index) 
{ 
    return buffer[(end_index + index) % buffer_size]; 
} 

はmodulus operator (%)の詳細についてはmodulo operationを参照してください。

Answer 3

それはプロセッサに多少依存しますが、それはおそらく、少なくともreturn (end_index + index) % buffer_size;

Answer 4

FWIWような何かをしようとする価値がある、あなたが並列アレイ常に行うことができます：i = next[i];

をしかし、実際に、私はいつもてきましたこれは今までに大幅なパフォーマンスの問題である場合i++; if (i >= n) i = 0; OR

i = (i+1) % n;かかわらず、私は本当に驚いだろう：ちょうどこれが行わ。

Answer 5

I tested all 3 versions：

// plain wrap 
public static int WrapIndex(int index, int endIndex, int maxSize) 
{ 
    return (endIndex + index) > maxSize ? (endIndex + index) - maxSize : endIndex + index; 
} 

// wrap using mod 
public static int WrapIndexMod(int index, int endIndex, int maxSize) 
{ 
    return (endIndex + index) % maxSize; 
} 

// wrap by masking out the top bits 
public static int WrapIndexMask(int index, int endIndex, int maxSize) 
{ 
    return (endIndex + index) & (maxSize - 1); 
} 

パフォーマンスの結果は（ティック）：

Plain: 25 Mod: 16 Mask: 16 (maxSize = 512) 
Plain: 25 Mod: 17 Mask: 17 (maxSize = 1024) 
Plain: 25 Mod: 17 Mask: 17 (maxSize = 4096) 

だから、それはのサイズ上の任意の制限を必要としないため、弾性率は、より良い選択であると思われますバッファ。

Answer 6

私が作ってみたベストです：

public static int Wrap(int index, int n) 
{ 
    return ((index % n) + n) % n; 
} 

BUFFER_SIZEと等しくEND_INDEXされていない場合