内存和向量的向量

Question

我正在实现一个距离矩阵来计算每个点和所有其他点之间的距离,我有100,000个点,所以我的矩阵大小将是100,000 x 100,000.我用它来实现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-tree,quadtrees,r-trees可能呢？