压缩稀疏矩阵

Question

使用压缩稀疏行(CSR、CRS或或格式)压缩稀疏矩阵。

这些都是相同的压缩形式(忽略新耶鲁)。

输入可以是任何2d数据结构(列表等)：例如

[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

输出应该是三个一维数据结构(列表等)，例如表示输出A、IA和JA。

[5, 8, 3, 6]
[0, 0, 2, 3, 4]
[0, 1, 2, 1,]

维基百科描述了这个过程：

• 数组A的长度为NNZ，并按从左到右的自上而下(“行-主”)顺序保存M的所有非零项。
• 数组IA的长度为m + 1。它是由这个递归定义定义的：
• IA[0] = 0 IA[i] = IA[i − 1] + (number of nonzero elements on the (i − 1)-th row in the original matrix)
• 因此，m的第一IA元素将索引存储到M的每一行第一非零元素的A中，最后一个元素IA[m]存储NNZ，即A中的元素数，这也可以被认为是幻影行的第一个元素在矩阵M结束后的A中的索引。原始矩阵的i-th行的值从元素A[IA[i]]读取到A[IA[i + 1] − 1] (两端包含在内)，即从一行开始到下一个.5开始之前的最后一个索引。
• 第三个数组JA包含A的每个元素的M中的列索引，因此它的长度也是NNZ。

如果您的语言不支持实际的数据结构，则输入和输出可能是文本。

测试用例

投入1：

[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

产出1：

[ 5, 8, 3, 6 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1, ]

投入2

[[10 20 0 0 0 0],
 [0 30 0 40 0 0],
 [0 0 50 60 70 0],
 [0 0 0 0 0 80]]

产出2：

[ 10 20 30 40 50 60 70 80 ]
[  0  2  4  7  8 ]
[  0  1  1  3  2  3  4  5 ]

投入3：

[[0 0 0],
 [0 0 0],
 [0 0 0]]

产出3：

[ ]
[ 0 0 0 0 ]
[ ]

投入4：

[[1 1 1],
 [1 1 1],
 [1 1 1]]

产出4：

[ 1 1 1 1 1 1 1 1 1 ]
[ 0 3 6 9 ]
[ 0 1 2 0 1 2 0 1 2 ]

投入5：

[[0 0 0 0],
 [5 -9 0 0],
 [0 0 0.3 0],
 [0 -400 0 0]]

产出5：

[ 5, -9, 0.3, -400 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1, ]

假设输入可能包含任何实数，则不需要考虑数学符号或指数表示(例如，5,000将永远不会输入为5e3)。您不需要处理inf、-inf、NaN或任何其他“伪数字”。您可以输出数字的不同表示形式(5,000可以输出为5e3，如果您选择的话)。

评分

这是一个密码-高尔夫，最少字节获胜。

Answer 1

马蒂尔，19字节

!3#f!Dx0Gg!XsYshDq!

输入使用;作为行分隔符。

在网上试试！或验证所有测试用例：1、2、3.、4.、5。

解释

!     % Implicit input. Transpose
3#f   % 3-output version of find: it takes all nonzero values and pushes
      % their column indices, row indices, and values, as column vectors
!     % Transpose into a row vector
D     % Display (and pop) vector of values
x     % Delete vector of row values
0     % Push 0
G     % Push input
g     % Convert to logical: nonzeros become 1
!     % Transpose
Xs    % Sum of columns. Gives a row vector
Ys    % Cumulative sum
h     % Prepend the 0 that's below on the stack
D     % Display (and pop) that vector
q     % Subtract 1 from the vector of row indices
!     % Transpose into a row vector. Implicitly display

Answer 2

Mathematica，78字节

{a=SparseArray@#;a@"NonzeroValues",a@"RowPointers",Join@@a@"ColumnIndices"-1}&

见这个答案在mathematica.stackexchange.com上。

Answer 3

R，70字节

function(m,M=t(m))list(M[x<-!!M],diffinv(colSums(x)),which(x,T)[,1]-1)

在网上试试！

这是一个古老的，矩阵的挑战，没有得到一个R的答案3年！必须以行为主而不是列主要顺序来完成此操作，成本为8字节(,M=t(m)))。