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

确保缓冲区始终是 long 的 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 回答