c++ - 包含许多零的矩阵的数据结构？

Question

在 C++ 中，我必须在 RAM 中保存一个非常大的方阵，它由大约 90%(零的真实频率取决于用户输入)的零组成。为所有这些零分配内存会浪费 RAM。

如何制作一个使用少量 RAM 并且可以方便地使用类似 instance.getElement(row,column) 的方法将元素放入这个大矩阵的类？

Answer 1

有很多方法可以去。但首先要考虑的是，这样做会大大提高性能，因为访问元素会变得更加复杂。其次，你将无法使用像 LAPACK 这样著名的库，因为据我所知，它们不为如此复杂的数据结构提供任何接口(interface)。所以，每次你想做一些数学运算时，你要么解压缩你的矩阵并将其展平，要么你必须重新开发代码来执行你想做的操作，这并不是一件容易的事去做。从事 LAPACK 工作的人们对此进行了多年研究。

我的意思是:在做之前考虑后果。

现在，在提到后果之后，我可以提到一种方法。

1. 将您的矩阵想象成一个平面阵列，按 column major 排序(因此在内存中一列又一列)，在内存中是连续的。
2. 现在这个矩阵是一个有很多零的列表。您的问题是:我们如何消除这些零？

好吧，有很多种方法，每种方法都会有不同的计算复杂度，具体取决于您的应用程序，让我举一些方法:

• 你可以使用 linked list ，其中每个元素都可以是 std::pair，包含当前矩阵元素的值和下一个可用元素的索引。

• 您可以使用链表，也可以使用某些压缩软件的工作方式，计算每个元素之前有多少个零，然后将其存储在每个元素的容器中。

你看，真的有很多路要走……我可以考虑和猜测另外一些。但问问自己:您正在寻找的计算复杂度是多少？

希望这对您有所帮助。