0

サイズが 10 6 × 10 6要素の 2 次元整数配列を作成したいと考えています。このために、boost ライブラリを使用しています。

boost::multi_array<int, 2> x(boost::extents[1000000][1000000]);

ただし、次の例外がスローされます。

'std::bad_alloc'
what(): std::bad_allocのインスタンスをスローした後に呼び出される終了

問題の解決方法を教えてください。

4

3 に答える 3

5

そんなに巨大な配列を割り当てたくありません。メモリは約 4 テラバイトです。

その配列で何をしたいかによって、次の 2 つのオプションを検討する必要があります。

  • 外部データ構造。アレイはハード ドライブに書き込まれます。最近アクセスされた部分も RAM にあるため、アクセス方法によってはかなり高速になる可能性がありますが、もちろん完全に RAM にある場合ほど高速になることはありません。外部データ構造については STXXL をご覧ください。

    この方法には、配列内のすべての要素にアクセスできるという利点があります (2 番目の方法とは対照的です)。ただし、問題はまだ残っています。少なくとも一般的なデスクトップ アプリケーションについて話している場合、4 テラバイトはハード ドライブ上でも非常に巨大です。

  • スパース データ構造。その配列から実際にはいくつかのアイテムしか必要としないが、これらのアイテムをサイズ 10⁶ ⨯ 10⁶ のスペースでアドレス指定したい場合は、配列を使用せず、マップのようなものまたは両方の組み合わせを使用します。 1024 x 1024 要素の「ブロック」としましょう。これらのブロックを、ブロック インデックス (座標を 1024 で割った値) をキーとしてマップに配置します。

    この方法には、自分で簡単に作成できるため、別のライブラリにリンクする必要がないという利点があります。ただし、10⁶ ⨯ 10⁶ の座標空間全体に分散された要素にアクセスする場合、またはすべての値が必要な場合でも、約 4TB (さらに少し多く) のメモリを使用するという欠点があります。この巨大な「仮想」配列のスマートな部分のみに実際にアクセスする場合にのみ機能します。

    次の (テストされていない) C++ コードは、これを示しているはずです。

    class Sparse2DArray
{
    struct Coord {
        int x, y;
        Coord(int x, int y) : x(x), y(y) {}
        bool operator<(const Coord &o) const { return x < o.x || (x == o.x && y < o,y); }  // required for std::map
    };

    static const int BLOCKSIZE = 1024;

    std::map<Coord, std::array<std::array<int,BLOCKSIZE>,BLOCKSIZE> blocks;

    static Coord block(Coord c) {
        return coord(c.x / BLOCKSIZE, c.y / BLOCKSIZE);
    }
    static Coord blockSubCoord(Coord c) {
        return coord(c.x % BLOCKSIZE, c.y % BLOCKSIZE);
    }

public:
    int & operator[](int x, int y) {
        Coord c(x, y);
        Coord b = block(c);
        Coord s = blockSubCoord(c);
        return blocks[b][s.x][s.y];
    }
};

    a の代わりに(ハッシュ マップ)std::mapを使用することもできますが、型std::unordered_mapの代わりにハッシュ関数を定義する(または代わりに使用する) 必要があります。operator<Coordstd::pair

于 2013-02-03T02:12:51.680 に答える
2

この方法で配列を作成すると、配列はスタック上に作成され、スタックのサイズは制限されます。したがって、その大きな配列を割り当てるのに十分なスペースがないため、プログラムはクラッシュします。

これを解決するには 2 つの方法があります。 new キーワードを使用してヒープ上に配列を作成できますが、後で削除する必要があります。そうしないとメモリ リークが発生します。スタックはまだ有限です。

もう 1 つの方法は、std::vector内部std::vectorで使用してメモリを処理させることです。

于 2013-02-03T01:47:49.023 に答える
0

10 6 ×10 6行列を作成する意図は何ですか? 疎行列 (つまり、10 6有限要素の熱伝達問題の拡散行列) を作成しようとしている場合は、既存の線形代数ライブラリの使用を検討する必要があります。たとえば、trilinosプロジェクトは、作成しようとしているような大規模な疎行列の解決をサポートしています。

于 2013-02-03T02:23:01.087 に答える