创建大型的2d数组int arr [1000000] [1000000]

Question

我想创建一个大小为10 ⁶ ×10 ^6个元素的二维整数数组.为此,我正在使用boost库:

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

但它抛出以下异常:

抛出'std :: bad_alloc'的实例后调用terminate
():std :: bad_alloc

请告诉我如何解决问题.

Answer 1

你真的不想分配一个巨大的数组.它的内存大约是4TB.

根据您对该阵列的要求,您应该考虑两个选项:

• 外部数据结构.该阵列将写在硬盘上.最近访问的部分也在RAM中,因此根据您访问它的方式,它可以非常快,但当然永远不会像在RAM中完全一样快.看看STXXL的外部数据结构.

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

• 稀疏数据结构.如果您实际上只需要该数组中的几个项目,但是您想要在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];
      }
  };
  

  取而代之的是std::map,你还可以使用std::unordered_map(哈希地图),但必须定义一个哈希函数,而不是operator<对Coord类型(或使用std::pair替代).