Jump to content

  • Log In with Google      Sign In   
  • Create Account

Algorithm for certain permutaion of array elements (parallel sorting by regular sampling)


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 Misery   Members   -  Reputation: 317

Like
0Likes
Like

Posted 11 July 2013 - 01:07 AM

I am implementing a parallel sorting by regular sampling algorithm which is described here. I am stuck in a point at which I need to migrate sorted sublists to proper places of the sorted array. The problem can be stated in that way: There is one global array. The array has been divided into p subarrays.Each of those subarrays was sorted. p-1 global pivot elements were determined and each sub-array was divided into p sub-sub arrays (yellow, red, green). Now I need to move those sub-sub-arrays so that sub-sub-arrays with local index i are in the thread i (so they are ordered in such manner at which colors are neighbouring and the order from left to right remains).

Actually serial algorithm will do, but I just have no clever idea how to obtain a proper permutation. The following figure shows a case for p=3 threads. Yellow color denotes a sub-sub-array 0, red - 1, green - 2.

 

ProblemImg.png

 

The sub-sub arrays may have different sizes.


Edited by Misery, 11 July 2013 - 01:07 AM.


Sponsor:

#2 Norman Barrows   Crossbones+   -  Reputation: 2158

Like
1Likes
Like

Posted 11 July 2013 - 12:13 PM

perhaps something like:

 

for CurrentSubSubArray = 0 to 2

   for CurrentThread = 0 to 2

      for CurrentGlobalIndex = FirstIndexInThread to LastIndexInThread

          if Element[CurrentGlobalIndex].SubSubArray == CurrentSubSubArray

               CopyToNewArray()


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#3 Álvaro   Crossbones+   -  Reputation: 13372

Like
1Likes
Like

Posted 11 July 2013 - 12:28 PM

This seems straight forward enough:

 

#include <iostream>

int color[27] = {0, 0, 0, 1, 1, 2, 2, 2, 2, 0, 0, 1, 1, 1, 1, 1, 2, 2, 0, 1, 1, 2, 2, 2, 2, 2, 2};

int main() {
  int counters[3] = {0};
  for (int i=0; i<27; ++i)
    counters[color[i]]++;
 
  int indices[3];
  int accumulator = 0;
  for (int i=0; i<3; ++i) {
    indices[i] = accumulator;
    accumulator += counters[i];
  }
 
  int permutation[27];
  for (int i=0; i<27; ++i)
    permutation[indices[color[i]]++] = i;
 
  for (int i=0; i<27; ++i)
    std::cout << permutation[i] << ' ';
  std::cout << '\n';
}


#4 Misery   Members   -  Reputation: 317

Like
0Likes
Like

Posted 13 July 2013 - 05:32 AM

Well, the problem is that processed amounts of data are huge so I need not to copy whole data. If i'll think of something clever i'll post it here.



#5 Álvaro   Crossbones+   -  Reputation: 13372

Like
0Likes
Like

Posted 13 July 2013 - 11:49 AM

My code doesn't copy any data... Perhaps you can describe your requirements better, but my code does just about the minimal amount of work required, given what I understood you are trying to do.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS