removing entries in sorted list: efficiently in gpu

I am trying to code the following problem in cuda/thrust. I am given a list of key and three values associated with each keys. I have managed to sort them in lexicographic order. The input now needs to be reduced if inputs with same key have each value-wise relation. In example below, V1(a)<=V1(c) and V2(a)<=V2(c) and V3(a)<=V3(c), implies that Input a < Input c, and hence, Input c is removed from output.

Example Input:

       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

Example Output:

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

• Input a < Input c ==> c removed
• Input a < Input d ==> d removed

I’ve been able to solve the above problem using for-loops, and if-statements. I am currently trying to solve this using gpu based cuda/thrust. Could this be done on the gpu (preferably thrust) or an individual kernel has to be written in cuda ?

I have not been to formulate this problem using unique as discussed in Thrust: Removing duplicates in key-value arrays

Edited to include program "stl/c++" program to generate above scenario: section "Reducing myMap" is my implementation using for-loops and if-statements.

#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;
}

---

I think that you can use thrust::unique with a predicate as it's shown in Thrust: Removing duplicates in key-value arrays. Actually, we can do it because of the following characteristic of unique:

For each group of consecutive elements in the range [first, last) with the same value, unique removes all but the first element of the group.

So, you should define a predicate to test for pseudo-equality that will return true for tuples that have the same key and all values are smaller in the first tuple:

    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>()));
        }
    };

And you have to apply it to a sorted collection. In this way, only the first tuple (the smallest) will not be removed. A tuple with the same key and a bigger value in V1, V2 or V3 will yield false so it won't be removed.

    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() );