What is the complexity of the permute() fonction for multiway arrays?

3 次查看（过去 30 天）
Jeremy Cohen
Jeremy Cohen 2018-10-26
评论： Bruno Luong 2018-10-26
Some functions to manipulate arrays, such as the "reshape" function, seem to run in O(1). On the other hand, the "permute" function runs quite slowly for larger arrays, especially multiway arrays.
Is it possible to bound the numerical complexity of the "permute" function? I guess my question relates to how "permute" is internally implemented.
  7 个评论
显示 5更早的评论
Jeremy Cohen
Jeremy Cohen 2018-10-26
Actually I can mention that, when computing tensor decompositions such as PARAFAC (a data-mining model), it is standard to reshape and permute arrays several times. Also, Sparse tensors are really a common thing ^^
Bruno Luong
Bruno Luong 2018-10-26
I just check with debug format, RESHAPE sparse will result a new Pr, even if nothing is explicit shared.
>> S = sparse(rand(1,2))
S =
Structure address = d92c4250
m = 2
n = 1
pr = 21159d80
(1,1) 0.3437
(1,2) 0.8925
>> S = reshape(S,[2 1])
S =
Structure address = d92c7f90
m = 2
n = 1
pr = 20a03700
(1,1) 0.3437
(2,1) 0.8925
Whereas for FULL matrix, Pr address will be unchanged if I do the same reshaping.
I believe for SPARSE, JIT accelerator could optimized further so that
  • Pr data is fixed as well as data behind it,
  • Ir pointer could be unchanged but new data is inplace updated, but
  • Jc pointer must be reallocated and updated.
Obviously TMW fill it's not worth effort to optimize that way for sparse matrix.
Close this out of topic. Sorry.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Bruno Luong
Bruno Luong 2018-10-26
The complexity of PERMUTE(A,P) is O(numel(A)) regardless p, but with the constant O depends on p, for example when p=1,2...,d, it will be significantly faster due to linear memory access, but still O(n).
I have no idea how it's implemented internally. There can be so many variants for such problem.
That's why if you can trade permute by reshape, don't hesitate.
Timing and test code
function t = timepermute
p = perms(1:3);
n3 = 10:10:100;
t = zeros(size(p,1),length(n3));
for j = 1:length(n3)
A=rand(1000,1000,n3(j));
for i=1:size(p,1)
pi = p(i,:);
tic
B = permute(A,pi);
t(i,j) = toc;
end
end
s = arrayfun(@(i) sprintf('p = %s',mat2str(p(i,:))), 1:size(p,1),'unif',0);
close all
plot(n3*size(A,1)*size(A,2),t);
xlabel('n');
ylabel('permute time [s]');
legend(s,'location','northwest')
grid on

更多回答（2 个）

Steven Lord
Steven Lord 2018-10-26
Calling reshape on an array doesn't change the order of the elements, just the size/shape of the array, so there's no need to move the elements around in memory.
Calling permute needs to change the order of the elements (unless the permutation vector starts with 1:ndims(arrayBeingPermuted)) so there are memory manipulation operations involved.
>> r = reshape(1:10000, [100 100]);
>> r2 = reshape(r, [50 200]);
>> r(4836), r2(4836)
ans =
4836
ans =
4836
>> p2 = permute(r, [2 1]);
>> r(4836), p2(4836)
ans =
4836
ans =
3549
If you're trying to compare the performance of those two operations, you're comparing apples and oranges. Actually, a better analogy would be asking your friends to call you by a different name (low effort, reshape) versus filing the necessary paperwork with the government to change your name legally on your driver's license, passport, and other official documents (higher effort, permute.)
  2 个评论
Jeremy Cohen
Jeremy Cohen 2018-10-26
I completely agree with what you just explained, which is why I mentionned reshape is O(1). I'm just curious how the "permute" operator scales with the dimensions of the arrays.
Walter Roberson
Walter Roberson 2018-10-26
permute() touches each input entry exactly once. It is not implemented as a multiplication by a permutation matrix.

请先登录，再进行评论。

Walter Roberson
Walter Roberson 2018-10-26
permute is probably O(n) but is probably badly affected by cache line effects.
  2 个评论
Jeremy Cohen
Jeremy Cohen 2018-10-26
I'm sorry but this is not quite precise. Given a multidimensional array of dimensions n_1, n_2, ..., n_d, do you mean the complexity is probably around O(\prod_i {n_i}) ?

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Matrix Indexing 的更多信息

标签

产品


版本

R2018a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by