недостаточно памяти и вектора векторов

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 х 100000?Быстрый расчет показывает, почему это никогда не сработает:

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

Даже если бы можно было выделить столько памяти, я очень сомневаюсь, будет ли это эффективным подходом к реальной проблеме.

Если вы хотите выполнить некоторую геометрическую обработку больших наборов данных, вас может заинтересовать какая-то пространственная древовидная структура: деревья kd , quadtrees , р-деревья может быть?

Answer 2

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

Легко видеть, что в 32-битной системе - нехватка памяти гарантируется для такой большой базы данных, даже не вычисляя тот факт, что мы нашли количество элементов, а нечисло используемых байтов.

Даже в 64-битных системах крайне маловероятно, что ОС позволит вам выделять столько памяти [также обратите внимание, что вам на самом деле нужно гораздо больше памяти, в том числе и потому, что каждый элемент, который вы выделяете, оченьбольше, чем байт.]

Answer 3

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

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

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

Answer 4

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