C中的稀疏矩阵存储-Java 学习之路

我有一个非对称的稀疏矩阵 . 稀疏性有点随机，我不能指望距离对角线一定距离的所有值 .

但是，它仍然很稀疏，我想减少矩阵的存储需求 . 因此，我试图找出如何按顺序存储从第一个非零开始的每一行，直到我到达最后一个非零 .

也就是说，如果行m的第一个非零出现在第2列，而最后一个非零出现在第89列，我想存储在A [m]行2-> 89中 .

由于每行不具有相同数量的非零，因此我将使A的所有行具有相同数量的元素，并且对于具有较少数量的非零元素的行，将零填充到行的末尾 .

我如何在C中进行此翻译？我实际上没有一个原始的完整矩阵来复制值（原始矩阵以CSR形式出现在我身上） . 如果我在fortran中执行此操作，我可以将我的数组定义为二维，并且通过跟踪非零列的开始/停止值并将其存储为每行，每行都是可变长度 .

我将尝试演示如下：

这是我所知道的值的矩阵表示 - 对于每个值，我知道行和列的位置

[1    2    3    4                   ]
  [   5    6    7    8                ]
  [       10    11    12    13        ]
 m[   14    15    16    17       18   ]
  [         19    20    21         22 ]

现在这一行 m 在第一个非零和最后一个非零之间有最大的"span"所以我的新矩阵将是 5x[span of row m]

[1     2     3     4          ]
  [5     6     7     8          ]
  [10    11    12    13         ]
 m[14    15    16    17       18]
  [19    20    21       22      ]

如你所见，行 m 不需要零填充，因为它是最长的"span"

其他行现在都将行0作为第一个非零，并在每个非零之间保持零列的间距 .

3 回答

我将它实现为一个参差不齐的数组，A [n] [0]总是返回对角线上的元素 . A [n] [1]将项目返回到对角线的右侧，A [n] [2]将项目返回到对角线的左侧，等等 . 然后，您只需要一个将矩阵索引[i，j]映射到不规则数组索引[r] [s]的函数 .

这具有稀疏性的优点，并且如果您的值保持接近对角线，则阵列不会很长 .

或者，你可以有这个定义：

struct Row
{
    int InitialOffset;
    int NumElements;
    int[] Values;
}

然后你会有一个Row [] . 检索基于矩阵索引的值如下所示：

//matrix is merely an array of rows...
int GetValue(*matrix this, int i, int j)
{
    Row CurrentRow = (*this)[i];
    if (CurrentRow.InitialOffset > j)
        return 0;
    else if (CurrentRow.InitialOffset + CurrentRow.NumElements < j)
        return 0; 
    return CurrentRow.Values[j - CurrentRow.InitialOffset]
}

我的C语法有点朦胧，但你应该明白这个想法 .

根据您的演示，我会建议：

struct Matrix
{
    int[,] Data
    int[] StartOffset;
    int[] NumberElements;
}

使用如下......

int GetValue(*Matrix this, int i, int j)
{
    if (this.StartOffset[i] > j)
        return 0;
    else if (this.StartOffset[i] + this.NumberElements[i] < j)
        return 0; 
    return this.Data[i, j-this.StartOffset[i]];
}

您的初始化过程看起来像这样

//Data is a struct that holds row index, col index, and value
Matrix* InitMatrix (*Data values, int numVals)
{
    //loop through values to find longest row and number of rows
    //create new matrix, malloc matrix for longrow * numRows
    //malloc numrows elements for StartOffset and NumItems
    //foreach row, find min() and max()-min() of col indexs and 
    //store in StartOffset and NumItems
}

您需要进行一些处理，但数据压缩并不便宜 .

回复于 2024-04-23T17:54:24+08:00

3

另一种方法是使用链接结构（如果矩阵非常稀疏，非常有效，不如填充更多） . I hinted at the implementation in a earlier answer .

我将继续执行连续运行，我不确定您是否真的需要/需要使用相等长度的行 . 为什么不使用衣衫褴褛的阵列？

回复于 2024-04-23T17:54:24+08:00
1
Derek，你在其中一条评论中提到过要使用单个malloc . 这意味着你知道你有多少非空元素 . 鉴于此，tt可以将稀疏矩阵存储在一个数组中，该数组每个元素保存矩阵元素的值，并将"location delta"保存到下一个元素 . 就像是：
```
struct melem {
    int value; // value of data
    int offset; // offset to next element
}

struct melem matrix[num_nonempty_elements];

...

// Note: this is pseudocode!
matrix[row*COLS + col].value = a[row][col];
matrix[row*COLS + col].offset = (row*COLS + col)_[i] - (row*COLS + col)_[i-1];
```
编辑：考虑一下，这与链表方法非常相似，但需要1次分配 . OTOH，可能需要更多计算才能访问所需的单元格 .
回复于 2024-04-23T17:54:24+08:00

C中的稀疏矩阵存储

3 回答

相关问题