Уменьшение кольцевого буфера

Я пытаюсь реализовать операцию сжатия для кругового буфера. Буфер имеет начальный указатель (m_start) и хранит количество элементов (m_numelements). Когда буфер заполнен, я просто очищаю старое значение.

Скажем, у нас есть массив размером 16. m_start = 9 m_numelements = 11.

Я хочу уменьшить этот массив до массива размером 8 (можно отбрасывать элементы).

Ограничение здесь состоит в том, что m_start( 9 ) старого массива должно сопоставляться с новой емкостью m_start % ( 9 % 8 = 1 ) нового массива.

Я попытался написать код, но в итоге получил много лестницы «если-иначе». Любая эффективная реализация для этого?


algorithm data-structures circular-buffer circular-list
person KodeWarrior    schedule 05.07.2013    source источник
comment
У меня похожая проблема. Могу ли я отредактировать вопрос, чтобы использовать более конкретную реализацию (на C), возможно, заставив обновить некоторые предложения ответов (ни один из них не был принят до сих пор), или я должен задать новый вопрос?   -  person U. Windl    schedule 30.10.2020

Ответы (2)


arrow_upward
1
arrow_downward

Пусть у массива хранения индексация начинается с нуля, а его размер равен степени двойки (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|. . . .

Вы можете изменить эту схему для индексации массива на основе единицы.

person MBo    schedule 05.07.2013

arrow_upward
0
arrow_downward

Сжатие эквивалентно удалению всего содержимого из очереди во временный буфер, а затем добавлению содержимого этого буфера в новый циклический буфер с указанной емкостью. Это не совсем то, что вам нужно, но это даст информацию о том, как должен выглядеть код.

Итак: напишите код, чтобы удалить из очереди все содержимое циклического буфера и поставить его в очередь в новый циклический буфер, используя уже имеющиеся у вас методы, затем встроить код, содержащийся в используемых вами методах, затем реорганизовать этот код, чтобы поместить содержимое в существующий круговой буфер (после изменения размера) вместо нового и оптимизировать все ненужные копии или случаи.

person Craig Gidney    schedule 05.07.2013