在磁盘上存储列并读取行

Question

所以我有一个 C++ 代码可以找到方阵的逆矩阵。逆是满的，将它全部保存在内存中是不好的，因为我正在处理数十万列。我的代码一一生成列。找到逆后，我的其余代码需要一行一行。理想情况下，我想按如下方式进行：

重复： 1）找到一列 2）存储在磁盘上 3) 从内存中删除该列。

重复： 1) 从磁盘读取一行 2）对其进行处理（基本上就是线性程序的objective函数） 3) 从内存中删除该行。

这样做的一种方法是按原样在文件中写入矩阵。意思是，我将第一列写为文件中的 "actual" 列，然后我将第二列写在它旁边（这会有点低效），等等。如果我没记错的话，最后一列将花费 O(n^2) 来编写。这样做可以让阅读行变得非常容易。另一种方法是将列写成行，然后再读取列。但是，最后一列将需要 O(n^2) 来读取。第三种方法是使用n个文件，但是打开和关闭n个文件效率低下。

关于如何解决此类问题的任何想法？也许我必须使用数据库（可能 SQL）来使每个条目的读写复杂度为 O(1)？

谢谢。

Answer 1

如果是方阵，那么写个随机存取文件就容易了。例如，如果按行存储矩阵，如...

FILE * f = fopen( FileName, "w+b" );
for(int i = 0; i < MaxRows; ++i) {
    for(int j = 0; j < MaxColumns; ++i) {
        fwrite( &v[ i ][ j ], 1, sizeof( double ), f );
    }
}

现在你可以去任何你想去的地方。只需考虑到您每次都必须应用一个公式：

pos = ( MaxColumns * rowNumber ) + colNumber;

为了在文件中定位自己，您必须使用 fseek()，它以字节为单位，而不是以元素为单位。

假设您想转到第三列的第一个元素。该职位将是...

int pos = ( MaxColumns * 2 ) + 0;

现在您可以 fseek 到那个位置了：

fseek( f, pos * sizeof( double ), SEEK_SET );

然后，比如说，读取值：

double value;
fread( &value, 1, sizeof( double ), f );

所以我的回答是：一旦你将矩阵保存在磁盘中，你就可以无限制地操作它，而不用担心它占用多少。

只是不要忘记关闭文件：

fclose( f );

希望对您有所帮助。

Answer 2

提到的 fseek 解决方案很好。但是，对于大型矩阵来说它可能会非常慢（因为磁盘不喜欢随机访问，尤其是距离很远）。为了加快速度，您应该使用阻塞。

我将展示一个基本概念，如果您需要，可以进一步解释。

首先，您将矩阵分成大小相等的块，如下所示：

块大小的计算方式应使块的列或行可以装入 RAM。

接下来，您将块列保留在内存中，并将第一个生成的 blocksize 列复制到此处。这里黄色部分是您保存在内存中的内容，橙色部分是您的下一个生成列：

完成前 blocksize 列后，将它们转储到单独的文件中（对于我的图像，您可以将这些文件命名为 "A1"、"A7" 和 "A13" ), 然后从下一列块重新开始。

当你以后需要这个矩阵作为行时，反转这个过程。从准备好的文件（例如"A1"、"E1"、"I1"和"M1"）中读取第一行块，逐行处理：

在磁盘上存储列并读取行

Storing columns on disk and reading rows

c++

io

file

matrix