Как я могу инициализировать вектор, содержащий около 300000 векторов размером около 300000

Question

В моей реализации некоторого уравнения мне нужно построить диагональную матрицу NXN . Я использую вектор векторов для представления матриц. Однако N составляет около 300000 , поэтому

std::vector<std::vector<double> > new_matrix(300000,std::vector<double>(300000,0)) 

при работе дает

terminate called after throwing an instance of 'std::bad_alloc'

  what():  std::bad_alloc

Это невозможно из-за памяти предел?

Answer 1

На этот вопрос обычно можно ответить: Работа с большими объемами данных в c ++

В вашем случае,

ошибка связана с недостаточной непрерывной памятью кучи для вектора

300 000 * 300 000 чисел с плавающей запятой двойной точности.

Возможно, предпочтительнее использовать другой контейнер это не нуждается в непрерывной памяти как std::list. Но подождите, какой объем памяти необходим для этого?

300000 * 300000 * sizeof (double) =

300000 * 300000 * 8 =

720000000000 байт =

703125000 КБ =

686646 МБ =

671 ГБ!

Если вы не работаете с суперкомпьютером, забудьте об этом идея.

В давние времена программистам приходилось придумывать умные решения для работы в пределах крошечной оперативной памяти. Почему бы не сделать это сегодня? Давайте начнем с поиска шаблонов в вашей проблеме. Вы работаете с

Диагональная матрица:

Матрица, имеющая ненулевые элементы только по диагонали, идущей от верхнего левого угла к нижнему правому

Следовательно, вам не нужно хранить недиагональные элементы в памяти, поскольку гарантируется, что эти элементы равны 0. Таким образом, проблема сводится к хранению только основных диагональных элементов (матрица [0 ] [0], матрица [1] [1], ... матрица [n-1] [n-1]), всего n элементов . Теперь вы можете рассмотреть только 300000 элементов, что намного меньше, чем 90000000000!

Расчет памяти для этого:

300000 * sizeof (double) =

300000 * 8 =

2400000 байт =

2344 КБ =

2,3 МБ!

Как видите, этот подход сократил наши требования от 670 ГБ до всего 2 МБ. Он может все еще не работать с некоторой стековой памятью, но это не имеет значения, потому что мы имеем дело с кучей памяти (std::vector - это динамический c массив).

Теперь, когда мы уменьшили сложность пространства, это просто вопрос реализации этой логики c. Но будьте осторожны, соблюдайте это соглашение при доступе, обходе и хранении массива.

Например:

#include <iostream>
#include <vector>

typedef std::vector<double> DiagonalMatrix;

int main()
{
    // std::vector<std::vector<double>> new_matrix(300000, std::vector<double>(300000, 0));
    DiagonalMatrix m(300000, 0);

    // Store the main diagonal elements only

    // Keep this convention in mind while using this implementation of DiagonalMatrix

    return 0;
}

Редактировать:

Чтобы продемонстрировать этот дизайн и после вашего запроса в комментариях, ниже приведена реализация необходимого logi c:

// Product = DiagonalMatrix * Matrix
Matrix DiagonalMatrix::preMultiply(Matrix multiplier)
{
    // Check if multiplication is possible
    if (multiplier.r != this->n)
        return Matrix();

    // Product is the same as the multiplier where
    // every element in the ith row of the multiplier is
    // multiplied by the ith diagonal element of the diagonal matrix
    Matrix& product = multiplier;
    for (int i = 0; i < multiplier.r; ++i)
    {
        for (int j = 0; j < multiplier.c; ++j)
        {
            product.m[i][j] *= this->m[i];
        }
    }
    return product;
}

// Product = Matrix * DiagonalMatrix
Matrix DiagonalMatrix::postMultiply(Matrix multiplier)
{
    // Check if multiplication is possible
    if (multiplier.c != this->n)
        return Matrix();

    // Product is the same as the multiplier where
    // every element in the jth column of the multiplier is
    // multiplied by the jth diagonal element of the diagonal matrix
    Matrix& product = multiplier;
    for (int j = 0; j < multiplier.c; ++j)
    {
        for (int i = 0; i < multiplier.r; ++i)
        {
            product.m[i][j] *= this->m[j];
        }
    }
    return product;
}