performance - 加快矩阵输入速度

Question

我的 matlab 计算速度有点问题。我能够在 matlab 中编写代码来运行小矩阵的计算，但它使用嵌套的 for 循环，并且对于我正在使用的大型数据集，matlab 无法完成计算。

注意:我对 Matlab 不太熟悉，所以虽然程序可以运行，但效率极低。

简而言之，我正在尝试创建一个矩阵，其条目描述一组唯一位置之间的关系。作为一个具体的例子，我们从这个矩阵开始:

B = 

5873 4 1

5873 7 1

5873 1 1

2819 8 2

2819 1 2

9771 4 3

9771 2 3

9771 5 3

9771 6 3

5548 7 4

其中第三列是唯一位置标识符，第二列是恰好位于该位置的“段”的编号。请注意，多个段可以落入不同的位置。

我想要创建一个矩阵来描述不同位置之间的关系。具体来说，对于位置 i 和 j，我希望新矩阵的 (i,j) 条目是 i 和 j 共有的段数除以 i 和 j 组合的段总数。

目前我的代码如下所示:

C = zeros(max(B.data(:,3)), max(B.data(:,3)));

for i = 1:max(B.data(:,3))

  for j = 1:max(B.data(:,3))

    vi = B.data(:,3) == i;
    vj = B.data(:,3) == j;
    C(i,j) = numel(intersect(B.data(vi,2), B.data(vj,2))) / numel(union(B.data(vi,2), B.data(vj,2)));
  end

end

但是速度非常非常慢。有人对加快计算速度有什么建议吗？

非常感谢!!

Answer 1

分组和循环方法

1. 位置根据段进行分组(下面代码中的元胞数组 groups)。 accumarray具有自定义函数用于该任务。
2. 大小等于最大位置的方阵C被初始化为零。对于每个组，属于该组的所有位置对在 C 中的条目都会增加 1。
3. 矩阵 C 已标准化。

代码:

groups = accumarray(B.data(:,2), B.data(:,3), [], @(x) {x});  %// step 1
C = zeros(max(B.data(:,3)));                                  %// step 2
for n = 1:numel(groups);
    ind = groups{n};
    C(ind,ind) = C(ind,ind)+1;
end
d = diag(C);                                                  %// step 3
C = C./(bsxfun(@plus,d,d.')-C);

使用 3D 数组的矢量化方法

这种方法非常消耗内存；根据下面 @Divakar 的评论，对于非常大的数据集，它并不比循环方法更快:

1. 它构建一个 3D 逻辑 数组 T，使得 T(m,n,s) 为 1当且仅当位置 m 和 n 共享段 s 时。使用bsxfun可以有效地完成此操作。 .
2. 沿第三个维度对 T 求和可得到与之前方法相同的 C。
3. 矩阵 C 的标准化方式与之前相同。

代码:

T = full(sparse(B.data(:,3), B.data(:,2), 1));               %// step 1
T = bsxfun(@and, permute(T, [1 3 2]), permute(T, [3 1 2]));
C = sum(T, 3);                                               %// step 2
d = diag(C);                                                 %// step 3
C = C./(bsxfun(@plus,d,d.')-C);

---

基准测试

以下基准测试和解释归功于@Divakar:

以下是一些运行时，将基于循环的方法与后一种矢量化方法进行比较 -

***** Parameters: No. of rows in B ~= 10000 and No. of groups = 10 *****
---------------------------------- With loopy approach
Elapsed time is 0.242635 seconds.
---------------------------------- With vectorized approach
Elapsed time is 0.022174 seconds.
 
 
***** Parameters: No. of rows in B ~= 10000 and No. of groups = 100 *****
---------------------------------- With loopy approach
Elapsed time is 0.318268 seconds.
---------------------------------- With vectorized approach
Elapsed time is 0.451242 seconds.
 
 
***** Parameters: No. of rows in B ~= 100000 and No. of groups = 100 *****
---------------------------------- With loopy approach
Elapsed time is 1.173182 seconds.
---------------------------------- With vectorized approach
Elapsed time is 0.464339 seconds.
 
 
***** Parameters: No. of rows in B ~= 100000 and No. of groups = 1000 *****
---------------------------------- With loopy approach
Elapsed time is 10.310780 seconds.
---------------------------------- With vectorized approach
Elapsed time is 54.216923 seconds.

人们可以注意到，对于 B 中相同数量的行，组数量的增加意味着矢量化方法的性能大幅下降。

因此，在为问题案例选择适当方法时可以牢记这一点。