MATLAB 计算 9 元素向量的 Spearman 秩相关性太慢
MATLAB is too slow calculation of Spearman's rank correlation for 9-element vectors
我需要计算具有不同长度的向量对(例如 5 元素向量到 20 元素向量)的 Spearman 秩相关性(使用 corr
函数)。每个长度的对数通常在 300 对以上。我用 waitbar
跟踪进度。我注意到,对于 9 元素的向量对,它需要非常长的时间,而对于其他长度(更大和更小),它需要非常短的时间。由于公式完全相同,问题一定出在 MATLAB 函数 corr
.
我编写了以下代码来验证问题出在 corr
函数而不是我除 'corr' 之外的其他计算,其中所有计算(包括 'corr')发生在 2 或 3 个 'for' 循环中。代码重复计时50次以避免意外结果。
结果是 bar graph,证实 MATLAB 计算 9 元素向量的 Spearman 秩相关需要很长时间。由于我的计算量不大,所以这个问题不会导致无休止的等待,只是增加了整个过程的总耗时。谁能告诉我是什么原因导致了这个问题以及如何避免它?
Times1 = zeros(20,50);
for i = 5:20
for j = 1:50
tic
A = rand(i,2);
[r,p] = corr(A(:,1),A(:,2),'type','Spearman');
Times1(i,j) = toc;
end
end
Times2 = mean(Times1,2);
bar(Times2);
xticks(1:25);
xlabel('number of elements in vectors');
ylabel('average time');
经过一些调查,我想我找到了这个非常有趣的问题的根源。我的测试已经使用内置的 Matlab profiler 对每个外部迭代进行了分析,如下所示:
res = cell(20,1);
for i = 5:20
profile clear;
profile on -history;
for j = 1:50
uni = rand(i,2);
corr(uni(:,1),uni(:,2),'type','Spearman');
end
profile off;
p = profile('info');
res{i} = p.FunctionTable;
end
生成的输出如下所示:
我注意到的第一件事是,行数小于或等于 9
的矩阵的 Spearman 相关性的计算方式与行数 10
或更多行的矩阵的计算方式不同.对于前者,corr
函数内部调用的函数是:
Function Number of Calls
----------------------- -----------------
'factorial' 100
'tiedrank>tr' 100
'tiedrank' 100
'corr>pvalSpearman' 50
'corr>rcumsum' 50
'perms>permsr' 50
'perms' 50
'corr>spearmanExactSub' 50
'corr>corrPearson' 50
'corr>corrSpearman' 50
'corr' 50
'parseArgs' 50
'parseArgs' 50
对于后者,corr
函数内部调用的函数是:
Function Number of Calls
----------------------- -----------------
'tiedrank>tr' 100
'tiedrank' 100
'corr>AS89' 50
'corr>pvalSpearman' 50
'corr>corrPearson' 50
'corr>corrSpearman' 50
'corr' 50
'parseArgs' 50
'parseArgs' 50
由于 10
行或更多行的矩阵的 Spearman 相关性的计算似乎 运行 顺利且快速并且没有显示任何性能瓶颈的证据,我决定避免浪费时间调查这个事实,我把重点放在了主要问题上:小矩阵。
我试图了解具有 5
行的矩阵和具有 9
行的矩阵(表现最差的矩阵)的整个过程执行时间之间的差异。这是我使用的代码:
res5 = res{5,1};
res5_tt = [res5.TotalTime];
res5_tt_perc = ((res5_tt ./ sum(res5_tt)) .* 100).';
res9_tt = [res{9,1}.TotalTime];
res9_tt_perc = ((res9_tt ./ sum(res9_tt)) .* 100).';
res_diff = res9_tt_perc - res5_tt_perc;
[~,res_diff_sort] = sort(res_diff,'desc');
tab = [cellstr(char(res5.FunctionName)) num2cell([res5_tt_perc res9_tt_perc res_diff])];
tab = tab(res_diff_sort,:);
tab = cell2table(tab,'VariableNames',{'Function' 'TT_M5' 'TT_M9' 'DIFF'});
结果如下:
Function TT_M5 TT_M9 DIFF
_______________________ _________________ __________________ __________________
'corr>spearmanExactSub' 7.14799963478685 16.2879721171023 9.1399724823154
'corr>pvalSpearman' 7.98185309750143 16.3043118970503 8.32245879954885
'perms>permsr' 3.47311716905926 8.73599255035966 5.26287538130039
'perms' 4.58132952553723 8.77488502392486 4.19355549838763
'corr>corrSpearman' 15.629476293326 16.440893059217 0.811416765890929
'corr>rcumsum' 0.510550019981949 0.0152486312660671 -0.495301388715882
'factorial' 0.669357868472376 0.0163923929871943 -0.652965475485182
'parseArgs' 1.54242684137027 0.0309456171268161 -1.51148122424345
'tiedrank>tr' 2.37642998160463 0.041010720272735 -2.3354192613319
'parseArgs' 2.4288171135289 0.0486075856244615 -2.38020952790444
'corr>corrPearson' 2.49766877262937 0.0484657591710417 -2.44920301345833
'tiedrank' 3.16762535118088 0.0543584195582888 -3.11326693162259
'corr' 21.8214856092549 16.5664346332513 -5.25505097600355
发现瓶颈后,我开始分析内部代码(open corr
),终于找到了问题的原因。在spearmanExactSub
中,正在执行这部分代码(其中n
是矩阵的行数):
n = arg1;
nfact = factorial(n);
Dperm = sum((repmat(1:n,nfact,1) - perms(1:n)).^2, 2);
正在计算值范围从 1
到 n
的向量的排列。这就是增加函数的计算复杂性(显然还有计算时间)的原因。其他操作,例如 1:n
的 factorial(n)
上的后续 repmat
以及低于该点的操作,会导致情况恶化。现在,长话短说...
factorial(5) = 120
factorial(6) = 720
factorial(7) = 5040
factorial(8) = 40320
factorial(9) = 362880
您能看出为什么在 5
和 9
之间,您的条形图显示 "exponentially" 计算时间增加的原因吗?
附带说明一下,您无法解决此问题,除非您找到另一个不存在相同瓶颈的 Spearman 相关性实现,或者您自己实现。
我需要计算具有不同长度的向量对(例如 5 元素向量到 20 元素向量)的 Spearman 秩相关性(使用 corr
函数)。每个长度的对数通常在 300 对以上。我用 waitbar
跟踪进度。我注意到,对于 9 元素的向量对,它需要非常长的时间,而对于其他长度(更大和更小),它需要非常短的时间。由于公式完全相同,问题一定出在 MATLAB 函数 corr
.
我编写了以下代码来验证问题出在 corr
函数而不是我除 'corr' 之外的其他计算,其中所有计算(包括 'corr')发生在 2 或 3 个 'for' 循环中。代码重复计时50次以避免意外结果。
结果是 bar graph,证实 MATLAB 计算 9 元素向量的 Spearman 秩相关需要很长时间。由于我的计算量不大,所以这个问题不会导致无休止的等待,只是增加了整个过程的总耗时。谁能告诉我是什么原因导致了这个问题以及如何避免它?
Times1 = zeros(20,50);
for i = 5:20
for j = 1:50
tic
A = rand(i,2);
[r,p] = corr(A(:,1),A(:,2),'type','Spearman');
Times1(i,j) = toc;
end
end
Times2 = mean(Times1,2);
bar(Times2);
xticks(1:25);
xlabel('number of elements in vectors');
ylabel('average time');
经过一些调查,我想我找到了这个非常有趣的问题的根源。我的测试已经使用内置的 Matlab profiler 对每个外部迭代进行了分析,如下所示:
res = cell(20,1);
for i = 5:20
profile clear;
profile on -history;
for j = 1:50
uni = rand(i,2);
corr(uni(:,1),uni(:,2),'type','Spearman');
end
profile off;
p = profile('info');
res{i} = p.FunctionTable;
end
生成的输出如下所示:
我注意到的第一件事是,行数小于或等于 9
的矩阵的 Spearman 相关性的计算方式与行数 10
或更多行的矩阵的计算方式不同.对于前者,corr
函数内部调用的函数是:
Function Number of Calls
----------------------- -----------------
'factorial' 100
'tiedrank>tr' 100
'tiedrank' 100
'corr>pvalSpearman' 50
'corr>rcumsum' 50
'perms>permsr' 50
'perms' 50
'corr>spearmanExactSub' 50
'corr>corrPearson' 50
'corr>corrSpearman' 50
'corr' 50
'parseArgs' 50
'parseArgs' 50
对于后者,corr
函数内部调用的函数是:
Function Number of Calls
----------------------- -----------------
'tiedrank>tr' 100
'tiedrank' 100
'corr>AS89' 50
'corr>pvalSpearman' 50
'corr>corrPearson' 50
'corr>corrSpearman' 50
'corr' 50
'parseArgs' 50
'parseArgs' 50
由于 10
行或更多行的矩阵的 Spearman 相关性的计算似乎 运行 顺利且快速并且没有显示任何性能瓶颈的证据,我决定避免浪费时间调查这个事实,我把重点放在了主要问题上:小矩阵。
我试图了解具有 5
行的矩阵和具有 9
行的矩阵(表现最差的矩阵)的整个过程执行时间之间的差异。这是我使用的代码:
res5 = res{5,1};
res5_tt = [res5.TotalTime];
res5_tt_perc = ((res5_tt ./ sum(res5_tt)) .* 100).';
res9_tt = [res{9,1}.TotalTime];
res9_tt_perc = ((res9_tt ./ sum(res9_tt)) .* 100).';
res_diff = res9_tt_perc - res5_tt_perc;
[~,res_diff_sort] = sort(res_diff,'desc');
tab = [cellstr(char(res5.FunctionName)) num2cell([res5_tt_perc res9_tt_perc res_diff])];
tab = tab(res_diff_sort,:);
tab = cell2table(tab,'VariableNames',{'Function' 'TT_M5' 'TT_M9' 'DIFF'});
结果如下:
Function TT_M5 TT_M9 DIFF
_______________________ _________________ __________________ __________________
'corr>spearmanExactSub' 7.14799963478685 16.2879721171023 9.1399724823154
'corr>pvalSpearman' 7.98185309750143 16.3043118970503 8.32245879954885
'perms>permsr' 3.47311716905926 8.73599255035966 5.26287538130039
'perms' 4.58132952553723 8.77488502392486 4.19355549838763
'corr>corrSpearman' 15.629476293326 16.440893059217 0.811416765890929
'corr>rcumsum' 0.510550019981949 0.0152486312660671 -0.495301388715882
'factorial' 0.669357868472376 0.0163923929871943 -0.652965475485182
'parseArgs' 1.54242684137027 0.0309456171268161 -1.51148122424345
'tiedrank>tr' 2.37642998160463 0.041010720272735 -2.3354192613319
'parseArgs' 2.4288171135289 0.0486075856244615 -2.38020952790444
'corr>corrPearson' 2.49766877262937 0.0484657591710417 -2.44920301345833
'tiedrank' 3.16762535118088 0.0543584195582888 -3.11326693162259
'corr' 21.8214856092549 16.5664346332513 -5.25505097600355
发现瓶颈后,我开始分析内部代码(open corr
),终于找到了问题的原因。在spearmanExactSub
中,正在执行这部分代码(其中n
是矩阵的行数):
n = arg1;
nfact = factorial(n);
Dperm = sum((repmat(1:n,nfact,1) - perms(1:n)).^2, 2);
正在计算值范围从 1
到 n
的向量的排列。这就是增加函数的计算复杂性(显然还有计算时间)的原因。其他操作,例如 1:n
的 factorial(n)
上的后续 repmat
以及低于该点的操作,会导致情况恶化。现在,长话短说...
factorial(5) = 120
factorial(6) = 720
factorial(7) = 5040
factorial(8) = 40320
factorial(9) = 362880
您能看出为什么在 5
和 9
之间,您的条形图显示 "exponentially" 计算时间增加的原因吗?
附带说明一下,您无法解决此问题,除非您找到另一个不存在相同瓶颈的 Spearman 相关性实现,或者您自己实现。