稀疏矩阵快速转置算法分析

深藏阁楼爱情的钟 2022-06-07 08:51 338阅读 0赞

#### 稀疏矩阵的相关知识 ####

*  矩阵通常是使用二维数组来进行模拟的，并且可以通过下标快速的访问二维数组里面的元素，但是矩阵里面包含大量重复元素的情况，使用二维数组就很浪费空间的；
 *  对于含有大量重复元素的矩阵，就可以使用稀疏矩阵的思想来进行处理，但是对于是否为稀疏矩阵，有没有特别严格的标准来进行判断，稀疏矩阵不在采用二维数组的方式进行处理，而是使用三元素来进行处理；

typedef struct
    {
        int col;　//表示矩阵里面元素的列数；
        int row;//表示矩阵里面元素的行数；
        int value;//表示这里面元素的值；
    } term;
    //用来存放上述结构的一个数组;
    term my[MAX_SIZE];

*  为了便于稀疏矩阵循环条件的判定，可以使用`term[0].col`表示有效列的列数，`term[0].row`表示有效行的行数，`a[0].value`表示有效元素的个数，并且三元组按照行升序，同行按照列升序的方式进行排列；
 *  对于常见的二维数组表示的矩阵，首先需要进行遍历，将其转换为三元组结构数组表示的稀疏矩阵形式；

void change_to(int row, int col, int array[row][col], term mynew[MAX_SIZE])
    {
        int i, j;
        //按照先行后列的方式进行遍历，得到的三元组就是有序排列的;
        for (i = 0; i < row; i++)
        {
            for (j = 0; j < col; j++)
            {
                if (array[i][j] != 0)
                {
                    mynew[val].row = i;
                    mynew[val].col = j;
                    mynew[val].value = array[i][j];
                    val++;
                }
            }
        }
        //分别用来表示矩阵的行数以及列数，非０元素的个数；
        mynew[0].row = row;
        mynew[0].col = col;
        mynew[0].value = val - 1;
    }

*  按照上面的代码进行转换之后，可以得到这样的结果；  
    ![得到的结果是符合要求的][SouthEast]
 *  稀疏矩阵的转置可以使用两种方式来进行转置：
    
     *  第一种方法通过分别遍历元素的列数和所有元素的个数两层`for`循环来进行遍历；
        
            void transpose(term a[], term b[])
            {
            int n, i, j, currentb;
            n = a[0].value;
            b[0].row = a[0].col;
            b[0].col = a[0].row;
            b[0].value = n;
            if (n > 0)
            {
                currentb = 1;
                for (i = 0; i < a[0].col; ++i)
                {
                    for (j = 0; j <= n; j++)
                    {
                        if (a[j].col == i)
                        {
                            b[currentb].row = a[j].col;
                            b[currentb].col = a[j].row;
                            b[currentb].value = a[currentb].value;
                            currentb++;
                        }
                    }
                }
            }
            }
        
         *  对于这种转置算法，时间复杂度是`n^2`这种级别；
     *  通过上述方法进行转置，得到的结果同样是有序的；  
        ![这里写图片描述][SouthEast 1]
     *  `-------`之前的表示的是原始稀疏矩阵，在`-------`之后的表示的是转置之后的稀疏矩阵；
     *  第二种方法是时间复杂度比较低的快速转置算法；
        
            void fasttranspose(term a[], term b[])
            {
            int rowTerms[MAX_COL], startingPos[MAX_COL];
            int i, j, numCols = a[0].col, numTerms = a[0].value;
            b[0].row = numCols;
            b[0].col = a[0].row;
            b[0].value = numTerms;
            
            if (numTerms > 0)
            {
                for (i = 0; i < numCols; i++)
                    rowTerms[i] = 0;
                for (i = 1; i <= numTerms; i++)
                {
                    rowTerms[a[i].col]++;
                }
                startingPos[0] = 1;
                for (i = 1; i <= numCols; i++)
                    startingPos[i] = startingPos[i - 1] + rowTerms[i - 1];
                for (i = 1; i <= numTerms; i++)
                {
                    j = startingPos[a[i].col]++;
                    b[j].row=a[i].col;
                    b[j].col=a[i].row;
                    b[j].value=a[i].value;
                }
            }
            }
 *  接下来分析快速转置算法的执行过程，来尝试理解这个算法：
 *  首先因为需要进行的是元素的转置操作，将列变为行，所以对原始矩阵采取的是按照列进行遍历的方式，通过遍历的方式得到两种信息：每一列具有元素的个数，以及这一列第一个元素应该放置的位置；
 *  1.这段代码首先得到的是的一一个初始化`numcols`个元素为`0`的数组；

