2

CPUsortでのソートに役立つ、STL の関数用に独自のコンパレーターを実装std::vector< std::vector<int> >しました。ユーザーは、入力として aと、たとえば のような文字列変数を指定します。この文字列を使用すると、ソートは最初の列で最初に行われ、次に 3 番目の列で、次に 2 番目の列で行われます。例：std::vector< std::vector<int> >021

  1 2 3
  3 2 1
  1 1 1
  1 1 2

文字列が10

出力は次のようになります。

  1 1 1
  1 1 2
  1 2 3
  3 2 1

私の CPU 実装は というクラスを使用しますSorting。このクラスは次の 2 つのファイルで実装されます。

Sorting.h

class Sorting{

   private:

   public:

Sorting();
~Sorting();
std::vector<std::vector<int>> applySort(std::vector<std::vector<int>>
    data,const std::string& attr);

 };

Sorting.cpp

 Sorting::Sorting(){}

 Sorting::~Sorting(){}


 std::vector<std::vector<int>> Sorting::applySort(
      std::vector<std::vector<int>> data, const std::string& attr){

         std::sort(data.begin(), data.begin()+data.size(), Comparator(attr));

         return data;
  }

Comparator.h

   class Comparator{

   private:
     std::string attr;

   public:
     Comparator(const std::string& attr) { this->attr = attr; }

     bool operator()(const std::vector<int>& first, const std::vector<int>&
          second){

    size_t i;
    for(i=0;i<attr.size();i++){
        if(first[attr.at(i) - '0'] < second[attr.at(i) - '0']) return true;
        else if(first[attr.at(i) - '0'] > second[attr.at(i)-'0'])          
             return  false;
    }
    return false;
  }

  };

私の実装はテスト済みで、正しく動作します。出力をより高速に生成するために、GPU の機能を利用する同様の CUDA 実装を行うことに興味があります。

最初は、私の目標が少しわかりにくいので、GPU での並べ替えの既に知られている実装を変更することで、私の仕事がうまくいくかもしれないと考えました。ただし、ここで説明されているような多くの実装を検索し始めました: http://blogs.nvidia.com/2012/09/how-tesla-k20-speeds-up-quicksort-a-familiar-comp-sci-code/とそれ達成するのは難しいことだと思い知らされました。

これが最善の策かどうかはわかりません。ライブラリの検索を開始し、 を見つけましThrustた。ただし、Thrust では独自のコンパレータを定義できますが、昨日尋ねた質問host_vector < host_vector<int> >で、 .

そして、ベクトルのベクトルを単一のベクトルに変換しても、コンパレータ クラスをどのように実装する必要があるのか​​ わからないため、あまり役に立たないと思います。

この問題についてあなたの意見を聞きたいです：

  1. この問題にどのようにアプローチすればよいですか？
  2. でそれを達成することは可能Thrustですか?
  3. GPU で実行すると、コード全体のパフォーマンスが大幅に向上しますか? ベクトルのベクトルは、何百万行にもなる巨大なものになる可能性がありますが、数列 (5 ～ 10) しかないことに注意してください。
  4. 独自の並べ替えを設計するか、既に利用可能な並べ替え機能を変更した方がよいでしょうか? これは良いアイデアのように聞こえますが、実際には達成するのに多くの努力が必要になると感じています. ライブラリの単純なコンパレータとソート関数を使用するのが最善ですが、制限によりThrustそうすることができません。

前もって感謝します

4

2 に答える 2

1

私はあなたが辞書式ソート技術を実装しようとしているのを見ています（しかし、私は単一の1Dの巨大なベクトルでそれをやったことがあります）、私はそこにいて、ベクトルをソートする関数を実装しましたが、実際には辞書式ソートより遅れています、とにかく、ここにコードを投稿できるかどうかわからないので、何か助けが必要な場合は喜んでお手伝いします

PS: スラスト サンプル コードで lexicographical_sort.cu の実装を調べてください (私も微調整しましたが、これも遅れています)。データ) は下にリストされています (ちなみに、この手法は CPU よりもはるかに遅いです)。

struct arbitrary_functor
{
    template <typename Tuple>   __host__ __device__
        void operator()(Tuple t)
        {
            if(thrust::get<0>(t)>thrust::get<1>(t))
                thrust::get<2>(t) = 1;
            else
                thrust::get<2>(t) = 0;
        }
};

int checkLexo_1vec(const thrust::device_vector<char> & A, int bv1, int bv2, int N){
    int i;

    thrust::device_vector<char> temp(N);
    thrust::device_vector<char> sum(N);

    thrust::for_each(thrust::make_zip_iterator(
                        thrust::make_tuple(A.begin()+bv2, A.begin()+bv1,temp.begin())),
                    thrust::make_zip_iterator(
                        thrust::make_tuple(A.end()+(bv2+N),A.end()+(bv1+N), temp.end())),
                    arbitrary_functor());


    thrust::inclusive_scan(temp.begin(),temp.end(),sum.begin());

    int a = thrust::lower_bound(sum.begin(),sum.end(),1) - sum.begin();

    thrust::for_each(thrust::make_zip_iterator(
                        thrust::make_tuple(A.begin()+bv1, A.begin()+bv2, temp.begin())),
                    thrust::make_zip_iterator(
                        thrust::make_tuple(A.end()+(bv1+N), A.end()+(bv2+N),temp.end())),
                    arbitrary_functor());

    thrust::inclusive_scan(temp.begin(),temp.end(),sum.begin());

    int b = thrust::lower_bound(sum.begin(),sum.end(),1) - sum.begin();

    if(a<=b)
        return 1;
    else
        return 0;
}
于 2013-04-08T19:26:30.913 に答える
0

最終的にCPUを打ち負かすことができる合理的な方法を見つけました（時間ではなくデータ要素の観点から）実際に私の新しい方法には、推力::ミスマッチの使用が含まれており、関数のコードを添付しています

このバージョンの良いところは、この関数の実行時間が約 2 ミリ秒であることです。などの非常に大量のデータを使用してN = 1000000 to N = 1000、とにかく関数コードを投稿しています。全体の実行時間を短縮できる他の改善を見つけたユーザーがいる場合はお知らせください

template<typename Ivec>    
int lexoMM(Ivec vec, int bv1, int bv2, int N){

  typedef thrust::device_vector<int>::iterator Iterator;
  thrust::pair<Iterator,Iterator> result;

  result = thrust::mismatch(vec.begin()+bv1, vec.begin()+(bv1+N-1), vec.begin()+bv2);

if(result.first == vec.end()){
      //cout<<"Both are equal (right order)"<<endl;
      return 1;
  }
else if(result.first>result.second){
    //cout<<"Wrong order"<<endl;
    //cout<<*result.first<<","<<*result.second;
    return 0;
}
else{
    //cout<<"Right order"<<endl;
    //cout<<*result.first<<","<<*result.second;
    return 1;
    }

}

PS: これと同じことの独自のバージョンを実装するために本当に時間を無駄にしたような気がしますが、thrust素晴らしいです :)

于 2013-04-09T18:39:14.377 に答える