声明一个巨大的动态数组与细胞[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？

非常感谢， Uriel。

编辑：进一步的信息。

1. 这个问题主要是理论上的，它是我硕士论文的一部分。我仍然希望这个计划尽可能地发挥作用。
2. 我现在的步骤是使用2.56e + 09项的数组进行这项工作，快速计算显示我们正在讨论的数组至少有0.6千兆字节，这是我的系统应该能够应对的。然而，即使所需的空间数量真的达到4.5GB，我仍无法用我当前的编码解决方案实现这一目标。

Answer 1

是否有任何方式来创建使用长长来确定所述阵列中细胞的数目和大小具有INT的每一个细胞的阵列？

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

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

---

不过，我很担心，当你说你需要创建一个数组“大如〜7.13e + 17”。我不知道你的意思是字节还是元素，但是对于一个直线阵列来说，这种方式是非常巨大的。这正在进入PB级数据领域。

在32位程序中，这根本不可能。从理论上讲，你可以有一个数组达到几千兆字节（尽管在实践中大多数时候会少得多）。

在一个64位程序中，理论上你可以分配一个很大的数组，据我所知。然而，我怀疑大多数机器实际上可以处理它。由于该数据量远远超过机器中的RAM，因此操作系统将被迫将该数组的大部分推送到页面文件中。但是，PB级大小的页面文件现在远远超过大多数典型机器上的硬盘空间。

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

Answer 2

由于所有的值都小于255，所以您可能希望将此数组作为char。 在任何情况下，指针类型都不会规定相同的最大可分配大小。

Answer 3

由于有一个有限的值列表，所以可能只使用一个char数组。一个字节可以很容易地保存三个不同的值。

值：
0 - > 0
1 - > 1
2.2 - > 2

存储值：

char values[i]; 
values[i] = 0; 
values[i] = 1; 
values[i] = 2; // really the 2.2 value 

检索值：

int zero = values[i] - 0; 
int one = values[i] - 0; 
double two_point_two values[i] - 0; 
if (two_point_two == 2) 
    two_point_tow = 2.2; 

小需要额外的注意力来获得最后的值，但数组会很小（1字节）。

数组分配：

int main() 
{ 
    // static allocation requires a const size 
    const int static_array_size = 100; 
    char static_array[static_array_size]; 
    std::cout << "static array size is:" << sizeof(static_array) << std::endl; 

    // heap allocation can vary in size (i.e. non const heap_array_size variable) 
    int heap_array_size = 200; 
    char* heap_array = new char[heap_array_size]; 
    std::cout << "static array size is:" << sizeof(heap_array_size) << std::endl; 
} 

Answer 4

既然你想最大限度地提高封装密度，你可能是最好关闭使用位字段：

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

然后，您可以创建这些数组，并使用代理对象以支持读写个别项目 - 条件是你可以用代理对象做多少限制，所以你必须小心你如何使用它。有些关于vector<bool>的文章应该提供一些合理的提示 - 其大部分特征来自这种通用类型的实现。尽管通用容器存在缺点，但它可以在有限的范围内工作，并且比大多数明显的替代方案提供更紧密的信息包装。

Answer 5

但据我所知，这个数组产生了一个最大尺寸为int的数组。如果我更改我的代码并使用以下代码

这绝对是错误的！数组的大小完全独立于数组类型的最大值。

所以没有必要使它成为long long阵列。相反，你甚至应该使它成为一个char数组，甚至更少。

如果你只需要存储三个不同的值，你应该玩char或任何其他类型的位。然后制作这些数组。

A char通常是1个字节，所以8位。要存储3个值，您需要2位;因此您可以将4个值存储在char中。

使用binary masks你应该找出一种方法来优化它。

Answer 6

在这个项目中我需要创建一个巨大的数组（希望我能创造一个大如〜7.13e + 17，但这一目标仍然高达遥遥领先。）

那调用创建一个专用结构，一个la digital tree（或b-tree），键是索引，以避免执行大量分配。

大量分配和特别是重新分配可能会导致不必要的memory fragmentation。如果将大数组分成更小的块，那么不仅数组扩展变得容易，而且稀疏数组的呈现变得可能。

N.B. ~7.13e+17大约有60位长。你甚至有硬件可以支持那么多的RAM吗？这并不是说我密切关注着行业，但是我简要地听说过使用58位地址总线的NUMA拱形结构 - 但没有任何关于60位拱形结构的东西。

数组内的每个单元格可以包含三个值之一：0,1,2.2。

如果单元格可能只包含3个值（2.2可以表示为2），使其成为2位信息。这意味着您可以将数值打包成uint32_t 32值。

您可以尝试找到一些现有的数字树实现（或自己推出）并将其用作索引的关键高位。原始索引的剩余位是树叶的索引，它将是一个具有打包值的数组。为了举例说明代替特里结构的使用std::map，未测试：

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被使用。这也可以得到改善，但是访问性能成本要高得多。

Answer 7

用于指定数组大小的大小需要为size_t。 new表达式中使用的类型是数组元素的类型。无论您的示例中的i的类型如何，它都将转换为size_t以创建阵列。

现在在一台32位机器上，最大的size_t大概是4e + 9，所以制作一个大小为1e + 17的数组是正确的。在64位计算机上，理论上size_t可能会上升到1e + 19左右，但您无法在任何位置接近该内存量，因此分配将失败。

因此，您需要某种稀疏的数据结构，正如其他人所讨论的。这里的关键是决定你的3个值中哪一个最常见，并且只存储数组是其他2个值之一的值。您可以使用std :: map来保存这些值（甚至支持使用[index]语法）或其他类型的值，具体取决于您想要执行的操作以及数据的细节。