Как сделать декартово произведение векторов, когда число элементов> 1000? - PullRequest
Новая
       35

Как сделать декартово произведение векторов, когда число элементов> 1000?

5 голосов
/ 01 апреля 2019

У меня 1,2, ..., n кусочек векторов.Каждый вектор содержит более 10000 элементов, и я должен получить декартово произведение этих векторов.У меня есть код, что работает, но только под 1000 элементов и под 4 вектора.Я хотел бы записать декартово произведение в файл, но если выходной файл больше, чем 1 ГБ, я получил: «завершить вызов после создания экземпляра 'std :: bad_alloc' what (): std :: bad_alloc".

Мой основной вопрос: как я могу исправить эту ошибку выделения памяти?

Вот исполняемый фрагмент моего кода: 

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <fstream>
#include <math.h>

using namespace std;

vector<double> makeVectorByRange(double min, double max, double step){
    vector<double> out = {};
    for( ; min <= max; min+=step){
        out.push_back(min);
    }
    return out;
} 


void cart_product_solve_and_write_to_file (const vector<vector<double>>& inpV) {
    vector<vector<double>> out = {{}};

    std::ofstream outputFile;
    std::fixed;

    for (auto& u : inpV) {
        vector<vector<double>> r;
        r.clear();
        for (auto& x : out) {

            //make/open file, append
            outputFile.open ("out.csv", std::ofstream::out | std::ofstream::app);
            outputFile.precision(8);

            for (auto y : u) {
                r.push_back(x);
                r.back().push_back(y);

                if( r.back().size() == inpV.size() ){

                    // write the input parameters of griewank to file
                    for(double asd : r.back()){
                        outputFile << asd << ";";
                    }

                    outputFile << "; \n";
                    outputFile << std::flush;

                    r.back().clear();
                }
            }
            //close file
            outputFile.close();
        }
        out.swap(r);
    }  
}

// Pure cartesian product. This function returns the cartesian product as a vector, but if the input vectors are too big, it has an error
/*
vector < vector<double> > cartesian_product (const vector< vector<double> >& inpV) {
    vector< vector<double> > out = {{}};
    for (auto& u : inpV) {
        vector< vector<double> > r;
        for (auto& x : out) {
            for (auto y : u) {
                r.push_back(x);
                r.back().push_back(y);
            }
        }
        out.swap(r);
    }
    return out;
}
*/

int main(){

    clock_t tStart = clock();

    // it works
    // const vector<vector<int> > test ={ {0,1,2,3,4}, {5,6,7}, {8,9,10,11,12,13} };
    // vector<vector<int> > cart_prod = cartesian_product(test);

    vector <vector<double> > test = {};
    test.push_back( makeVectorByRange( 0, 0.5, 0.001) );
    test.push_back( makeVectorByRange( 0, 0.5, 0.001) );
    test.push_back( makeVectorByRange( 0, 0.5, 0.001) );

    cart_product_solve_and_write_to_file(test);

    printf("Time taken: %.6fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

    return 0;
}

1 Ответ

2 голосов
/ 01 апреля 2019

Вам нужно перебрать все комбинации полученного декартова произведения.Обычно это достигается путем рекурсии.На каждом уровне рекурсии вы затем выполняете итерации по элементам одного входного вектора.

Вот пример решения для вывода полученных комбинаций в std::cout.Вы можете легко изменить его для печати в файл, предоставив дополнительный ссылочный параметр для открытого std::ofstream объекта для рекурсивной функции. 

#include <iostream>
#include <vector>

template <typename T>
void vector_cartesian_product_helper(
  const std::vector<std::vector<T>>& v, std::vector<T>& combination, size_t level)
{
  if (level == v.size()) {
    for (auto elem : combination)
      std::cout << elem << ";";
    std::cout << "\n";
  }
  else {
    for (const auto& elem : v[level]) {
      combination[level] = elem;
      vector_cartesian_product_helper(v, combination, level + 1);
    }
  }
}

template <typename T>
void vector_cartesian_product(const std::vector<std::vector<T>>& v)
{
  std::vector<T> combination(v.size());
  vector_cartesian_product_helper(v, combination, 0);
}

int main(){
  std::vector<std::vector<int>> test = {{0,1,2,3,4}, {5,6,7}, {8,9,10,11,12,13}};
  vector_cartesian_product(test);
}

Live demo: https://wandbox.org/permlink/PoyEviWGDtEpvN1z

Itработает с векторами любых размеров и использует только дополнительную память O (N) , где N - количество векторов.

...