추력 라이브러리가있는 키의 정밀도가 낮은 정렬 방법

Question

정수 값 집합이 있으며 추력을 사용하여 정렬하려고합니다. 이 정렬에서 일부 상위 비트/하위 비트 만 사용하는 것이 가능합니까? 가능하다면 사용자 정의 비교기를 사용하고 싶지 않습니다. 사용 된 알고리즘을 radix-sort에서 merge-sort로 변경하고 경과 시간을 상당히 늘리기 때문입니다.

모든 숫자가 같은 값을 가질 때 정렬하는 동안 건너 뛴다 고 생각합니다. 가능한 가장 낮은 비트 수를 사용하는 것이 가능하고 충분할 것이라고 생각합니다. (예 : 0 상위 3 개 비트를 8 비트의 문자를 사용하여 설정 5 비트 용)

예 : 하이 또는 로우 단지 4 비트를 사용

sort<4, 0>(myvector.begin(), myvector.end()) 
sort<4, 1>(myvector.begin(), myvector.end()) 

정렬 .. 유사한

뭔가 http://www.moderngpu.com/sort/mgpusort.html

Answer 1

추력의 인터페이스는 현재 정렬 전략 중 하나는 기수 정렬 사실로 알고리즘 구현 세부 사항을 멀리 추상화합니다. 기본 정렬 구현이 버전에서 백엔드로 변경되거나 백엔드로 호출되거나 심지어 호출로 변경 될 수 있기 때문에 사용자가 정렬 할 비트 수를 전달할 수있는 방법이 없습니다.

다행히도 이러한 명시적인 정보는 일반적으로 필요하지 않습니다. 적절한 경우 추력의 현재 정렬 구현은 정렬 키를 검사하고 비트가 0 인 동안 불필요한 계산을 생략합니다.

Answer 2

transformer_iterator를 사용하는 것은 어떻습니까? 다음은 간단한 예제입니다 (첫 번째 비트로 정렬). 목적에 맞게 고유 한 단항 함수를 작성할 수 있습니다.

#include <iostream> 
#include <thrust/device_vector.h> 
#include <thrust/iterator/transform_iterator.h> 
#include <thrust/sort.h> 

using namespace std; 
struct and_func : public thrust::unary_function<int,int> 
{ 
    __host__ __device__ 
     int operator()(int x) 
     { 
      return 8&x; 
     } 
}; 
int main() 
{ 
    thrust::device_vector<int> d_vec(4); 
    d_vec[0] = 10; 
    d_vec[1] = 8; 
    d_vec[2] = 12; 
    d_vec[3] = 1; 
    thrust::sort_by_key(thrust::make_transform_iterator(d_vec.begin(), and_func()), 
       thrust::make_transform_iterator(d_vec.end(), and_func()), 
       d_vec.begin()); 
    for (int i = 0; i < 4; i++) 
     cout<<d_vec[i]<<" "; 
    cout<<"\n"<<endl; 
    return 0; 
}