улучшить объединение 2-х массивов в с ++

Question

Есть ли способ ускорить объединение двух массивов A и B в c ++ (с учетом любого n)?Я размышляю, но не вижу другого пути ...

double *A = (double *)malloc( n*n *sizeof(double));
double *B = (double *)malloc(   n *sizeof(double));
double *U = (double *)malloc((n*n+n) *sizeof(double));


int i=0, ci=0;
for (i = 0; i <n*n; i++)
    U[ci++] = A[i];
for (i = 0; i < n; i++)
    U[ci++] = B[i];

Answer 1

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

double *A = (double *)malloc( n*n *sizeof(double));
double *B = (double *)malloc(   n *sizeof(double));
double *U = (double *)malloc((n*n+n) *sizeof(double));

/* Copy over A onto U. */
memcpy(U, A, n * n * sizeof(double));

/* Append B to U. */
memcpy((char*)U + n * n * sizeof(double), B, n * sizeof(double));

Это может быть быстрее, потому что логика копирования байтов может быть ручной-optimized.

Вы пометили этот вопрос на C ++, хотя он больше похож на C-код.Тем не менее, если вы используете C ++, вы могли бы написать это так (используя std::copy):

double *A = new double[n * n];
double *B = new double[n];
double *U = new double[n * n + n];

std::copy(A, A + n * n, U);
std::copy(B, B + n,     U + n * n);

Или, что еще лучше, используя std::vector без открытого управления памятью или указателей:

vector<double> A(n * n);
vector<double> B(n);

vector<double> U;
U.reserve(A.size() + B.size());
U.insert(U.end(), A.begin(), A.end());
U.insert(U.end(), B.begin(), B.end());

Надеюсь, это поможет!

Answer 2

Поскольку все, что вы делаете - это объединение двух блоков памяти, вы можете использовать memcpy:

double *A = (double *)malloc( n*n *sizeof(double));
double *B = (double *)malloc(   n *sizeof(double));
double *U = (double *)malloc((n*n+n) *sizeof(double));
memcpy(U, A, n*n *sizeof(double));
memcpy(U+n*n *sizeof(double), B, n *sizeof(double));

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

Answer 3

Если это действительно C ++, а не C, то вы должны использовать конструкции C ++, такие как std::vector.

Я считаю, что код будет выглядеть (хотя я его не проверял):

size_t n = 100;
std::vector A(n*n);
std::vector B(n);
std::vector U;

U.reserve( A.size() + B.size() );
std::copy(A.begin(), A.end(), std::back_inserter(U));
std::copy(B.begin(), B.end(), std::back_inserter(U));

Если вы на самом деле имеете в виду объединение, как в наборе объединений, в котором нет повторяющихся чисел, вам нужно отсортировать как A, так и B, а затем использовать функцию std::set_union.