我正在尝试计算 20x20 布尔矩阵的数百万 (10 8 ) 个排列。我能够很快地计算它们。之后,我需要使用标准输出显示它或将其存储到文件中。您认为可以在 4 小时内以某种方式管理这么多数据吗?
3 回答
10 18操作?让我们看看...您的 PC 可能不会比每秒10 9到 10 10条指令更好。所以,你至少需要 10 9到 10 10秒来做 10 18次操作,也就是超过 31 年的时间。这速度够快吗?在 31 年的过程中,您的 PC 是否还活着并拥有不间断的电源?
一个 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;
}
};
并在main
for 循环中
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 分钟。在当前的硬件上,这应该更快。
使用 10^8 个排列,每个排列打包成 50 个字节(400 位),它将提供大约 5 GB 的数据。应该可以在普通磁盘上以每秒 100 MB 的速度将其存储到磁盘上的文件中——5 GB 数据的总写入时间为 50 秒。
因此,只要您可以足够快地生成排列,在指定的 4 小时内将它们存储到文件中应该没有问题。