c++ - 处理数百万个排列

Question

我正在尝试计算 20x20 布尔矩阵的数百万 (10 ⁸ ) 个排列。我能够很快地计算它们。之后，我需要使用标准输出显示它或将其存储到文件中。您认为可以在 4 小时内以某种方式管理这么多数据吗？

Answer 1

10 ¹⁸操作？让我们看看...您的 PC 可能不会比每秒10 ⁹到 10 ^{10条指令更好。}所以，你至少需要 10 ⁹到 10 ¹⁰秒来做 10 ¹⁸次操作，也就是超过 31 年的时间。这速度够快吗？在 31 年的过程中，您的 PC 是否还活着并拥有不间断的电源？

Answer 2

一个 20x20 的布尔矩阵是 400 位 = 50 字节 * 10^8 排列 = 5 * 10^9 字节 = 5 GB。

使用 3 GBit/s SATA 驱动器，您的下限为

5 GB = 40 GBit / 3 GBit/s ~ 13.3 sec

在我 5 岁的电脑上，复制一个 1.9 GB 的文件大约需要 82 秒。这涉及读取和写入 1.9 GB。因此，编写 10^8 400 位值的二进制表示的上限约为 215 秒。

编写一个 ASCII 表示将使用大约 50 GB 并且需要大约 8-10 倍的时间，大约 2150 秒。这将超过 35 分钟。

综上所述，我认为在 4 小时之内写完这么多数据应该是可以的。

更新：

我没有 5 GB 的主内存来保存所有排列。因此，我多次写入相同的数据。调用这个

./a.out a.bin 100

在我的机器上写入大约 4.7 GiB 的数据并花费 114 秒。

#include <fstream>

struct matrix {
    unsigned char data[50];
    void write(std::ostream &f) {
        f.write(reinterpret_cast<char*>(data), sizeof(data));
    }
};

static const unsigned long N = 1000000;
matrix permutations[N];

int main(int argc, char **argv)
{
    // prevent sparse file
    for (unsigned long j = 0; j < N; ++j)
        permutations[j].data[j % 50] = 1;

    std::ofstream f(argv[1]);
    f.sync_with_stdio(false);
    unsigned long m = std::stoi(argv[2]);
    for (unsigned long i = 0; i < m; ++i) {
        for (unsigned long j = 0; j < N; ++j)
            permutations[j].write(f);

    }

    return 0;
}

使用 ASCII 表示看起来很相似

struct matrix {
    unsigned char data[50];
    friend std::ostream &operator<<(std::ostream &f, const matrix &x) {
        static int bits[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
        for (int i = 0; i < 50; ++i) {
            for (int j = 0; j < 8; ++j)
                f << (x.data[i] & bits[j] ? '1' : '0');
        }

        return f;
    }
};

并在mainfor 循环中

for (unsigned long i = 0; i < m; ++i) {
    for (unsigned long j = 0; j < N; ++j)
        f << permutations[j] << '\n';
}

写入 10^7 个排列在磁盘上使用了大约 3.8 GiB，大约花费了 4:41 分钟。写十倍的内容可能需要一个小时或 90 分钟。在当前的硬件上，这应该更快。

Answer 3

使用 10^8 个排列，每个排列打包成 50 个字节（400 位），它将提供大约 5 GB 的数据。应该可以在普通磁盘上以每秒 100 MB 的速度将其存储到磁盘上的文件中——5 GB 数据的总写入时间为 50 秒。

因此，只要您可以足够快地生成排列，在指定的 4 小时内将它们存储到文件中应该没有问题。