Optimize repeated permutation of a large vector

2 views (last 30 days)
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
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?
Shaked Reich
Shaked Reich on 7 May 2021
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.

Sign in to comment.

Accepted Answer

Bruno Luong
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)
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 Comments
Shaked Reich
Shaked Reich on 8 May 2021
Thank you Bruno!
the sparse method was exactly what I needed.
This got my Thesis simulation x20 times faster!
much appreciated
Bruno Luong
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
Elapsed time is 0.001302 seconds.
tic; t=s(:,p); toc
Elapsed time is 0.000594 seconds.

Sign in to comment.

More Answers (1)

Bruno Luong
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)
ans = 1×8
2 3 4 1 6 7 5 8

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!