0

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

4

3 回答 3

4

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

于 2013-03-25T23:56:58.823 回答
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 分钟。在当前的硬件上,这应该更快。

于 2013-03-26T00:44:00.360 回答
1

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

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

于 2013-03-26T00:44:49.097 回答