将稀疏矩阵高效转换为单元数组

Question

我有一个如下形式的稀疏矩阵

我们以一个5x10矩阵为例

      1  2  3  4  5  6  7  8  9  10
 1    1  1  0  0  0  0  0  0  0   0
 2    0  1  0  0  0  0  0  0  0   0
 3    .............................
 4    .............................
 5    .............................

从这个稀疏矩阵中，我想创建一个形式为C的单元数组。

C{1} 1
C{2} = [1,2]
...........
...........
...........

我的稀疏矩阵是高维的，例如40000乘以790000。在Matlab中如何高效地处理它？我可以使用循环来处理，但这样效率不高。你有什么建议吗？

- user34790

Answer 1

使用 find 函数获取索引，再使用 accumarray 函数按列进行分组：

[ii, jj] = find(A);
C = accumarray(jj, ii, [], @(v) {v.'});

基准测试

%// Random sparse matrix. Code adapted from @teng's answer
sz = [4e4 79e4];
nz = 1e5; %// number of nonzeros
A = sparse(randi(sz(1),[nz 1]),randi(sz(2),[nz 1]),1,sz(1),sz(2));

tic;    
[ii, jj] = find(A);
C = accumarray(jj, ii, [], @(v) {v.'});
toc

结果：

• For nz = 1e4:

  Elapsed time is 0.099657 seconds.
  

• For nz = 1e5:

  Elapsed time is 0.756234 seconds.
  

• For nz = 1e6:

  Elapsed time is 5.431427 seconds.
  

- Luis Mendo

---

你的两行代码不仅使用更少的内存，而且比我的三行代码快大约15倍。 :D 很棒的解决方案！ - pangyuteng

Answer 2

让我开始派对吧... 我们从基础知识开始：

 tic;
 sz = [ 400 7900]; % hehe...
 aMat = sparse(randi(sz(1),[1000 1]),randi(sz(2),[1000 1]),1,sz(1),sz(2));
 aCell = mat2cell(aMat,ones([sz(1) 1]));
 preC = cellfun(@(x) x(x~=0), aCell,'UniformOutput',false);
 C = cellfun(@(x) find(x), preC,'UniformOutput',false);
 toc

- pangyuteng