2

我有我正在做的这个项目。以下条件适用

  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”类型，使得数组的内存非常重。有没有办法使用 long long 创建一个数组来确定数组中的单元格数量并让每个单元格的大小为 int？

非常感谢，乌列尔。

编辑：了解更多信息。

  1. 这个问题主要是理论上的，它是我硕士论文的一部分。我仍然希望这个程序尽可能地工作。
  2. 我当前的步骤是使这个工作适用于具有 2.56e+09 项的数组，快速计算表明我们正在谈论一个至少 0.6 GB 的数组，这是我的系统应该能够处理的。然而，即使所需的空间量实际上是 4.5GB，我也无法用我当前的编码解决方案实现这个目标。
4

7 回答 7

7

有没有办法使用 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”的数组时，我很担心。我不知道您是指字节还是元素，但无论哪种方式对于直接数组来说都是非常巨大的。这进入了 PB 级数据的领域。

在 32 位程序中，这是不可能的。从理论上讲，您可以拥有一个高达几千兆字节的数组（尽管实际上大多数时候要少得多）。

据我所知，在 64 位程序中，理论上您可以分配一个那么大的数组。但是，我怀疑大多数机器是否真的能处理它。由于该数据量将远远超过机器中的 RAM，因此操作系统将被迫将该数组的大部分内容推送到页面文件中。但是，PB 大小的页面文件将远远超过目前大多数典型机器上的硬盘空间。

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

于 2010-09-12T18:06:54.837 回答
4

由于您希望最大化打包密度，因此最好使用位字段：

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

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

于 2010-09-12T18:07:47.637 回答
2

在这个项目中，我需要创建一个巨大的数组（希望我能够创建一个与 ~7.13e+17 一样大的数组，但这个目标仍然遥遥领先。）

这需要创建一个专用结构，即以键为索引的 la数字树（或b-tree），以避免进行大量分配。

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

NB~7.13e+17大约 60 位长。您甚至有可以支持这么多 RAM 的硬件吗？这并不是说我密切关注行业，而是我简要地听说过具有 58 位地址总线的 NUMA 拱门——但对 60 位以上的拱门一无所知。

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

如果单元格可能仅包含 3 个值（2.2 可以表示为 2），则使其成为 2 位信息。这意味着您可以打包到uint32_t16 个值和uint64_t32 个值中。

您可以尝试找到一些现有的数字树实现（或自己滚动）并用作索引的关键高位。原始索引的剩余位将是到树叶的索引，这将是一个包含压缩值的数组。举例说明使用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 个。这也可以改进，但访问性能成本要高得多。

于 2010-09-12T18:21:32.197 回答
1

但据我了解，这个数组创建了一个可能最大大小为 int 最大大小的数组。如果我更改我的代码并使用以下代码

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

所以没有必要把它变成一个long long数组。相反，您甚至应该将其char设为数组甚至更少。

如果您只需要存储三个不同的值，则应该使用 achar或任何其他类型中的位。然后制作一个数组。

Achar通常是 1 个字节，因此是 8 位。要存储 3 个值，需要 2 位；因此，您可以在 a 中存储 4 个值char。

使用二进制掩码，您应该找到一种优化方法。

于 2010-09-12T18:13:48.980 回答
1

用于指定数组大小的大小必须是 type size_t。new表达式中使用的类型是数组元素的类型。无论i您的示例中的类型如何，它都会被转换size_t为创建数组。

现在在 32 位机器上，最大值size_t约为 4e+9，因此制作大小为 1e+17 的数组是正确的。在 64 位机器上，size_t理论上可以达到 1e+19 左右，但是你不可能拥有接近这个数量的内存，所以分配会失败。

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

于 2010-09-12T18:41:04.270 回答
1

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

于 2010-09-12T17:32:38.160 回答
1

由于存在有限的值列表，因此可能只使用 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;
}
于 2010-09-12T17:40:53.600 回答