5

私は、100,000,000,000 (100 Billion) 未満のすべての素数を計算するために ~12GB の RAM を使用する C++ で素数ふるいプログラムを作成しました。

このプログラムは、Visual Studio 2012 (x64 用にセットアップされたプロジェクト) および 64 ビット Linux の g++ でコンパイルすると正常に動作します。ただし、Windows 7 Home Premium 64 ビットの cygwin64 で g++ を使用してコンパイルすると、~2GB を超える RAM を使用しようとすると (~17,000,000,000 を超えるふるいを実行すると)、セグメンテーション エラーが発生します。

タスクマネージャーのプロセス名の横に*32がな​​いため、64ビットプロセスとして実行されていると確信しています。

コード：

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
using namespace std;

long long sieve(long long n);

int main(int argc, char** argv) {
    const long long ONE_BILLION = 1000*1000*1000;
    if(argc == 2)
        cout << sieve(atol(argv[1])) << endl;
    else
        cout << sieve(ONE_BILLION * 100) << endl;
}

long long sieve(long long n) {
    vector<bool> bools(n+1);
    for(long long i = 0; i <=n; i++) 
        bools[i] = true;

    double csqrtn = sqrt(n);
    for (long long i = 2; i < csqrtn; ++i)
        if (bools[i]) 
            for (long long j = i * i; j < n; j += i) 
                bools[j] = false;

    long long primes2 = 0;
    for (long long i = 2; i < n; i++) 
        if (bools[i]) 
            primes2++;

    return primes2;
}

Visual Studio で正常に動作:

ここに画像の説明を入力

x64 Linux で正常に動作:

ここに画像の説明を入力

次のコマンドでコンパイル:

$ g++ -O3 sieve.cpp -o sieve.exe

180 億の実行は失敗します。

$ ./sieve.exe 18000000000
Segmentation fault (core dumped)

正常に動作します (タスク マネージャーによると 2,079,968 K のメモリを使用していますが、私の評判では 3 つ目のリンクを投稿することはできません)。

$ ./sieve.exe 17000000000
755305935

g++ バージョン:

$ g++ --version
g++ (GCC) 4.8.1
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

注: これを自分で実行しようとすると、かなり時間がかかる場合があります。ビジュアル スタジオで 1000 億を実行する 3570k @ 4.2GHz では、約 30 分、10 億で約 10 秒かかります。ただし、ベクトルの割り当てだけでエラーを再現できる場合があります。

編集:私は明示的に質問をしなかったので:なぜこれが起こるのですか? これは cygwin64 dll の制限ですか (cygwin64 は約 1 か月前に完全にリリースされたばかりです)。

4

1 に答える 1

0

cygwin のメモリ制限を増やしてみてください。This cygwin documentationは、64ビットプラットフォームでのデフォルトの最大アプリケーションヒープサイズが4GBであることを示唆しています...ただし、これは64ビットプラットフォームでの32ビット実行可能ファイルを参照している可能性があります...最大ヒープサイズについて持っています。

于 2013-08-18T02:06:50.030 に答える