Optimize repeated permutation of a large vector
1 view (last 30 days)
Show older comments
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 Comments
the cyclist
on 6 May 2021
Edited: the cyclist
on 7 May 2021
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?
Accepted Answer
Bruno Luong
on 7 May 2021
Edited: Bruno Luong
on 7 May 2021
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)
s(p)
3 Comments
Bruno Luong
on 8 May 2021
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
tic; t=s(:,p); toc
More Answers (1)
Bruno Luong
on 7 May 2021
Edited: Bruno Luong
on 7 May 2021
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)
0 Comments
See Also
Categories
Find more on Loops and Conditional Statements in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!