ベクトルのベクトルとベクトルの

Question

私は各ポイントと他のすべてのポイント間の距離を計算し、私は100000ポイントを持っているので、私のマトリックスサイズは100000×100000になる距離行列を実装しています。私はvector<vector<double> > distを使って実装しました。しかし、この大きなデータサイズの場合、メモリエラーが発生します。以下は私のコードです、そして、どんな助けも本当に感謝されるでしょう。

vector<vector<double> > dist(dat.size()) vector<double>(dat.size())); 
size_t p,j; 
ptrdiff_t i; 
#pragma omp parallel for private(p,j,i) default(shared) 
for(p=0;p<dat.size();++p) 
{ 
// #pragma omp parallel for private(j,i) default(shared) 
for (j = p + 1; j < dat.size(); ++j) 
{ 
double ecl = 0.0; 
for (i = 0; i < c; ++i) 
{ 
ecl += (dat[p][i] - dat[j][i]) * (dat[p][i] - dat[j][i]); 
} 
ecl = sqrt(ecl); 
dist[p][j] = ecl; 
dist[j][p] = ecl; 
} 
} 

Answer 1

100000 x 100000マトリックス？これが仕事に行くことはありません、なぜ迅速な計算は示しています

100000 x 100000 x 8 (bytes)/(1024 * 1024 * 1024) = 74.5 gigabytes... 

私はこれが本当の問題のための効率的なアプローチであるかどうかは非常に多くを疑うこのくらいのメモリを割り当てることが可能であったとしても。

大規模なデータセットで何らかの幾何学的処理を行う場合は、何らかの種類の空間ツリー構造に興味があります：kd-trees、quadtrees、r-trees多分？

Answer 2

100,000 * 100,000 = 10,000,000,000 ~= 2^33

32ビットのシステムでそれを見ることは容易である - メモリ不足があっても、我々は要素の数を発見し、そしていないという事実を計算することなく、このような大規模なデータベースのために保証されています使用されたバイト数。

64ビットシステムであっても、OSがあなたに非常に多くのメモリを許可することはほとんどありません。また、割り当てた各要素がバイトよりはるかに多いため、実際にはさらに多くのメモリが必要です。

Answer 3

100,000回100,000回は100億回ですか？距離を32ビットの整数として格納する場合は、400億バイト（37.5 GB）になります。これはあなたが持っているよりも多分RAMであるため、これは実行可能ではありません。

Answer 4

ベクトルのオーバヘッドなしで100,000 x 100,000 x sizeof（double）=約80GIG（8バイト倍）。

あなたが本当に大きなマシンにいなければ、それは起こりそうにありません。 大量のデータがディスクに流出するC/C++コレクションライブラリのうちの1つまたはソートのデータベースを使用します。

Rogue WaveのSourcePROクラスライブラリには、ディスクベースのコレクションクラスがいくつかありますが、それは無料ではありません。