推力：删除键值数组中的重复项 | 删除键值数组中的重复项

本文介绍了推力：删除键值数组中的重复项的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有一对相等大小的数组，我将它们称为键和值。

例如：

这些键被排序，并且与每个键相关联的值是
排序的。如何删除与每个键
及其相应键相关联的值重复？

是，我要压缩上面的：

  1：99 
 1：100 
 1： 103 
 2：103<  - 这应该保持，因为关键是不同
 2：105 
 3：45 
 3：67 
  
 
 
 我查看了 Thrust 中提供的流压缩函数，但
没能找到任何这样做。这是可能与
 Thrust吗？或者，我需要编写自己的内核来标记
a stencil中的重复项，然后删除它们。
解决方案
键进行排序，并且与每个键相关联的值也被排序。因此，我们可以考虑对键值对进行排序。  thrust :: unique 将直接工作，如果它可以看到这两个向量作为一个单一的向量。这可以通过使用 zip_iterator 将每个位置处的2个项目（键值）压缩成单个元组来实现。
 
 
 这里是如何实现这个就地和也修剪键值向量只有唯一的元素：
  typedef thrust :: device_vector< int> IntVector; 
 typedef IntVector :: iterator IntIterator; 
 typedef thrust :: tuple< IntIterator，IntIterator> IntIteratorTuple; 
 typedef thrust :: zip_iterator< IntIteratorTuple> ZipIterator; 
 
 IntVector keyVector; 
 IntVector valVector; 
 
 ZipIterator newEnd = thrust :: unique（thrust :: make_zip_iterator（thrust :: make_tuple（keyVector.begin（），valVector.begin（））），
 thrust :: make_zip_iterator :: make_tuple（keyVector.end（），valVector.end（））））; 
 
 IntIteratorTuple endTuple = newEnd.get_iterator_tuple（）; 
 
 keyVector.erase（thrust :: get< 0>（endTuple），keyVector.end（））; 
 valVector.erase（thrust :: get< 1>（endTuple），valVector.end（））; 
  
如果你想压缩和产生一个单独的结果流，你需要编写自己的二进制谓词你的类型，看两个元素的元组。  thrust :: zip_iterator 可用于从单独的数组形成一个虚拟元组迭代器。
 
 
 一个完整的工作示例你如何做到这一点看起来像这样：
  #include< iostream> 
 #include< thrust / tuple.h> 
 #include< thrust / functional.h> 
 #include< thrust / device_vector.h> 
 #include< thrust / iterator / zip_iterator.h> 
 #include< thrust / unique.h> 
 
 //用于元组对的二进制谓词
 typedef thrust :: tuple< int，int> tuple_t; 
 struct tupleEqual 
 {
 __host__ __device__ 
 bool operator（）（tuple_t x，tuple_t y）
 {
 return（（x.get< 0> （）== y.get< 0>（））&&（x.get 1（）== y.get& 
} 
}; 
 
 typedef thrust :: device_vector< int> :: iterator intIterator; 
 typedef thrust :: tuple< intIterator，intIterator> intIteratorTuple; 
 typedef thrust :: zip_iterator< intIteratorTuple>压缩器; 
 typedef thrust :: device_vector< tuple_t> :: iterator tupleIterator; 
 
 int main（void）
 {
 thrust :: device_vector< int> k（9），v（9）; 
 thrust :: device_vector< tuple_t> kvcopy（9）; 
 
 k [0] = 1; k [1] = 1; k [2] = 1; 
 k [3] = 1 k [4] = 1; k [5] = 2; 
 k [6] = 2; k [7] = 3; k [8] = 3; 
 
 v [0] = 99; v [1] = 100; v [2] = 100; 
 v [3] = 100; v [4] = 103; v [5] = 103; 
 v [6] = 105; v [7] = 45; v [8] = 67; 
 
 zipIterator kvBegin（thrust :: make_tuple（k.begin（），v.begin（）））; 
 zipIterator kvEnd（thrust :: make_tuple（k.end（），v.end（）））; 
 thrust :: copy（kvBegin，kvEnd，kvcopy.begin（））; 
 
 tupleIterator kvend = 
 thrust :: unique（kvcopy.begin（），kvcopy.end（），tupleEqual（））; 
 
 for（tupleIterator kvi = kvcopy.begin（）; kvi！= kvend; kvi ++）{
 tuple_t r = * kvi; 
 std :: cout<< r.get< 0>（）<< ，< r.get 1（）<< std :: endl; 
} 
 
 return 0; 
} 
  
 
I have a pair of arrays of equal size, I will call them keys and values.
For example:
K: V
1: 99
1: 100
1: 100
1: 100
1: 103
2: 103
2: 105
3: 45
3: 67
The keys are sorted and the values associated with each key aresorted. How do I remove the value duplicates associated with each keyand its corresponding key?
That is, I want to compact the above to:
1: 99
1: 100
1: 103
2: 103 <-- This should remain, since key is different
2: 105
3: 45
3: 67
I looked at the stream compaction functions available in Thrust, butwas not able to find anything which does this. Is this possible withThrust? Or do I need to write my own kernel to mark the duplicates ina stencil and then remove them?
 解决方案 
