使用推力在组中查找元素

Question

我有两个用于键和值的 int 向量，它们的大小约为 500K。

键向量已经排序。大约有10K组。

取值为非负（有用）或-2（无用），每组中应有1个或0个非负值，其余为-2。

key:   0  0  0  0 1  2  2  3  3  3  3 
value:-2 -2  1 -2 3 -2 -2 -2 -2 -2  0

第0组第三对[0 1]有用。对于第 1 组，我们得到对 [1 3]。第 2 组的值都是 -2，所以我们什么也得不到。对于第 3 组，结果是 [3 0].

所以，问题是我如何通过 thrust 或 cuda 做到这一点？

这里有两个想法。

第一个: 通过直方图算法得到每组的数量。因此可以计算每个组的障碍。对每组进行操作thrust::find_if，得到有用的元素。

第二个: 使用 thrust::transform 为每个值加 2 现在所有值都是非负数，零表示无用。使用 thrust::reduce_by_key 得到每个组的减少量，然后为每个输出值减去 2。

我认为一定有其他方法可以实现比上述两种方法更好的性能。

方法的性能：

我测试了上面的Second方法和@Robert Crovella给出的方法，即。 reduce_by_key 和 remove_if 方法。向量的大小为 2691028，向量由 100001 组组成。这是他们的平均时间：

reduce_by_key: 1204ms
remove_if: 192ms

从上面的结果，我们可以看出remove_if方法要快得多。而且 "remove_if" 方法易于实现并且消耗更少的 gpu 内存。

简而言之，@Robert Crovella 的方法非常好。

Answer 1

我将对压缩值使用 thrust::zip_iterator 到 zip the key and values pairs together, and then I would do a thrust::remove_if 操作，这将需要一个函子定义，该定义将指示删除值为负的每一对（或您希望的任何测试.)

这是一个有效的例子：

$ cat t1009.cu
#include <thrust/remove.h>
#include <thrust/device_vector.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/copy.h>

struct remove_func
{
  template <typename T>
  __host__ __device__
  bool operator()(T &t){
    return (thrust::get<1>(t) < 0); // could change to other kinds of tests
    }
};

int main(){

  int keys[] = {0,0,0,0,1,2,2,3,3,3,3};
  int vals[] = {-2,-2,1,-2,3,-2,-2,-2,-2,-2,0};
  size_t dsize = sizeof(keys)/sizeof(int);

  thrust::device_vector<int>dkeys(keys, keys+dsize);
  thrust::device_vector<int>dvals(vals, vals+dsize);
  auto zr = thrust::make_zip_iterator(thrust::make_tuple(dkeys.begin(), dvals.begin()));

  size_t rsize = thrust::remove_if(zr, zr+dsize, remove_func()) - zr;

  thrust::copy_n(dkeys.begin(), rsize, std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;
  thrust::copy_n(dvals.begin(), rsize, std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;
  return 0;
}
$ nvcc -std=c++11 -o t1009 t1009.cu
$ ./t1009
0,1,3,
1,3,0,
$

使用推力在组中查找元素

Use thrust to find element in groups

cuda

thrust