1

I'm trying to implement the shrinking operation for a circular buffer. The buffer has a start pointer( m_start ) and stores the number of elements( m_numelements). When the buffer is full I just purge the old value.

Say we have a array of size 16. m_start = 9 m_numelements = 11.

I want to shrink this array into an array of size 8( Can discard elements ).

The constraint here is that m_start( 9 ) of the old array should map to the m_start % new capacity ( 9 % 8 = 1 ) of the new array.

I tried writing the code but ended up with a lot of if-else ladder. Any efficient implementation for this ?

4

2 回答 2

1

让我们的存储数组具有从零开始的索引，它的大小是 2 的幂 (2,4,8...)，m_start 是起始索引。

当数组增长时：

 double array length
 if m_start > 0 then
    copy (m_start elements) from (0th index) to (old size index)

例子：

  3 0 1 2|. . . .
  . 0 1 2|3 . . .

当数组缩小时：

  if m_start > 0 then
     copy (m_start elements) from (newsize index) to (0th index) 
  half array length

例子：

  . 0 1 2|3 . . . 
  3 0 1 2|. . . .

您可以修改此方案以进行基于 1 的数组索引。

于 2013-07-05T11:21:57.267 回答
0

收缩相当于将整个内容出列到一个临时缓冲区中，然后将该缓冲区的内容入列到一个具有指定容量的新循环缓冲区中。这不是您想要的，但它会告知代码必须是什么样子。

所以：编写代码以将循环缓冲区的全部内容出列并使用您已有的方法将它们排入新的循环缓冲区，然后内联包含在您使用的方法中的代码，然后重构该代码以将内容放入现有的循环缓冲区（调整大小后）而不是新缓冲区，并优化掉任何不必要的副本或案例。

于 2013-07-05T20:38:16.990 回答