如何用循环缓冲区解决这个问题？

Question

在数组中将一个元素插入到其他元素之前而无需使用 for 循环重新排列所有元素的最有效方法是什么。我尝试了循环缓冲区实现，但它不起作用，我感到很沮丧。我把问题简单化了，希望对大家来说更容易。

int * buffer = (int *) calloc(L_buffer, sizeof(int));
int i, j, K, out;

while(1) {

    i = rand();
    K = 3;

    /* Calculate output */

    out = buffer[i]  buffer[i+1]  + buffer[K];

    /* Shift array elements by one and insert new value */

    for(j = 0; j < L_buffer-1; j++) 
        buffer[j+1] = buffer[j];

    buffer[0] = new_value;
}

解决方法：我编辑了@Eric Postpischil 的解决方案以满足我的需要。通过将函数扩展到下面，我可以双向推进当前索引并始终环绕。

int * cb_element(CircularBuffer *cb, ptrdiff_t i) {

    if ( cb->current < 0)
        cb->current += cb->size;

    ptrdiff_t index = cb->current + i;

    if ((size_t) index >= cb->size)
        index -= cb->size;


    return &cb->array[index];
}

所以我可以

out = *cb_element(&cb, i) + *cb_element(&cb, i+1);

cb.current--;
*cb_element(&cb, 0) = new_value;

真的很整洁！

Answer 1

There is probably a more elegant way than doing it with so many lines.

"mod" 数组索引访问 % L_array 使用无符号数学。此外，如果 L_array 是无符号的 2 的幂，则 % L_array 会简单地生成和代码。

output = p_dynamic[i] + p_dynamic[(i+1)% L_array] + p_dynamic[(i+2)% L_array];

注意：除非代码依赖于未定义的行为，否则--p_dynamic < p_start永远不会成立。与 p_dynamic 进行比较的有效值是 array[0]...array[length]，不包括 array[-1]。

循环缓冲区的插入看起来很可疑。应该没有理由 for 循环到 shift。而是调整对缓冲区末端的引用。

考虑使用以下：

array = calloc(L_array, sizeof *array);
size_t length = 0; // current length
size_t begin = 0;  // Index of eldest sample
size_t end = 0;    // Index to store the next sample

插入

if (length < L_array) {
  length++;
  array[end] = new_value;
  end = (end+1)%L_array;
}

提取

if (length > 0) {
  length--;
  sample = array[begin];
  begin = (begin+1)%L_array;
}

从 i

开始采样 3 个元素

if (length >= 3) {
  output = array[(begin+i) % L_array] + array[(begin+i+1) % L_array] +
      array[(begin+i+2) % L_array];
}

Answer 2

int *p_dynamic = array[0]; int *p_start = array[0]; int *p_end = array[L_array - 1];

您没有告诉我们这些变量的用途，因此我们不知道您是否以合理的方式使用它们来达到预期目的。

if (--p_dynamic < p_start)

当p_dynamic指向array[0]时，C标准没有定义--p_dynamic的行为。该标准仅定义从数组元素 0 到数组最后一个元素之后的指针算法。

int K = 3; int i = some_int; int output; output = array[i] + array[i+1] + array[K];

同样，你没有告诉我们意图，所以我们不知道你在这里试图达到什么目的。为什么 K 3？这是每次使用您的代码时的固定常量还是只是一个示例？跟i有关系吗？你的意思是 array[K] 意味着实际元素 array[3] 将始终被添加，还是你的意思是从循环缓冲区的当前开始偏移量 3 处的元素将被添加？

if (p_dynamic[K] > p_end && p_dynamic[i] < p_end && p_dynamic[i+1] < p_end)

这没有意义，因为 p_dynamic 是指向 int 的指针，所以 p_dynamic[K] 是 int，但 p_end 是指向int，因此 p_dynamic[K] > p_end 尝试将 int 与指针进行比较。我怀疑您正试图询问元素 p_dynamic[K] 是否会超出数组的末尾。您可以使用 p_dynamic + K > p_end 来执行此操作，但与 --p_dynamic 一样，如果它超出了数组的末尾，则指针算法未由 C 标准定义。

创建一个函数来帮助您访问数组元素，从而简化您的代码。制作一个描述循环缓冲区的结构。简单地开始，我假设你有一个固定的缓冲区大小 Size eleemnts.

typedef struct
{
    int array[Size];
    ptrdiff_t current;
} CircularBuffer;

成员current将是缓冲区中当前最旧元素的索引（下标），循环缓冲区的当前“开始”。（ptrdiff_t 类型在头文件 <stddef.h> 中定义。它可能用于数组下标。

然后创建一个函数，为您提供指向索引为 i:

的元素的指针

int *CBElement(CircularBuffer *cb, ptrdiff_t i)
{
    ptrdiff_t index = i + current;
    if (Size <= index) index -= Size;
    return &cb->array[index];
}

则可以引用数组元素K，例如*CBElement(&cb, K):

output = *CBElement(&cb, i) + *CBElement(&cb, i+1) + *CBElement(&cb, K);

您还可以在数组中放入新值：

*CBElement(&cb, i) = NewValue;

要推进缓冲区，以明显的方式更新 current 成员并将新值放入新的最后一个元素 (*CBElement(&cb, Size-1))。

这应该可以简化让代码正常工作的任务。生效后，可以考虑对buffer的实现进行优化和细化。

如何用循环缓冲区解决这个问题？

How to solve this with a circular buffer?

c

circular-buffer