c++ - CUDA:在 GPU 上对 vector<vector<int>> 进行排序

Question

我已经为 STL 的 sort 实现了自己的比较器函数，有助于对 std::vector< std::vector<int> > 进行排序在 CPU 上。 用户输入 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 允许您定义自己的比较器，但在 question 中我昨天问过，我了解到无法创建 host_vector < host_vector<int> > .

而且我想将我的 vector vector 转换为单个 vector 对我没有太大帮助，因为我不知道我将如何实现我的比较器类。

我想听听您对这个问题的看法:

1. 我该如何解决这个问题？
2. 有可能用Thrust实现吗？ ？
3. 在 GPU 中执行此操作是否会提高我的整体代码的性能？请注意， vector 的 vector 可能很大，有数百万行，但只有几 (5-10) 列。
4. 是设计我自己的排序更好还是更改现有的排序功能更好？这虽然听起来是个好主意，但在实践中我觉得这需要我付出很多努力才能实现。使用库中的简单比较器和排序函数对我来说是最好的，但是 Thrust 的局限性不允许我这样做。

提前致谢

Answer 1

我看到你正在尝试实现一种字典排序技术(但我已经用单个 1D 巨大的 vector 做到了)，好吧我已经在那里并且我已经实现了一个对 vector 进行排序的函数但实际上它落后了词典排序，无论如何我不确定我是否可以在这里发布代码，所以如果你需要任何帮助，我很乐意提供帮助

PS:查看 thrust 示例代码中 lexicographical_sort.cu 的实现(我也对其进行了调整，但那个也落后了) 为了从 1D vector (包含所有数据)中的两个不同位置进行检查，您可能需要使用比较器功能(顺便说一句，这种技术比 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;
}