Оптимизация вставки одного массива в другой массив C / C ++

Question

У меня есть эта функция в моем собственном классе динамических массивов, которая позволяет пользователю вставлять другой массив в этот. Это работает, но я на 99% уверен, что это не самое быстрое решение, и мне интересно, можно ли объединить два цикла for для повышения производительности? Если так, то как? Я немного застрял.

спасибо заранее.

void insertrange(T item[], int sizerange, int index) 
    {
        int k = this->size;
        int j = 0;
        if(this->size + sizerange >= this->capacity) //if the size + added size are bigger than the capacity
        {
            this->enlarge(this->capacity + sizerange); //enlarge the array
        }
        for(k; k >= index; k--) //for every element from the end to the index where to add the new array
        {
            this->array[k + sizerange] = a[k]; //replace the element to his new spot
        }
        for(j; j < sizerange; j++) //vor every element in the new array
        {
            this->array[index + j] = item[j]; //place it in the new spot
        }
        size += sizerange; 
    }

Answer 1

Я думаю, что ключ в том, что вам не нужно копировать пустые ячейки.

   void insertrange(T item[], int sizerange, int index) 
    {
        // This actually points past the end of the current array, right?
        int onePastLastEntry = this->size;
        // Still need to make sure the new array is large enough
        if(this->size + sizerange >= this->capacity) //if the size + added size are bigger than the capacity
        {
            this->enlarge(this->capacity + sizerange); //enlarge the array
        }
        // you should be able to go forward instead of backwards
        for(i = index; i < onePastLastEntry ; i++)
        {
            // move the current element
            this->array[i + sizerange] = a[i];
            // then copy the new value
            this->array[i] = item[i - index];
        }

Вы могли бы сделать цикл с нуля, перейдя также к onePastLastEntry - index, но это делает математику странной:

        // you should be able to go forward instead of backwards
        for(i = 0; i < onePastLastEntry - index; i++)
        {
            // now you have to add the index in two places here
            this->array[i + index + sizerange] = a[i + index];
            // and add the index in the copy as well
            this->array[i + index] = item[i];
        }

Answer 2

Единственное возможное преимущество в производительности, которое я вижу, заключается в уменьшении динамического распределения при каждом увеличении массива. В большинстве случаев лучше каждый раз перераспределять емкость на 2.

Answer 3

У вас есть одна дополнительная копия в цикле k for.Индекс k должен начинаться с размера 1, а не с размера, поэтому вы копируете один дополнительный элемент за конец вашего массива.Тем не менее, это обеспечит незначительное ускорение.Если требуется серьезное улучшение производительности, вам следует подумать об оптимизации функции увеличения или использовать структуру данных, отличную от массива.

Answer 4

Вы можете перемещать элементы вместо их копирования:

for(k; k >= index; k--)
{
    this->array[k + sizerange] = std::move(a[k]);
}

Другим возможным улучшением, особенно для классов, которые имеют дорогой конструктор по умолчанию, является создание T на месте с использованием конструктора перемещения. Когда вы выделяете вместо new T[], который по умолчанию создает каждый элемент, выделяйте необработанные байты с new char[] или malloc. Затем вы можете использовать размещение новых, чтобы переместить построить объект на месте.