4

我试图从我的记忆中挤出尽可能多的东西。我有一个4.9999995e13整数矩阵，但它们只需要是真或假 - 基本上我只需要为这些整数中的每一个存储一个位。

我知道 C 中没有单个位类型（也许有人可以向我解释为什么），而且我也知道如果short short int存在 a 它将是 1 个字节，与 char 相同。然而，C 中的所有逻辑运算都返回整数（以及一些其他函数）。

所以我的问题是：

  • 有什么方法可以创造short short int存在吗？
  • 如果我改为使用char，我会因为必须完成所有转换而导致性能下降int吗？
  • 还有另一种我想念的方式吗？

以防万一，我正在使用 GCC 为 C99 进行编译。

编辑我刚刚在这个维基百科页面上看到有一种_Bool类型，这实际上是标准的吗？

4

8 回答 8

6

该_Bool类型在最新版本的 C 中是标准的，但这仍然不是您想要的，因为 a_Bool仍然占用至少一个字节（根据char定义， a 也是如此）。

不，如果你想要那么多布尔位，你需要将它们打包到一个位域或位数组中。C 中的位域没有标准数据类型，因此您还必须编写自己的宏或函数来获取特定偏移量的位。我还希望您将在具有大量 RAM 的 64 位计算机上运行它，否则您将耗尽内存并且速度很快。

于 2011-07-14T18:00:39.907 回答
5

您想要的是位图（或维基百科所称的位数组）。

并且没有 a 之类的东西short short int，它只是charC 中最小的整数存储类。

使用这种方法时可能会有一些性能开销，但不是因为隐式转换为整数，而是因为操作位图比直接操作数组成员更棘手。

一个小例子可能有助于说明：

使用普通整数矩阵：

诠释垫[8 * 8]；// 假设行主要顺序
int is_element_set(int x, int y) {
  返回垫子[y*8 + x];
}

使用位图：

unsigned char mat[8]; // assuming CHAR_BIT == 8
int is_element_set(int x, int y) { 
  return mat[y] & (1 << x);
}
于 2011-07-14T18:02:45.203 回答
5

你有大约 50 TB 的数据。您想一次将它们全部放入 RAM 中吗？使用多于一位的 RAM 来保存一位信息将是完全疯狂的，即便如此，您的计算机也必须与这个星球上最大的超级计算机一样大。忘记位打包的性能。你将不得不担心完全不同的事情。

于 2011-07-14T18:56:02.697 回答
4

5e13 大约是 5.6 TB 的存储空间，您只需要代表您的位域。可能有更好的方法来处理您的问题。

于 2011-07-15T12:34:16.080 回答
1

也许您可以使用 ANSI C 中可用的位域结构的一些明智实现。

像这样的东西：

typedef struct node_t_
{
    char bit0 : 1;
    char bit1 : 1;
    char bit2 : 1;
    char bit3 : 1;
    char bit4 : 1;
    char bit5 : 1;
    char bit6 : 1;
    char bit7 : 1;
} node_t;

然后，您可以创建一些快速函数（可能是宏）来获取和设置此矩阵中的元素。不过，我从来没有实现过这样的东西。

于 2011-07-14T19:03:22.520 回答
1

C99stdbool.h允许使用bool. 但是这里你的问题是 4.9999995e13/8 会给出或多或少的 6.2500e+12 （$10^9$ 是 Gbyte，$10^12$ 是 Tbyte），所以你需要超过 6 Tbytes 的真实 + 虚拟内存（要幸运的）。这表明您做错了其他事情。您需要在可以使用更少内存处理的子问题中“扩展”您的问题。

于 2011-07-14T19:28:01.620 回答
1

正如其他人所建议的那样，您可能应该使用位域。

此外，如果您只是使用真/假值，并且其中一个值比另一个值少得多，请考虑使用隐式编码。您可以使用地图数据结构轻松完成此操作。当您使用图表时，如果您的图表非常稀疏，这将为您节省大量内存。如果将其与上面的位打包技术结合使用，您甚至可以将其全部放入 RAM。不过，必须对索引非常聪明。

如果您不关心在处理过程中对性能的影响（即，如果您更担心存储它而不是处理它），您可以做的另一件事是通过块中的压缩算法运行结构。有一个用于 bzip2 的 C 库，它可能会为您节省 90% 或更多类似的东西。缺点是这需要（非常！）很长时间。您可能会从动态马尔可夫压缩 (DMC) 等按位压缩器中获得相当的性能，而且速度要快得多。

于 2011-07-15T05:04:38.223 回答
0

我试图从我的记忆中挤出尽可能多的东西。

如果这是真的，那么您就不会浪费 8 位来存储 1 位的数据。你会使用一个位域。

如果您对矩阵的内容类型有所了解，则可以使用其他优化。例如，如果您知道大多数矩阵通常设置为零，那么您可以只存储设置为 1 的元素的 x,y 对。

如果没有，那么 4.9999995e13 将占用大约 6 TB 的 RAM！

于 2014-04-09T02:26:29.237 回答