三元表实现的稀疏矩阵的快速转置

分析与cpp/python实现

总的来说,交换行列索引+放到正确位置

python实现与分析

以下大部分代码都用于输出和分析思路,若需查看实现,请向下移至c++实现。

# 一些初始化和引入
import pandas as pd
col =["col", "row","value"]
matrix_dst1,matrix_dst2 = [],[]
from IPython.display import display

首先,初始化一个待转置的矩阵

matrix_src = [[1, 2, 12], [1, 3, 9], [3, 1, -3], [3, 6, 14], [4, 3, 24], [5, 2, 18], [6, 1, 15], [6, 4, -7]]
pd.DataFrame(matrix_src, columns=col)
col row value
0 1 2 12
1 1 3 9
2 3 1 -3
3 3 6 14
4 4 3 24
5 5 2 18
6 6 1 15
7 6 4 -7

转置,无非就是把行列索引给交换就行了。转置过来以后是这样。

for item in matrix_src:
    matrix_dst1.append([item[1],item[0],item[2]])
pd.DataFrame(matrix_dst1, columns=col)
col row value
0 2 1 12
1 3 1 9
2 1 3 -3
3 6 3 14
4 3 4 24
5 2 5 18
6 1 6 15
7 4 6 -7

这时候,我们发现一个问题:三元组应该是按照col主序的,交换以后就是按照row主序了。

所以,我们需要在交换col和row的同时调整顺序,而这里调整顺序很像计数排序。

首先需要添加计数:

count = [0]*len(matrix_src)
for item in matrix_src:
    for i in range(item[1],len(matrix_src)):
        count[i]+=1
count
[0, 2, 4, 6, 7, 7, 8, 8]

也就是说,我们这时候已经知道转置后矩阵的col列的数值分段

for index,value in enumerate(count):
    while len(matrix_dst2)<value:
        matrix_dst2.append([index,"",""])
pd.DataFrame(matrix_dst2, columns=col)
col row value
0 1
1 1
2 2
3 2
4 3
5 3
6 4
7 6

我们需要做的,就是按照这个计数,把节点加入到它属于的那个段。

比如,某个点转置后col=3,则把它放入col=3的那个段中。而我们知道矩阵的row是有序的,所以在col段里顺着往下放就好了

新的索引就应该是 count[matrix_src[i][1]-1]

接下来,每个表格表示每一步操作后的的矩阵内容

for i in range (len(matrix_src)):
    matrix_dst2[count[matrix_src[i][1]-1]][1:] = [matrix_src[i][0],matrix_src[i][2]]
    count[matrix_src[i][1]-1]+=1
    display(pd.DataFrame(matrix_dst2, columns=col))
col row value
0 1
1 1
2 2 1 12
3 2
4 3
5 3
6 4
7 6
col row value
0 1
1 1
2 2 1 12
3 2
4 3 1 9
5 3
6 4
7 6
col row value
0 1 3 -3
1 1
2 2 1 12
3 2
4 3 1 9
5 3
6 4
7 6
col row value
0 1 3 -3
1 1
2 2 1 12
3 2
4 3 1 9
5 3
6 4
7 6 3 14
col row value
0 1 3 -3
1 1
2 2 1 12
3 2
4 3 1 9
5 3 4 24
6 4
7 6 3 14
col row value
0 1 3 -3
1 1
2 2 1 12
3 2 5 18
4 3 1 9
5 3 4 24
6 4
7 6 3 14
col row value
0 1 3 -3
1 1 6 15
2 2 1 12
3 2 5 18
4 3 1 9
5 3 4 24
6 4
7 6 3 14
col row value
0 1 3 -3
1 1 6 15
2 2 1 12
3 2 5 18
4 3 1 9
5 3 4 24
6 4 6 -7
7 6 3 14

c++实现

#include <iostream>
using namespace std;
struct item
{
    int col;
    int row;
    int value;
};

int main()
{
    int i, j;
    int actionCount = 0;
    item matrixSrc[] = {item{1, 2, 12}, item{1, 3, 9}, item{3, 1, -3}, item{3, 6, 14}, item{4, 3, 24}, item{5, 2, 18}, item{6, 1, 15}, item{6, 4, -7}};
    int length = sizeof(matrixSrc) / sizeof(item);
    item matrixDst[length];

    //print origin matrixSrc
    cout << "=========origin matrix\ncol row value" << endl;
    for (i = 0; i < length; i++)
    {
        cout << matrixSrc[i].col << "    " << matrixSrc[i].row << "    " << matrixSrc[i].value << endl;
    }

    // index
    int count[7] = {0, 0, 0, 0, 0, 0, 0}; // 0 is used as buffer
    for (i = 0; i < length; i++)
    {
        for (j = matrixSrc[i].row; j < length; j++)
        {
            count[j] += 1;
        }
    }

    // reverse
    for (i = 0; i < length; i++)
    {

        int newIndex = count[matrixSrc[i].row - 1];
        count[matrixSrc[i].row - 1]++;
        // exchange col and row
        matrixDst[newIndex].row = matrixSrc[i].col;
        matrixDst[newIndex].col = matrixSrc[i].row;
        matrixDst[newIndex].value = matrixSrc[i].value;
    }

    //print origin matrixSrc
    cout << "=========dst matrix\ncol row value" << endl;
    for (i = 0; i < length; i++)
    {
        cout << matrixDst[i].col << "    " << matrixDst[i].row << "    " << matrixDst[i].value << endl;
    }
}

输出:

=========origin matrix
col row value
1    2    12
1    3    9
3    1    -3
3    6    14
4    3    24
5    2    18
6    1    15
6    4    -7
=========dst matrix
col row value
1    3    -3
1    6    15
2    9    12
2    5    18
3    1    9
3    4    24
4    6    -7
6    3    14
本文总字数: 2825