Databases
StackOverflow2013
Postsdbo
POUsing C++-AMP to reduce runtime of unsorted vector search
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POUsing C++-AMP to reduce runtime of unsorted vector search
    primarykey
    data
    text
    <p>I have written a program that does a lot of searching through an unsorted vector of struct to find indices of unique elements. This searching is done multiple times each iteration in a for-loop and also the data inside the vector changes multiple times during the for-loop iteration (data is only added, nothing is removed). Now the program does what I want it to do, but it is rather slow, so after I let VS2012 analyze the performance of my program I found that more than 80% of the time the program is searching through the unsorted vector, so naturally I want to optimize the searching. I know the best I can get is O(n), because it is an unsorted vector (every element is unique and the order of the elements cannot change once they are inserted), but I am hoping to reduce the runtime somehow.</p> <p>I've been thinking of using parallel processing to reduce the programs runtime and Microsoft's AMP library looks promising. By the looks of it you can use parallel processing to iterate through an array to find an element in the array. But the data in the unsorted vector changes a lot, so won't this move the bottleneck from iterating the vector to data transfer from CPU to GPU or has AMP build-in optimizations to cope with this? Remember: the data in the vector is only added at the end of the vector, nothing is removed.</p> <p>Just in case it helps: here is the vector and the search function I use:</p> <pre><code>struct VertexData { VertexData( unsigned int pos, unsigned int norm, unsigned int tex ) : posIdx(pos), normIdx(norm), texIdx(tex) {} unsigned int posIdx; unsigned int normIdx; unsigned int texIdx; inline bool operator&lt;( const VertexData &amp;rhs ) const { return std::tie(posIdx, normIdx, texIdx) &lt; std::tie(rhs.posIdx, rhs.normIdx, rhs.texIdx); } inline bool operator==( const VertexData &amp;rhs ) const { return std::tie(posIdx, normIdx, texIdx) == std::tie(rhs.posIdx, rhs.normIdx, rhs.texIdx); } }; std::vector&lt;VertexData&gt; verts; int findIndex( const std::vector&lt;VertexData&gt; &amp;vec, const VertexData &amp;val ) const { std::vector&lt;VertexData&gt;::const_iterator it; int idx = 0; for ( it = vec.begin(); it != vec.end(); ++it, ++idx ) if ( *it == val ) return idx; return -1; } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USKrienie
    plurals
    1. This table or related slice is empty.
    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. POUsing C++-AMP to reduce runtime of unsorted vector search
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou don't need to maintain an index and an iterator during the iteration. I would simply use `auto it = std::find(vec.begin(), vec.end(), val); return it == vec.end()? -1: (it - vec.begin());` However, I don't expect that change to make a huge impact.
      singulars
      1. POUsing C++-AMP to reduce runtime of unsorted vector search
      1. USDietmar Kühl
    2. COYou could maintain two data structures, the one you have now for order and another for retrieval.
      singulars
      1. POUsing C++-AMP to reduce runtime of unsorted vector search
      1. USGManNickG
    3. COWhat is stopping you from maintaining some kind of lookup index, or rearranging the array? What exactly is your algorithm designed to do?
      singulars
      1. POUsing C++-AMP to reduce runtime of unsorted vector search
      1. USpaddy
 

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