在c ++中改进2个数组的并集

Question

有没有办法让这种方式使c ++中的2个数组A和B的联合更快(给定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));

这可能更快,因为复制字节的逻辑可以手动优化.

你用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());

希望这可以帮助!