布尔值的轻量级矩阵
我需要实现一个非常大的矩阵，比如标准 C 中的 NxN。该矩阵必须存储一个真值表，也就是说
matrix[i][j] = [true|false]
我知道我可以简单地使用 int 矩阵或 boolean type 如果使用 C99，但正在寻找内存方面最轻量级的解决方案。
I need to implement a very large matrix, say NxN in Standard C. The matrix must store a truth table, that is
matrix[i][j] = [true|false]
I know I could simply use a int matrix, or boolean type if using C99, but was looking for the most lightweight solution in terms of memory.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
就内存而言，最轻量级的解决方案是将八个布尔值保存在一个字符中：
然后您可以通过保存每行中的字节来存储
N x 8M矩阵。如果其中许多字节为空，那么您应该使用稀疏矩阵格式，例如压缩备件行。The most lightweight solution in terms of memory is saving eight boolean in a char:
Then you can store a
N x 8Mmatrix by saving the bytes in each row. If many of those bytes are empty then you should use a sparse matrix format, for example compressed spares row.如果矩阵特别稀疏，您可能需要使用哈希实现或列表列表。
此外，如果 i 或 j 小于系统可以存储的最大整数，您可以将布尔位集打包为单个整数，其中每一位对应一个索引。然后，您可以使用按位运算来访问或修改它。
You might want to use a hash implementation or a list of lists if the matrix is particularly sparse.
Also if the i or j is less than the largest integer your system can store you can pack a boolean bitset into a single integer with each bit corresponding to one index. You can then access or modify this using bitwise operations.
这不是 std::bitset 的用途吗？
Isn't it what std::bitset is for ?
如果您想在一位中存储超过 1 个布尔值，则需要使用一些压缩。
压缩仅适用于非随机数据；并且随机访问压缩数据可能会很慢。
最简单的一种方法是 RLE（独立压缩每一行）。稍微复杂一点的是将数据存储在稀疏矩阵中（仅当 0 值远多于 1 时；此方法可以压缩多维数据）。
这里使用了更复杂的压缩：http://crd-legacy.lbl。 gov/~kewu/fastbit/index.html 它被命名为 "字对齐混合压缩方案"
If you want to store more than 1 boolean in single bit, you need to use some compression.
Compression will work only on non-random data; And random access to compressed data can be slow.
Easiest one method is RLE (compress each row independently). A bit more complex is storing data in sparse matrix (only if you have much more 0 values than 1; this method can compress multi-dimensional data).
Much more complex compression is used here: http://crd-legacy.lbl.gov/~kewu/fastbit/index.html It is named "Word-Aligned Hybrid compression scheme"