Databases
StackOverflow2013
Postsdbo
POremoving entries in sorted list: efficiently in gpu
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POremoving entries in sorted list: efficiently in gpu
    primarykey
    data
    text
    <p>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)&lt;=V1(c) and V2(a)&lt;=V2(c) and V3(a)&lt;=V3(c), implies that Input a &lt; Input c, and hence, Input c is removed from output.</p> <p>Example Input:</p> <pre><code> 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 </code></pre> <p>Example Output:</p> <pre><code> Key V1 V2 V3 a. 1 2 5 3 b. 1 2 6 2 e. 2 8 8 8 f. 3 1 2 4 </code></pre> <ul> <li>Input a &lt; Input c ==> c removed</li> <li>Input a &lt; Input d ==> d removed</li> </ul> <p>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 ?</p> <p>I have not been to formulate this problem using unique as discussed in <a href="https://stackoverflow.com/questions/5521091/thrust-removing-duplicates-in-key-value-arrays">Thrust: Removing duplicates in key-value arrays</a></p> <p>Edited to include program "stl/c++" program to generate above scenario: section "Reducing myMap" is my implementation using for-loops and if-statements.</p> <pre><code>#include &lt;iostream&gt; #include &lt;tr1/array&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; struct mapItem { mapItem(int k, int v1, int v2, int v3){ key=k; std::tr1::array&lt;int,3&gt; v = {v1, v2, v3}; values=v; }; int key; std::tr1::array&lt;int,3&gt; values; }; struct sortLexiObj{ bool operator()(const mapItem&amp; lhs, const mapItem&amp; rhs){ return lhs.values &lt; rhs.values; } }; struct sortKey{ bool operator()(const mapItem&amp; lhs, const mapItem&amp; rhs){ return lhs.key &lt; rhs.key; } }; int main(int argc, char** argv){ std::vector&lt;mapItem&gt; 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 &lt;&lt; "\r\nOriginal sorted Map" &lt;&lt; std::endl; for(std::vector&lt;mapItem&gt;::iterator mt=myMap.begin(); mt!=myMap.end(); ++mt){ std::cout &lt;&lt; mt-&gt;key &lt;&lt; "\t"; for(std::tr1::array&lt;int,3&gt;::iterator it=(mt-&gt;values).begin(); it!=(mt-&gt;values).end(); ++it){ std::cout &lt;&lt; *it &lt;&lt; " "; } std::cout &lt;&lt; std::endl; } ///////////////////////// // Reducing myMap for(std::vector&lt;mapItem&gt;::iterator it=myMap.begin(); it!=myMap.end(); ++it){ std::vector&lt;mapItem&gt;::iterator jt=it; ++jt; for (; jt != myMap.end();) { if ( (it-&gt;key == jt-&gt;key)){ if ( it-&gt;values.at(0) &lt;= jt-&gt;values.at(0) &amp;&amp; it-&gt;values.at(1) &lt;= jt-&gt;values.at(1) &amp;&amp; it-&gt;values.at(2) &lt;= jt-&gt;values.at(2) ) { jt = myMap.erase(jt); } else ++jt; } else break; } } std::cout &lt;&lt; "\r\nReduced Map" &lt;&lt; std::endl; for(std::vector&lt;mapItem&gt;::iterator mt=myMap.begin(); mt!=myMap.end(); ++mt){ std::cout &lt;&lt; mt-&gt;key &lt;&lt; "\t"; for(std::tr1::array&lt;int,3&gt;::iterator it=(mt-&gt;values).begin(); it!=(mt-&gt;values).end(); ++it){ std::cout &lt;&lt; *it &lt;&lt; " "; } std::cout &lt;&lt; std::endl; } return 0; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USwaqy
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POremoving entries in sorted list: efficiently in gpu
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POremoving entries in sorted list: efficiently in gpu
      1. USMarek Kurdej
      1. VTFavorite
    3. VO
      singulars
      1. POremoving entries in sorted list: efficiently in gpu
      1. USMarek Kurdej
      1. VTFavorite
    1. COHaving trouble identifying precisely what you need, but it seems like thrust::unique_by_key might be the solution. Could you post a link to your serial solution?
      singulars
      1. POremoving entries in sorted list: efficiently in gpu
      1. USJared Hoberock
    2. COAdded code in original post.
      singulars
      1. POremoving entries in sorted list: efficiently in gpu
      1. USwaqy
    3. COI dont' think `thrust::unique_by_key` will work in an easy way because it does the unique step by looking at adjacent elements. The solution needs to look at all possible pairs.
      singulars
      1. POremoving entries in sorted list: efficiently in gpu
      1. USNathan Whitehead
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload