删除排序列表中的条目：在 GPU 中有效

Question

我正在尝试在 cuda/thrust 中编写以下问题的代码。我得到了一个键列表以及与每个键关联的三个值。我已经设法按字典顺序对它们进行排序。如果具有相同键的输入具有每个值关系，则现在需要减少输入。在下面的示例中，V1(a)<=V1(c)和V2(a)<=V2(c)并且V3(a)<=V3(c)，意味着输入a<=V3(c)。输入 c，因此输入 c 从输出中删除。

输入示例：

       Key      V1      V2      V3  
a.      1       2       5       3
b.      1       2       6       2
c.      1       2       7       4           
d.      1       3       6       5           
e.      2       8       8       8
f.      3       1       2       4

输出示例：

         Key    V1  V2  V3
 a.        1    2   5   3
 b.        1    2   6   2
 e.        2    8   8   8
 f.        3    1   2   4

• 输入 a <输入c==> c 删除
• 输入 a <输入d==> d 删除

我已经能够使用 for 循环和 if 语句解决上述问题。我目前正在尝试使用基于 GPU 的 cuda/thrust 来解决这个问题。这可以在 GPU 上完成（最好是推力）还是必须用 cuda 编写单独的内核？

我还没有使用 推力：删除重复项中讨论的 unique 来制定此问题键值数组

编辑以包含程序“stl/c++”程序来生成上述场景：“Reducing myMap”部分是我使用 for 循环和 if 语句的实现。

#include <iostream>
#include <tr1/array>
#include <vector>
#include <algorithm>

struct mapItem {
    mapItem(int k, int v1, int v2, int v3){
        key=k; 
        std::tr1::array<int,3> v = {v1, v2, v3};
        values=v;
    };
    int key;
    std::tr1::array<int,3> values;
};

struct sortLexiObj{
    bool operator()(const mapItem& lhs, const mapItem& rhs){ 
        return lhs.values < rhs.values; 
    }
};
struct sortKey{
    bool operator()(const mapItem& lhs, const mapItem& rhs){ 
        return lhs.key < rhs.key; 
    }
};

int main(int argc, char** argv){

    std::vector<mapItem> myMap;

    // Set up initial matrix:
    myMap.push_back(mapItem(3, 1, 2, 4));
    myMap.push_back(mapItem(1, 2, 6, 2));
    myMap.push_back(mapItem(1, 2, 5, 3));
    myMap.push_back(mapItem(1, 3, 6, 5));
    myMap.push_back(mapItem(2, 8, 8, 8));
    myMap.push_back(mapItem(1, 2, 7, 4));

    std::sort(myMap.begin(), myMap.end(), sortLexiObj());
    std::stable_sort(myMap.begin(), myMap.end(), sortKey());
    std::cout << "\r\nOriginal sorted Map" << std::endl;
    for(std::vector<mapItem>::iterator mt=myMap.begin(); mt!=myMap.end(); ++mt){
        std::cout << mt->key << "\t";
        for(std::tr1::array<int,3>::iterator it=(mt->values).begin(); it!=(mt->values).end(); ++it){
            std::cout << *it << " ";
        }
        std::cout << std::endl;
    }
    /////////////////////////

    // Reducing myMap
    for(std::vector<mapItem>::iterator it=myMap.begin(); it!=myMap.end(); ++it){
        std::vector<mapItem>::iterator jt=it; ++jt;
        for (; jt != myMap.end();) {
            if (   (it->key == jt->key)){
                if ( it->values.at(0) <= jt->values.at(0) && 
                    it->values.at(1) <= jt->values.at(1) &&
                    it->values.at(2) <= jt->values.at(2) ) {
                    jt = myMap.erase(jt);
                } 
                else ++jt;
            }
            else break;
        }
    }

    std::cout << "\r\nReduced Map" << std::endl;
    for(std::vector<mapItem>::iterator mt=myMap.begin(); mt!=myMap.end(); ++mt){
        std::cout << mt->key << "\t";
        for(std::tr1::array<int,3>::iterator it=(mt->values).begin(); it!=(mt->values).end(); ++it){
            std::cout << *it << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

Answer 1

我认为您可以将 thrust::unique 与谓词一起使用，如 推力：删除键值数组中的重复项。
事实上，我们可以做到这一点，因为unique具有以下特性：

对于 [first、last) 范围内具有相同值的每组连续元素，unique 会删除该组中除第一个之外的所有元素。

，您应该定义一个谓词来测试伪-相等性，对于具有相同键且第一个元组中所有值都较小的元组，它将返回true：

    typedef thrust::tuple<int, int, int, int> tuple_t;
    // a functor which defines your *uniqueness* condition
    struct tupleEqual
    {
      __host__ __device__
        bool operator()(tuple_t x, tuple_t y)
        {
          return ( (x.get<0>() == y.get<0>()) // same key
              && (x.get<1>() <= y.get<1>())   // all values are smaller
              && (x.get<2>() <= y.get<2>()) 
              && (x.get<3>() <= y.get<3>()));
        }
    };

因此 必须将其应用于排序集合。这样，只有第一个元组（最小的）不会被删除。
在 V1、V2 或 V3 中具有相同键和较大值的元组将产生 false，因此不会被删除。

    typedef thrust::device_vector< int >                IntVector;
    typedef IntVector::iterator                         IntIterator;
    typedef thrust::tuple< IntIterator, IntIterator, IntIterator, IntIterator >   IntIteratorTuple;
    typedef thrust::zip_iterator< IntIteratorTuple >    ZipIterator;

    IntVector keyVector;
    IntVector valVector1, valVector2, valVector3;

    tupleEqual predicate;
    ZipIterator newEnd = thrust::unique(
        thrust::make_zip_iterator(
            thrust::make_tuple(
                keyVector.begin(),
                valVector1.begin(),
                valVector2.begin(),
                valVector3.begin() ) ),
        thrust::make_zip_iterator(
            thrust::make_tuple(
                keyVector.end(),
                valVector1.end(),
                valVector2.end(),
                valVector3.end() ) ),
        predicate );

    IntIteratorTuple endTuple = newEnd.get_iterator_tuple();

    keyVector.erase( thrust::get<0>( endTuple ), keyVector.end() );
    valVector1.erase( thrust::get<1>( endTuple ), valVector1.end() );
    valVector2.erase( thrust::get<2>( endTuple ), valVector2.end() );
    valVector3.erase( thrust::get<3>( endTuple ), valVector3.end() );