Из памяти и вектора векторов

Question

Я реализую матрицу расстояний, которая вычисляет расстояние между каждой точкой и всеми остальными точками, и у меня есть 100 000 точек, поэтому размер моей матрицы будет 100 000 х 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

A 100000 x 100000 matrix? Быстрый расчет показывает, почему это никогда не будет работать:

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-разрядных системах маловероятно, что ОС позволит вам так много памяти [также обратите внимание, что на самом деле вам требуется гораздо больше памяти, так как каждый элемент, который вы выделяете, намного больше байта.]

Answer 3

Знаете ли вы, что 100 000 раз 100 000 - это 10 миллиардов? Если вы храните расстояния как 32-битные целые числа, то это должно составлять 40 миллиардов байт, или 37,5 ГБ. Это, вероятно, больше оперативной памяти, чем у вас, поэтому это будет невозможно.

Answer 4

100,000 x 100,000 x sizeof (double) = примерно 80GIG (с 8 байтами) без накладных расходов векторов.

Это вряд ли произойдет, если вы не находитесь на действительно большой машине. Посмотрите на использование какой-либо базы данных или одной из библиотек коллекции C/C++, которая проливает большие данные на диск.

В библиотеке классов SourcePRO Rogue Wave есть несколько классов коллекции на основе дисков, но это не бесплатно.