2

我已经为 STL 的功能实现了自己的比较器sort，这有助于std::vector< std::vector<int> >在CPU上对 a 进行排序。用户将 a 和字符串变量作为输入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，这个类是用以下两个文件实现的：

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;
  }

  };

我的实现已经过测试并且可以正常工作。我有兴趣做一个类似的 CUDA 实现，它可以利用 GPU 的功能来更快地产生输出。

最初我认为因为我的目标有点令人困惑，也许改变一个已知的在 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（不是在时间方面，而是在数据元素方面）实际上我的新方法涉及使用推力：：不匹配，我正在附加该函数的代码

这个版本的好处是这个函数的运行时间大约是 2ms。有非常大量的数据，例如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 回答