使用微小的单元格声明一个巨大的动态数组[C++]

Question

我正在做这个项目。适用下列条件

1. 在这个项目中，我需要创建一个巨大的数组(希望我能够创建一个和~7.13e+17一样大的数组，但是这个目标还在前面)。
2. 数组中的每个单元格可以包含以下三个值中的一个:0、1、2
3. 我使用C++作为我的语言。

我尝试使用普通的动态数组命令。

int * p;
int i;    
i=[size]; //This is calculated somewhere else.
p= new (nothrow) int[i];

但据我所知，这个数组可以使数组的最大大小达到int的最大大小。如果我更改我的代码并使用以下代码

long long * p;
long long i;    
i=[size]; //This is calculated somewhere else.
p= new (nothrow) long long [i];

然后数组中的每个单元格都是“长长”类型，这使得数组的内存非常重。是否有任何方法可以使用long long来创建数组，以确定数组中单元格的数量，并使每个单元格大小为int？

非常感谢，乌里尔。

编辑:获取更多信息。

1. 这个问题主要是理论上的，是我硕士论文的一部分。我仍然希望这个计划能发挥最大的作用。
2. 我现在的工作步骤是让一个包含2.56e+09项的数组工作，快速计算显示我们正在讨论的数组至少为0.6G，这是我的系统应该能够处理的。然而，我无法用当前的编码解决方案实现这一目标，即使所需的空间实际上是4.5GB。

Answer 1

是否有任何方法可以使用long long来创建数组，以确定数组中单元格的数量，并使每个单元格大小为int？

没有理由数组的类型必须与指定大小的变量的类型相同。因此，对指定大小的变量使用long long，然后对数组的类型使用int。

int * p;
long long i;    
i=[size]; //This is calculated somewhere else.
p= new (nothrow) int [i];

但是，当您说需要创建一个“和~7.13e+17一样大”的数组时，我很担心。我不知道你是指字节还是元素，但不管是哪种方式，这对于一个直线数组来说都是非常巨大的。这就进入了千兆字节的数据领域。

在32位程序中，这是不可能的。理论上，您可以拥有高达几千兆字节的数组(尽管在实践中，大多数情况下都要少得多)。

据我所知，在64位程序中，理论上你可以分配一个那么大的数组。然而，我怀疑大多数机器是否真的能处理它。由于这个数据量将远远超过机器中的RAM，操作系统将被迫将这个数组的大部分推入一个页面文件中。但是一个千兆字节大小的页面文件现在将远远超过大多数典型机器上的硬盘空间。

无论哪种方式，您可能都需要认真考虑不同的方案，而不仅仅是一次性分配整个庞大的数组。

Answer 2

由于您希望获得最大的填充密度，所以最好使用位字段：

struct item_pack { 
    char a:2;
    char b:2:
    char c:2;
    char d:2;
};

然后，您可以创建这些对象的数组，并使用代理对象来支持读取和写入单个项--附带条件是，您对代理对象所能做的事情有一些限制，所以您必须对如何使用代理对象有点谨慎。稍微看一下关于vector<bool>的一些文章，应该会提供一些合理的提示--它的大部分特性来自于这种一般的实现类型。尽管作为一个通用容器的缺点，这可以在有限的范围内工作，并提供比大多数明显的替代方案更紧密的信息包装。

Answer 3

在这个项目中，我需要创建一个巨大的数组(希望我能够创建一个和~7.13e+17一样大的数组，但是这个目标还在前面)。

这会调用创建一个专用结构，即以键为索引的la 数字树 (或B-树)，以避免进行大量分配。

大量分配，特别是重新分配，可能会导致不必要的内存碎片。如果将大数组分割成较小的块，那么不仅数组扩展变得容易，而且稀疏数组的表示也变得可能。

注：~7.13e+17大约有60位长。你有能支持这么多RAM的硬件吗？这并不是说我正在密切关注行业，但我简要地听说了NUMA的58位地址总线-但没有任何关于60+位架构。

数组中的每个单元格可以包含以下三个值中的一个: 0、1、2.2。

如果单元格可能只包含3个值(2.2可以表示为2)，则使其具有2位信息。这意味着您可以打包到uint32_t 16值和uint64_t 32值中。

您可以尝试找到一些现有的数字树实现(或滚动您自己的)，并将其用作索引的关键上位。原始索引的剩余部分将是树叶中的索引，这将是一个具有填充值的数组。为了举例说明使用std::map代替trie，未经测试：

enum {
   LS_BITS = 16,
   MS_BITS = 64-LS_BITS
};

enum {
   VALUE_BITS = 2,
   VALUE_MASK = ((1<<VALUE_BITS)-1)
};

// this represents an array of `1<<LS_BITS` values
struct leaf_node {
   uint64_t packed_data[ ((1<<LS_BITS)*VALUE_BITS) / (sizeof(uint64_t)*8) ];
};

// that should be a trie, to provide faster look-up
typedef std::map< uint64_t, leaf_node > big_array_type;

void
big_array_set_value( big_array_type &b, uint64_t index, uint64_t value )
{
   leaf_node &n = b[index >> LS_BITS];
   uint64_t li = index & ((1<<LS_BITS)-1);
   li *= VALUE_BITS;   // convert into bit offset
   uint64_t &x = n.packed_data[ li / (sizeof(uint64_t)*8) ];
   li %= (sizeof(uint64_t)*8);
   x = (x & (VALUE_MASK<<li)) | (value << li);
}

int
big_array_get_value( big_array_type &b, uint64_t index, uint64_t value )
{
   leaf_node &n = b[index >> LS_BITS];
   uint64_t li = index & ((1<<LS_BITS)-1);
   li *= VALUE_BITS;   // convert into bit offset
   uint64_t &x = n.packed_data[ li / (sizeof(uint64_t)*8) ];
   li %= (sizeof(uint64_t)*8);
   return (x >> li) & VALUE_MASK;
}

这样，人们仍然浪费0.5位的信息，因为存储是2位，允许4值，但只使用3。这也可以改进，但访问性能成本要高得多。