The keys are sorted and the values associated with each key are also sorted. Thus, we can consider that the key-value pairs are sorted. thrust::unique will work directly on this if it can see these 2 vectors as a single vector. This can be achieved by zipping up the 2 items (key-value) at each position into a single tuple using zip_iterator.
Here is how to achieve this in-place and also trim the key-value vectors to only the unique elements:
typedef thrust::device_vector< int >                IntVector;
typedef IntVector::iterator                         IntIterator;
typedef thrust::tuple< IntIterator, IntIterator >   IntIteratorTuple;
typedef thrust::zip_iterator< IntIteratorTuple >    ZipIterator;

IntVector keyVector;
IntVector valVector;

ZipIterator newEnd = thrust::unique( thrust::make_zip_iterator( thrust::make_tuple( keyVector.begin(), valVector.begin() ) ),
                                     thrust::make_zip_iterator( thrust::make_tuple( keyVector.end(), valVector.end() ) ) );

IntIteratorTuple endTuple = newEnd.get_iterator_tuple();

keyVector.erase( thrust::get<0>( endTuple ), keyVector.end() );
valVector.erase( thrust::get<1>( endTuple ), valVector.end() );
If you want to compact and produce a separate result stream, you need to write your own binary predicate for your type which looks at both elements of the tuple. The thrust::zip_iterator can be used to form a virtual tuple iterator from separate arrays.
A complete working example of how you might do it looks like this:
#include <iostream>
#include <thrust/tuple.h>
#include <thrust/functional.h>
#include <thrust/device_vector.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/unique.h>

// Binary predicate for a tuple pair
typedef thrust::tuple<int, int> tuple_t;
struct tupleEqual
{
  __host__ __device__
    bool operator()(tuple_t x, tuple_t y)
    {
      return ( (x.get<0>()== y.get<0>()) && (x.get<1>() == y.get<1>()) );
    }
};

typedef thrust::device_vector<int>::iterator  intIterator;
typedef thrust::tuple<intIterator, intIterator> intIteratorTuple;
typedef thrust::zip_iterator<intIteratorTuple> zipIterator;
typedef thrust::device_vector<tuple_t>::iterator tupleIterator;

int main(void)
{
  thrust::device_vector<int> k(9), v(9);
  thrust::device_vector<tuple_t> kvcopy(9);

  k[0] = 1; k[1] = 1; k[2] = 1;
  k[3] = 1; k[4] = 1; k[5] = 2;
  k[6] = 2; k[7] = 3; k[8] = 3;

  v[0] = 99;  v[1] = 100; v[2] = 100;
  v[3] = 100; v[4] = 103; v[5] = 103;
  v[6] = 105; v[7] = 45;  v[8] = 67;

  zipIterator kvBegin(thrust::make_tuple(k.begin(),v.begin()));
  zipIterator kvEnd(thrust::make_tuple(k.end(),v.end()));
  thrust::copy(kvBegin, kvEnd, kvcopy.begin());

  tupleIterator kvend =
        thrust::unique(kvcopy.begin(), kvcopy.end(), tupleEqual());

  for(tupleIterator kvi = kvcopy.begin(); kvi != kvend; kvi++) {
    tuple_t r = *kvi;
    std::cout << r.get<0>() << "," << r.get<1>() << std::endl;
  }

  return 0;
}
                        
这篇关于推力：删除键值数组中的重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！