1

一連の整数値があり、Thrust を使用してそれらを並べ替えたいと考えています。このソートで一部の上位ビット/下位ビットのみを使用する可能性はありますか? 可能であれば、ユーザー定義のコンパレータを使用したくありません。使用されるアルゴリズムが基数ソートからマージソートに変更され、経過時間が大幅に増加するためです。

すべての数値がビットで同じ値を持つ場合、ソート中にビットがスキップされると思うので、可能な限り最小のビット数を使用して、それで十分であることを願っています。(つまり、8 ビットの char を使用し、上位 3 ビットを 0 に設定する 5 ビットの場合)

例：

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

上位または下位の 4 ビットのみを使用して並べ替えます。

http://www.moderngpu.com/sort/mgpusort.htmlに似たもの

4

2 に答える 2

1

Thrust のインターフェースは、現在のソート戦略の 1 つが基数ソートであるという事実など、アルゴリズム実装の詳細を抽象化します。基礎となる並べ替えの実装がバージョンごと、バックエンドごと、または呼び出しごとに変更される可能性があるため、ユーザーが並べ替えるビット数を伝える方法はありません。

幸いなことに、このような明示的な情報は通常必要ありません。必要に応じて、Thrust の現在の並べ替えの実装は、並べ替えキーを検査し、ゼロ化されたビット内の余分な計算を省略します。

于 2012-08-26T22:25:47.713 に答える
0

transform_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;
}
于 2012-06-20T19:31:33.683 に答える