java 如何有效地包装固定大小的循环缓冲区的索引
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4868049/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to efficiently wrap the index of a fixed-size circular buffer
提问by Kiril
I have a fixed size circular buffer (implemented as an array): upon initialization, the buffer gets filled with the specified maximum number of elements which allows the use of a single position index in order to keep track of our current position in the circle.
我有一个固定大小的循环缓冲区（作为数组实现）：初始化时，缓冲区填充指定的最大元素数，允许使用单个位置索引来跟踪我们在圆圈中的当前位置。
What is an efficient way to access an element in the circular buffer? Here is my current solution:
访问循环缓冲区中元素的有效方法是什么？这是我目前的解决方案：
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];
}
Some definitions:end_indexis the index of the element immediately after the last element in the circle (it would also be considered the same as the start_index, or the first element of the circle).buffer_sizeis the maximum size of the buffer.
一些定义：end_index是圆中紧跟在最后一个元素之后的元素的索引（它也被认为与 start_index 或圆的第一个元素相同）。buffer_size是缓冲区的最大大小。
回答by mpen
Best I've come up with is:
我想出的最好的是：
public static int Wrap(int index, int n)
{
return ((index % n) + n) % n;
}
(Assuming you need to work with negative numbers)
（假设您需要使用负数）
回答by Peter Taylor
Ensure that the buffer is always a power of two long and mask out the top bits.
确保缓冲区始终是 2 的幂，并屏蔽掉最高位。
回答by Jerry Coffin
It'll depend somewhat on the processor, but it's probably at least worth trying something like return (end_index + index) % buffer_size;
它会在某种程度上取决于处理器，但它可能至少值得尝试类似的东西 return (end_index + index) % buffer_size;
回答by Kiril
// 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);
}
The performance results (ticks):
性能结果（滴答）：
Plain: 25 Mod: 16 Mask: 16 (maxSize = 512)
Plain: 25 Mod: 17 Mask: 17 (maxSize = 1024)
Plain: 25 Mod: 17 Mask: 17 (maxSize = 4096)
So it seems that the modulus is the better choice, because it does not require any restriction on the size of the buffer.
所以看起来模数是更好的选择，因为它对缓冲区的大小没有任何限制。
回答by Judge Maygarden
int GetElement(int index)
{
return buffer[(end_index + index) % buffer_size];
}
See modulo operationfor the more information on the modulus operator (%).
回答by Mike Dunlavey
FWIW, you could always do a parallel array: i = next[i];
FWIW，你总是可以做一个并行数组： i = next[i];
But, really, I've always just done this: i++; if (i >= n) i = 0;OR i = (i+1) % n;
但是，真的，我一直都是这样做的：i++; if (i >= n) i = 0;或者i = (i+1) % n;
Regardless, I'd be really surprisedif this is ever a significant performance issue.
无论如何，如果这是一个重大的性能问题，我真的会感到惊讶。
