c++ - 创建大小为 int arr[1000000][1000000] 的大型二维数组

Question

我想创建一个大小为 10⁶ × 10⁶ 元素的二维整数数组。为此，我使用了 boost 库:

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

但它抛出以下异常:

terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

请告诉我如何解决这个问题。

Answer 1

你真的不想分配这么大的数组。内存约为 4 TB。

根据您想对该数组执行的操作，您应该考虑两种选择:

• 外部数据结构。数组将写入硬盘。最近访问的部分也在 RAM 中，因此取决于您访问它的方式，它可能非常快，但当然不会像完全在 RAM 中那样快。看看STXXL用于外部数据结构。

  此方法的优点是您可以访问数组中的所有元素(与您将看到的第二种方法相反)。然而，问题仍然存在:即使在硬盘驱动器上，4 TB 也非常大，至少在谈论一般桌面应用程序时是这样。

• 稀疏数据结构。如果您实际上只需要该数组中的几个项目，但您想在大小为 10⁶ ⨯ 10⁶ 的空间中处理这些项目，请不要使用一个数组，但类似于 map 或两者的组合:在“ block ”中分配数组，比方说 1024 x 1024 元素。将这些 block 放入 map 中，同时引用 block 索引(坐标除以 1024)作为 map 中的键。

  这种方法的优点是您不必链接到另一个库，因为它可以很容易地由您自己编写。但是，它的缺点是，如果您访问分布在整个 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];
      }
  };
  

  而不是 std::map你也可以使用 std::unordered_map ( HashMap )但必须定义一个哈希函数而不是 operator<对于 Coord输入(或改用 std::pair)。