patterncppMinor
Generating permutation of indices from seed ID
Viewed 0 times
indicesgeneratingseedpermutationfrom
Problem
In my OpenCL kernel, I have the following logic:
Now, in my testing, I've verified that this logic is correct and applies correct behavior to my variables. However, it is extremely cumbersome to read and maintain, and I'm looking for a way to optimize it such that it's much easier to read and understand. How can I rewrite this logic so that it's much easier to read, and possibly faster to execute?
The intent of this code is to take an input integer in the range [0, 1615141312), and convert it into a permutation of 5 unique indices ranged [0,16). Like I said, this code works, but
size_t id = get_global_id(0);
uchar index0 = (id / 32760) % 16;
uchar index1 = (id / 2184) % 15;
uchar index2 = (id / 156) % 14;
uchar index3 = (id / 12) % 13;
uchar index4 = (id / 1) % 12;
if (index1 >= index0)
++index1;
if(index2 >= index0 ||
index2 >= index1)
++index2;
if(index2 >= index1 && index2 >= index0)
++index2;
if(index3 >= index0 ||
index3 >= index1 ||
index3 >= index2)
++index3;
if(index3 >= index0 && index3 >= index1 ||
index3 >= index1 && index3 >= index2 ||
index3 >= index2 && index3 >= index0)
++index3;
if(index3 >= index0 && index3 >= index1 && index3 >= index2)
++index3;
if(index4 >= index0 ||
index4 >= index1 ||
index4 >= index2 ||
index4 >= index3)
++index4;
if(index4 >= index0 && index4 >= index1 ||
index4 >= index0 && index4 >= index2 ||
index4 >= index0 && index4 >= index3 ||
index4 >= index1 && index4 >= index2 ||
index4 >= index1 && index4 >= index3 ||
index4 >= index2 && index4 >= index3)
++index4;
if(index4 >= index0 && index4 >= index1 && index4 >= index2 ||
index4 >= index1 && index4 >= index2 && index4 >= index3 ||
index4 >= index2 && index4 >= index3 && index4 >= index0 ||
index4 >= index3 && index4 >= index0 && index4 >= index1)
++index4;
if(index4 >= index0 && index4 >= index1 && index4 >= index2 && index4 >= index3)
++index4;Now, in my testing, I've verified that this logic is correct and applies correct behavior to my variables. However, it is extremely cumbersome to read and maintain, and I'm looking for a way to optimize it such that it's much easier to read and understand. How can I rewrite this logic so that it's much easier to read, and possibly faster to execute?
The intent of this code is to take an input integer in the range [0, 1615141312), and convert it into a permutation of 5 unique indices ranged [0,16). Like I said, this code works, but
Solution
Use your words
Let's start with what you're actually accomplishing in all those if statements. It looks like what you're doing is incrementing each index by the number of smaller indices, for each possible such count.
That translates itself naturally to using arrays:
And writing that idea as a loop:
This can be translated into the sort-of-more/sort-of-less readable (YMMV) C++11 version:
Let's start with what you're actually accomplishing in all those if statements. It looks like what you're doing is incrementing each index by the number of smaller indices, for each possible such count.
That translates itself naturally to using arrays:
uchar index[5] = {(id / 32760) % 16,
(id / 2184) % 15,
(id / 156) % 14,
(id / 12) % 13,
(id / 1) % 12};And writing that idea as a loop:
// for each index
for (int i=1; i= index[j]);
}
// and increment if necessary
if (k >= cnt) {
++index[i];
}
}
}This can be translated into the sort-of-more/sort-of-less readable (YMMV) C++11 version:
for (int& i : index) {
for (int cnt=1; cnt = j; }) >= cnt;
}
}Code Snippets
uchar index[5] = {(id / 32760) % 16,
(id / 2184) % 15,
(id / 156) % 14,
(id / 12) % 13,
(id / 1) % 12};// for each index
for (int i=1; i<5; ++i) {
// for each possible count of smaller indices
for (int cnt=1; cnt<=i; ++cnt) {
// count the number of smaller indices
int k=0;
for (int j=0; j<i; ++j) {
k += (index[i] >= index[j]);
}
// and increment if necessary
if (k >= cnt) {
++index[i];
}
}
}for (int& i : index) {
for (int cnt=1; cnt <= std::distance(index, &i); ++cnt) {
i += std::count_if(index, &i, [i](int j){return i >= j; }) >= cnt;
}
}Context
StackExchange Code Review Q#113646, answer score: 3
Revisions (0)
No revisions yet.