是否可以在 CUDA 中使用 CUDPP 进行分段排序?通过分段排序,我的意思是对受以下标志保护的数组元素进行排序。
A[10,9,8,7,6,5,4,3,2,1]
Flag array[1,0,1,0,0,1,0,0,0,0]
对 A 中连续 1 之间的元素进行排序。
预期输出
[9,10,6,7,8,1,2,3,4,5]
您可以在单个排序过程中执行此操作:想法是调整数组中的元素,以便排序仅在“段”内重新定位元素
对于您的示例:
A[10,9,8,7,6,5,4,3,2,1]
flag[0,0,1,0,0,1,0,0,0,0]
(我删除了第一个 1,因为它不需要)
首先扫描标志数组:
scanned_flag[0,0,1,1,1,2,2,2,2,2]
那么你有很多选项取决于数字类型,例如对于无符号整数,你可以设置最高位来区分“段”。最简单的方法就是将最大元素乘以scanned_flags:
A + scanned_flag*10 = [10,9,18,17,16,25,24,23,22,21]
剩下的很简单:对数组进行排序并反转转换。这是两个版本:使用 Arrayfire 和推力。检查您更喜欢哪个。
阵列火:
void af_test() {
int A[] = {10,9,8,7,6,5,4,3,2,1};
int S[] = {0, 0,1,0,0,1,0,0,0,0};
int n = sizeof(A) / sizeof(int);
af::array devA(n, A, af::afHost);
af::array devS(n, S, af::afHost);
// obtain the max element
int maxi = af::max< int >(devS);
// scan the keys
// keys = 0,0,1,1,1,2,2,2,2,2
af::array keys = af::accum(devS);
// compute: A = A + keys * maxi
// A = 10,9,18,17,16,25,24,23,22,21
devA = devA + keys * maxi;
// sort the array
// A = 9,10,16,17,18,21,22,23,24,25
devA = af::sort(devA);
// compute: A = A - keys * maxi
// A = 9,10,6,7,8,1,2,3,4,5
devA = devA - keys * maxi;
// print the results
print(devA);
}
推力:
template<typename T>
struct add_mul : public binary_function<T,T,T>
{
add_mul(const T& _factor) : factor(_factor) {
}
__host__ __device__ T operator()(const T& a, const T& b) const
{
return (a + b * factor);
}
const T factor;
};
void thrust_test()
{
int A[] = {10,9,8,7,6,5,4,3,2,1};
int S[] = {0, 0,1,0,0,1,0,0,0,0};
int n = sizeof(A) / sizeof(int);
thrust::host_vector< int > hA(A, A + n), hS(S, S + n);
thrust::device_vector< int > devA = hA, devS = hS, keys(n);
// scan the keys
thrust::inclusive_scan(devS.begin(), devS.end(), keys.begin());
// obtain the maximal element
int maxi = *(thrust::max_element(devA.begin(), devA.end()));
// compute: A = A + keys * maxi
thrust::transform(devA.begin(), devA.end(), keys.begin(), devA.begin(), add_mul< int >(maxi));
// sort the array
thrust::sort(devA.begin(), devA.end());
// compute: A = A - keys * maxi
thrust::transform(devA.begin(), devA.end(), keys.begin(), devA.begin(), add_mul< int >(-maxi));
// copy back to the host
hA = devA;
std::cout << "\nSorted array\n";
thrust::copy(hA.begin(), hA.end(), std::ostream_iterator<int>(std::cout, "\n"));
}