C++で2つの配列の和集合を改善する

Question

2つの配列AとBのUnionをC++で高速化する方法はありますか（任意のnを指定します）？あなたは正確に一度、すべての要素をコピーしなければならないので、私は思考beeingているが、他の方法を見ることができない ...

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++でタグ付けしました。それは（std::copyを使用して）あなたがC++を使用している場合、あなたはこのようにそれを書くことができ、言った：

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

あなたが行うすべては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ではないと思われる場合は、std::vectorのようなC++構造を使用する必要があります。

私は（私はそれをテストしていないが）、コードは次のようになり信じる：

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関数を使用します。