如何使用Thrust减少数组中不连续的数字段

Question

我有一维数组“A”，它由许多数组“a”组成，如下所示：

我正在实现一个代码来总结非连续的段（总结“A”中每个数组“a”的相同颜色的段中的数字如下：

任何想法有效地推动？

非常感谢你

注意：图片仅代表一个数组“a”。大数组“A”包含许多数组“a”

Answer 1

在一般情况下，数据的排序和分段的分组事先不知道，一般的建议是使用thrust::sort_by_key将相似的分组组合在一起，然后使用thrust::reduce_by_key对分段求和。给出了here的例子。

但是，如果输入数据段遵循已知的重复模式，例如此处建议的那样，我们可以通过使用thrust::permutation_iterator将类似的段“聚集”在一起来消除排序步骤，作为thrust::reduce_by_key的输入。

使用问题中的示例数据，其中最难的部分是创建置换迭代器。为此，并使用特定数量的段类型（3），段长度（3）和问题中给出的每段类型（3）的段数，我们需要一个映射“向量”（即迭代器）用于我们的置换迭代器具有以下顺序：

0  1  2 9 10 11 18 19 20 3 4 5 12 13 14 21 22 23 ...

然后，该序列将“映射”或重新排列输入数组，以便将所有相似的段组合在一起。我确信有多种方法可以创建这样的序列，但我选择的方法如下。我们将从标准计数迭代器序列开始，然后将变换函数应用于它（使用make_transform_iterator），以便我们创建上述序列。我选择使用以下方法执行此操作，按步骤顺序排列，显示添加到一起的组件：

counting iterator: (_1)                         0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 ...
---------------------------------------------------------------------------------------------------
((_1/seg_len)%seg_types)*(seg_len*seg_types):   0  0  0  9  9  9 18 18 18  0  0  0  9  9  9 18 18 18 ...
 _1%seg_len:                                    0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2 ...
_1/(seg_len*seg_types)*seg_len:                 0  0  0  0  0  0  0  0  0  3  3  3  3  3  3  3  3  3 ...
 Sum:                                           0  1  2  9 10 11 18 19 20  3  4  5 12 13 14 21 22 23 ...            

这是一个完整的例子：

$ cat t457.cu
#include <thrust/reduce.h>
#include <thrust/iterator/permutation_iterator.h>
#include <thrust/iterator/transform_iterator.h>
#include <thrust/iterator/discard_iterator.h>
#include <thrust/device_vector.h>
#include <thrust/copy.h>
#include <iostream>

typedef int dtype;
const int seg_len = 3;
const int seg_types = 3;

using namespace thrust::placeholders;

int main(){

  dtype data[] = {10,16,14,2,4,4,1,2,1,8,2,10,3,1,6,8,0,2,9,1,0,3,5,2,3,2,1};
  //                0   1  2 9 10 11 18 19 20 3 4 5 12 13 14 21 22 23 ...
  //              ((_1/seg_len)%seg_types)*(seg_len*seg_types) + _1%seg_len + (_1/(seg_len*seg_types)*seg_len

  int ads = sizeof(data)/sizeof(data[0]);
  int num_groups = ads/(seg_len*seg_types); // ads is expected to be whole-number divisible by seg_len*seg_types
  int ds = num_groups*(seg_len*seg_types);  // handle the case when it is not
  thrust::device_vector<dtype> d_data(data, data+ds);
  thrust::device_vector<dtype> d_result(seg_types);
  thrust::reduce_by_key(thrust::make_transform_iterator(thrust::counting_iterator<int>(0), _1/(ds/seg_types)), thrust::make_transform_iterator(thrust::counting_iterator<int>(ds), _1/(ds/seg_types)), thrust::make_permutation_iterator(d_data.begin(), thrust::make_transform_iterator(thrust::counting_iterator<int>(0), ((_1/seg_len)%seg_types)*(seg_len*seg_types) + _1%seg_len + (_1/(seg_len*seg_types)*seg_len))), thrust::make_discard_iterator(), d_result.begin());
  thrust::copy(d_result.begin(), d_result.end(), std::ostream_iterator<dtype>(std::cout, ","));
  std::cout << std::endl;
}
$ nvcc -o t457 t457.cu
$ ./t457
70,30,20,
$