for (i = 0; i < numCols; i++)
        rowTerms[i] = 0;

*  2.这段代码利用元素的下标作为索引，通过遍历所有的元素，得到的是每一列里面包含元素的个数；

for (i = 1; i <= numTerms; i++)
        rowTerms[a[i].col]++;

*  3.接下来的代码通过每一列的元素个数，和起始放置元素的位置，一开始的起始位置是`1`，统计得到每一列第一个元素应该放置的起始位置；

for (i = 1; i <= numCols; i++)
        startingPos[i] = startingPos[i - 1] + rowTerms[i - 1];

*  ４.然后进入最关键的一个循环，这个循环通过遍历所有的元素，找到和初始元素对应的位置，来完成稀疏矩阵的转置；

for (i = 1; i <= numTerms; i++)
            {
                j = startingPos[a[i].col]++;
                b[j].row=a[i].col;
                b[j].col=a[i].row;
                b[j].value=a[i].value;
            }

*  再来通过代码执行的结果来理解算法执行的过程：
 *  1.这是一开始的矩阵；  
    ![这里写图片描述][SouthEast 2]  
    
    
     *  按照列进行分析得到的信息，这四列包含的元素个数分别为`４，２，０，１，２`一共是`9`个元素，这个信息保存在`rowTerms`数组里面；
     *  按照列升序，列里面行升序的原则得到的数值排列信息应该是`{ {1,1,2,5},{5,6},{},{1},{1,3}}`,通过算法还应该得到的信息是每一列第一个元素的位置`{1,5,7,8}`，这个信息保存在`startingPos`里面，这里面元素的信息会随着该列填充一个元素之后进行增长；
 *  １.第一个`for`循环执行的过程是完成初始化操作，这就不再进行展示，但是需要来跟踪这里面数据的变化过程；
 *  2.首先来观察`rowterms`数组里面的数据；  
    ![这里写图片描述][SouthEast 3]
 *  数组里面元素的统计是符合要求的；
 *  然后是`startingPos`里面的元素；  
    ![这里写图片描述][SouthEast 4]
 *  但是对于`startintPos`里面元素的值，再每次放置元素之后都会进行改变，用于指向下一个元素应该放置的位置；这个位置是通过变量`j`来进行统计的；
 *  改变之后的元素元素的改变情况  
    ![这里写图片描述][SouthEast 5]
 *  对于这里面的前面`5`个元素进行`-1`操作，得到的最后一次放置元素的位置；
 *  最后的到的结果是  
    ![这里写图片描述][SouthEast 6]
 *  对比这张结果图来验证每一列第一个元素应该放置的位置：
 *  ![这里写图片描述][SouthEast 7] 应该放置在第一个位置；
 *  ![这里写图片描述][SouthEast 8]　应该放置在第五个位置；
 *  ![这里写图片描述][SouthEast 9]应该放置在第七个位置；
 *  ![这里写图片描述][SouthEast 10]应该放置在第八个位置；
 *  对于这个算法的时间复杂度明显下降，但是空间复杂度在上升，因为多使用了两个数组空间，时间复杂度属于线性；

[SouthEast]: /images/20220607/e9c459ad34ad43e89a7d98ced2578ac1.png
[SouthEast 1]: /images/20220607/d301d89241d64da9a449984885c9a792.png
[SouthEast 2]: /images/20220607/091c481955614b4c88de70113376702e.png
[SouthEast 3]: /images/20220607/e4a39ea763bc47d18d777bccb185a137.png
[SouthEast 4]: /images/20220607/56250ddf3afb4fa1b1ae7ce2ee45a933.png
[SouthEast 5]: /images/20220607/4bb1fa2c50754743a1a04de88b17d39d.png
[SouthEast 6]: /images/20220607/7bbf7fc77da34cf6bab4c78c14faf963.png
[SouthEast 7]: /images/20220607/e2020615aaa047ff93d72ac402ed7a02.png
[SouthEast 8]: /images/20220607/35d609d4defa400dabef3f6ebc077406.png
[SouthEast 9]: /images/20220607/f93c5feb991f439aaa873112e164c8ed.png
[SouthEast 10]: /images/20220607/4e84c9bddd9d45b5b4b59b7da24cf730.png