Optimize repeated permutation of a large vector

2 vues (au cours des 30 derniers jours)
Shaked Reich
Shaked Reich le 6 Mai 2021
Commenté : Bruno Luong le 8 Mai 2021
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 commentaires
the cyclist
the cyclist le 6 Mai 2021
Modifié(e) : the cyclist le 7 Mai 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 le 7 Mai 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.

Connectez-vous pour commenter.

Réponse acceptée

Bruno Luong
Bruno Luong le 7 Mai 2021
Modifié(e) : Bruno Luong le 7 Mai 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 commentaires
Shaked Reich
Shaked Reich le 8 Mai 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 le 8 Mai 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.

Connectez-vous pour commenter.

Plus de réponses (1)

Bruno Luong
Bruno Luong le 7 Mai 2021
Modifié(e) : Bruno Luong le 7 Mai 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

Catégories

En savoir plus sur Loops and Conditional Statements dans Help Center et File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by