0

20x20 ブール行列の数百万 (10 8 ) の順列を計算しようとしています。私はそれらを非常に速く計算することができます。その後、標準出力を使用してこれを表示するか、ファイルに保存する必要があります。この量のデータを、たとえば 4 時間で処理できると思いますか?

4

3 に答える 3

4

10 18操作？見てみましょう... お使いの PC は、おそらく 1 秒あたり 10 9～ 10 10命令よりも優れているわけではありません。したがって、10 18回の操作を行うには少なくとも 10 9～ 10 10秒必要であり、これは 31 年以上かかります。それは十分に速いですか？あなたの PC は 31 年間、まだ生きていて、途切れることなく電力を供給できますか?

于 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 分かかりました。その 10 回の書き込みには、1 時間または場合によっては 90 分かかる場合があります。現在のハードウェアでは、これはより高速になるはずです。

于 2013-03-26T00:44:00.360 に答える
1

それぞれが 50 バイト (400 ビット) にパックされた 10^8 順列では、約 5 GB のデータが得られます。通常のディスクでは 1 秒あたり 100 MB の速度でディスク上のファイルに保存できるはずです。5 GB のデータの合計書き込み時間は 50 秒です。

したがって、順列を十分に高速に生成できれば、指定された 4 時間以内に順列をファイルに保存しても問題ありません。

于 2013-03-26T00:44:49.097 に答える