如何使用推力减少数组中非连续的数字段 [英] How to reduce nonconsecutive segments of numbers in array with Thrust
问题描述
我有一维数组 A,它是由许多数组 a组成的,例如:
中数组 a的示例p>
我正在实现一个代码,对不连续的段进行求和(对 A中每个数组 a的相同颜色的段中的数字求和,如下所示:
有什么想法可以有效地做到这一点?
非常感谢
注意:这些图片代表只有一个数组 a。大数组 A包含许多数组 a
在一般情况下,预先不知道数据的顺序和按段分组,一般建议是使用 thrust :: sort_by_key
将类似的细分分组在一起,然后使用 thrust :: reduce_by_key
求和段。在此处中给出了示例。
但是,如果输入数据段遵循已知的重复模式(如此处所示),则可以使用 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
),以便创建上述序列。我选择使用以下方法进行操作,该方法以逐步的顺序排列,显示添加到一起的组件:
计数迭代器: (_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 0 3 3 3 3 3 3 3 3 3 3 ...
总和: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;
使用命名空间推力::占位符;
int main(){
dtype数据[] = {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 ); //广告应能被seg_len * seg_types整除
int ds = num_groups *(seg_len * seg_types); //处理不是
push :: device_vector< dtype> d_data(data,data + ds);
推力:: device_vector< dtype> d_result(seg_types);
推力:: reduce_by_key(thrust :: make_transform_iterator(thrust :: counting_iterator< int>(0 ),_ 1 /(ds / seg_types)),推力:: make_transform_iterator(推力:: counting_iterator< int>(ds),_ 1 /(ds / seg_types)),推力:: make_permutation_iterator(d_data.begin(),推力:: 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)* s eg_len))),推力:: make_discard_iterator(),d_result.begin());
推力:: 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,
$
I have 1D array "A" which is composed from many arrays "a" like this :
I'm implementing a code to sum up non consecutive segments ( sum up the numbers in the segments of the same color of each array "a" in "A" as follow:
Any ideas to do that efficiently with thrust?
Thank you very much
Note: The pictures represents only one array "a". The big array "A" contains many arrays "a"
In the general case, where the ordering of the data and grouping by segments is not known in advance, the general suggestion is to use thrust::sort_by_key
to group like segments together, and then use thrust::reduce_by_key
to sum the segments. Examples are given here.
However, if the input data segments follow a known repeating pattern, such as is suggested here, we can eliminate the sorting step by using a thrust::permutation_iterator
to "gather" the like segments together, as the input to thrust::reduce_by_key
.
Using the example data in the question, the hard part of this is to create the permutation iterator. For that, and using the specific number of segment types (3), segment lengths (3) and number of segments per segment type (3) given in the question, we need a map "vector" (i.e. iterator) for our permutation iterator that has the following sequence:
0 1 2 9 10 11 18 19 20 3 4 5 12 13 14 21 22 23 ...
This sequence would then "map" or rearrange the input array, so that all like segments are grouped together. I'm sure there are various ways to create such a sequence, but the approach I chose is as follows. We will start with the standard counting iterator sequence, and then apply a transform functor to it (using make_transform_iterator
), so that we create the above sequence. I chose to do it using the following method, arranged in a stepwise sequence showing the components that are added together:
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 ...
Here is a fully worked example:
$ 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,
$
这篇关于如何使用推力减少数组中非连续的数字段的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!