如何在向量元素数量超过1000时制作笛卡尔积？

Question

我有1, 2, ..., n个向量，每个向量都有超过10000个元素，我需要获取这些向量的笛卡尔积。我已经有了一段代码，它可以工作，但只适用于1000个元素和4个向量以下。

我想将笛卡尔积写入文件，但如果输出文件大于1GB，我会得到"terminate called after throwing an instance of '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;
}

- vizvezetek

---

嗯。向量的笛卡尔积通常是需要进行“迭代”的，这样你才能一次只看到一个组合。你为什么想要存储所有的组合呢？ - M Oehm

如何解决内存分配错误？请遍历所有组合并将它们存储在文件中，不要在内存中保留它们。 - Daniel Langr

此外，您知道向量的目标大小（因为它基于输入向量的大小），因此应使用reserve()来避免重新分配 - 不仅因为速度更快，而且还可以防止内存碎片化（这可能导致一个大块无法分配，尽管有足够的可用空闲内存，但是碎片化）。但正如其他人所说，如果可能的话，最好根本不要将结果存储在内存中，只需将它们写入文件即可。 - EmDroid

- Jarod42

@DanielLangr 是的，我知道。你在main()函数中看到的是一个测试。这个函数也可以处理4、40和400个向量。但如果我有400个向量，我不想写400个嵌套循环。 - vizvezetek

Answer 1

你需要对所有结果的笛卡尔积进行迭代，通常通过递归来实现。在每个递归级别上，你需要遍历一个输入向量的元素。

以下是将结果组合打印到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);
}

在线演示: https://wandbox.org/permlink/PoyEviWGDtEpvN1z

该算法适用于任何大小的向量，并且仅使用额外的O(N)内存，其中N是向量的数量。

最初的回答:

- Daniel Langr

---

太好了！谢谢你！ - vizvezetek