взять массив из круглой матрицы

Question

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

Но то, что я хочу сделать, это на каждом шагу к:

• первый, перезаписать самую последнюю информацию в массиве с новейшим, который только что прибыл
• дальше, используя весь массив, начиная с самых старых до последней
• повторе

мне трудно увидеть, как обрабатывать второй шаг в C++, будучи эффективным. Или может быть, что-то еще, чем круговой массив, было бы лучше? Любые рекомендации или точки зрения приветствуются.

Чтобы иметь что-то более графический:

for step in steps: 
    (current writing position = 2) 
    current buffer = [8, 9, 3, 4, 5, 6, 7] 

    new info = 10 

    overwrite buffer(new info) 
    new buffer = [8, 9, 10, 4, 5, 6, 7] 

    current writing position += 1 //(3) 

    array to use = [4, 5, 6, 7, 8, 9, 10] 

    function(array to use) 

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

То, что я имею в виду, чтобы скопировать последнюю часть и первую часть, а затем объединить их:

std::vector<int> buffer{8, 9, 10, 4, 5, 6, 7}; 

std::vector<int> oldest(&buffer[3],&buffer[6]); 
std::vector<int> youngest(&buffer[0],&buffer[2]); 

oldest.insert(oldest.end(), youngest.begin(), youngest.end()); 

function(oldest) 

Если вы знаете что-то, что было бы быстрее, сообщите мне.

Answer 1

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

Таким образом, для функции обработки потребуется просто указатель на массив (или ссылка на std :: vector), знать размер и текущую рабочую позицию.

// process from working pos to end of buffer 
for(int i = current_pos; i < buffer_size; ++i) { 
    processElement(new_buffer [i]); 
} 
// process the remainder from begin to working pos 
for(int i = 0; i < curent_pos; ++i) { 
    processElement(new_buffer [i]); 
} 

Это не должно быть трудно inplement как ваше рабочее положение отмечает и, в начале и в конце данных для обработки.

Answer 2

Этот подход уменьшает накладные расходы n-fold, где n - количество дополнительных элементов массива + 1.

Пример: массив с 2 дополнительными элементами

Обратите внимание, что в этом случае, самое старое значение на левой стороне, функция была вызвана с указателем на обр [0] (start_pos = 0)

arr == [3, 4, 5, 6, 7, 8, 9, x, x] 

теперь позволяет вставить на новое значение 10

arr == [3, 4, 5, 6, 7, 8, 9, 10, x] 

start_pos += 1 

вызов функции с указателем на второй элемент (старый 3 не будет использоваться)

function(arr + start_pos) 

и теперь добавить 11 и увеличивать рабочее положение (старый 4 не будет использоваться)

arr == [3, 4, 5, 6, 7, 8, 9, 10, 11] 

start_pos += 1 

function(arr + start_pos) 

Теперь массив заполнен.

И только теперь необходимо скопировать последние элементы в начало массива (после начала start_pos до конца) и установить working_pos на 0 в зависимости от количества дополнительных элементов, которые необходимо выполнить только каждый 10-й, 100-й или даже 1000-й итерации!

результат копирования будет:

arr == [6, 7, 8, 9, 10, 11, 9, 10, 11] 
          * 
start_pos = -1 // prepare for the +1 in regular iteration. 

рядом добавленную стоимость (12) перезаписывает значение *

arr == [6, 7, 8, 9, 10, 11, 12, 10, 11] 

start_pos += 1 // is 0 now 

function(arr + start_pos) 

Конечно, вам нужно одну переменную, чтобы определить поз, чтобы вставить новый элемент за другим значением val или вы получаете из start_pos + nElemsToProcess

Если ваша функция() принимает только контейнеры std, это, вероятно, не самый правильный выбор для удовлетворения потребности в sp ПЕД.