Optimize repeated permutation of a large vector

Question

Shaked Reich 2021-5-6

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/823650-optimize-repeated-permutation-of-a-large-vector

评论： Bruno Luong 2021-5-8

采纳的回答： Bruno Luong

在 MATLAB Online 中打开

Hi all,

s is a vector of length 2^14, whose elements are -1 or +1.

I need to repeatedly permutate s, in the following way:

the elements are diveded into cycles, that I need to cyclically permutate independently.

the first n_1 elements belongs to the first "cycle", the next n_2 elements belongs to the second, and so forth.

I would love Ideas for how to optimize this process.

* Edit for clarification:

Suppose instead that s were 2^3=8 elements. Suppose that vector is:

s = [1 2 3 4 5 6 7 8];

and suppose the cycle lengths are:

n1 = 4; n2 = 3; n3 = 1;

Then the desired output is:

s = [2 3 4 1 6 7 5 8];

What I have done:

I created a block matrix J consisting of cyclic permutation blocks for each cycle, so I have:

s = J*s;

I use single-precision gpuArray for J and s.

because J is a constant matrix consisting only 0's and 1's, I hope there is a way to speed up this multiplication.

Or perhaps there is another way to solve this?

thanks!

2 个评论
显示无隐藏无

the cyclist 2021-5-6

编辑：the cyclist 2021-5-7

在 MATLAB Online 中打开

Just to clarify ...

Suppose instead that s were 2^3 = 8 elements. Suppose that vector is

s = [1 1 0 1 1 0 0 1];

and suppose your cycle lengths are

n1 = 4;
n2 = 3;
n3 = 1;

What is your desired output?

Shaked Reich 2021-5-7

在 MATLAB Online 中打开

Thank you. In this case, The desired output is:

s = [1 0 1 1 0 0 1 1];

To further clarigy, if s was initialy

s = [1 2 3 4 5 6 7 8];

With the same n1,n2,n3, then the desired output would be:

s = [2 3 4 1 6 7 5 8];

Thank you for your question, I will also add it to the post.

请先登录，再进行评论。

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

Answer 1

Bruno Luong 2021-5-7

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/823650-optimize-repeated-permutation-of-a-large-vector#answer_694090

编辑：Bruno Luong 2021-5-7

在 MATLAB Online 中打开

s = [1 2 3 4 5 6 7 8];
i=1:length(s);
n=[4 3 1];
c=cumsum([1 n]);
b=cumsum(ismember(i,c));
p=mod(i+1-c(b),n(b))+c(b)
p = 1×8
     2     3     4     1     6     7     5     8
s(p)
ans = 1×8
     2     3     4     1     6     7     5     8

3 个评论
显示 1更早的评论隐藏 1更早的评论

Shaked Reich 2021-5-8

Thank you Bruno!

the sparse method was exactly what I needed.

This got my Thesis simulation x20 times faster!

much appreciated

Bruno Luong 2021-5-8

在 MATLAB Online 中打开

Just wonder why you use J instead of index permutation:

s=rand(1000,100);
p=randperm(size(s,2));
J=sparse(p,1:length(p),1);
tic; t=s*J; toc
Elapsed time is 0.001302 seconds.
tic; t=s(:,p); toc
Elapsed time is 0.000594 seconds.

请先登录，再进行评论。

Answer 2

Bruno Luong 2021-5-7

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/823650-optimize-repeated-permutation-of-a-large-vector#answer_694115

编辑：Bruno Luong 2021-5-7

在 MATLAB Online 中打开

s = [1 2 3 4 5 6 7 8];
n=[4 3 1];
c=cumsum([0 n]);
p=2:length(s)+1;
p(c(2:end))=c(1:end-1)+1;
s(p)
ans = 1×8
     2     3     4     1     6     7     5     8