5

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

循環バッファ内の要素にアクセスする効率的な方法は何ですか? これが私の現在の解決策です：

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バッファの最大サイズです。

4

6 に答える 6

18

私が思いついた最高のものは次のとおりです。

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

（負の数で作業する必要があると仮定します）

于 2012-04-17T03:43:34.470 に答える
11

バッファが常に2の累乗であることを確認し、上位ビットをマスクします。

于 2011-02-01T21:25:25.830 に答える
6

3つのバージョンすべてをテストしました：

// 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)

したがって、バッファのサイズに制限を必要としないため、モジュラスの方が適しているようです。

于 2011-02-05T07:13:33.020 に答える
5

プロセッサによって多少異なりますが、少なくとも次のようなものを試す価値はあります。return (end_index + index) % buffer_size;

于 2011-02-01T21:27:00.160 に答える
4 
int GetElement(int index)
{
    return buffer[(end_index + index) % buffer_size];
}

モジュラス演算子（）の詳細については、モジュロ演算を参照してください。%

于 2011-02-01T21:25:18.783 に答える
0

FWIW、いつでも並列配列を実行できます：i = next[i];

しかし、実際には、私はいつもこれを行ってきました:i++; if (i >= n) i = 0; またはi = (i+1) % n;

とにかく、これが重大なパフォーマンスの問題になるとしたら、私は本当に驚かれることでしょう。

于 2011-02-02T18:38:08.720 に答える