Databases
StackOverflow2013
Postsdbo
POC++ std::map creation taking too long?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POC++ std::map creation taking too long?
    primarykey
    data
    text
    <p>UPDATED:</p> <p>I am working on a program whose performance is very critical. I have a vector of structs that are NOT sorted. I need to perform many search operations in this vector. So I decided to cache the vector data into a map like this:</p> <pre><code> std::map&lt;long, int&gt; myMap; for (int i = 0; i &lt; myVector.size(); ++i) { const Type&amp; theType = myVector[i]; myMap[theType.key] = i; } </code></pre> <p>When I search the map, the results of the rest of the program are much faster. However, the remaining bottleneck is the creation of the map itself (it is taking about 0.8 milliseconds on average to insert about 1,500 elements in it). I need to figure out a way to trim this time down. I am simply inserting a long as the key and an int as the value. I don't understand why it is taking this long.</p> <p>Another idea I had was to create a copy of the vector (can't touch the original one) and somehow perform a faster sort than the std::sort (it takes way too long to sort it).</p> <p>Edit: </p> <p>Sorry everyone. I meant to say that I am creating a std::map where the key is a long and the value is an int. The long value is the struct's key value and the int is the index of the corresponding element in the vector.</p> <p>Also, I did some more debugging and realized that the vector is not sorted at all. It's completely random. So doing something like a stable_sort isn't going to work out.</p> <p>ANOTHER UPDATE:</p> <p>Thanks everyone for the responses. I ended up creating a vector of pairs (std::vector of std::pair(long, int)). Then I sorted the vector by the long value. I created a custom comparator that only looked at the first part of the pair. Then I used lower_bound to search for the pair. Here's how I did it all:</p> <pre><code> typedef std::pair&lt;long,int&gt; Key2VectorIndexPairT; typedef std::vector&lt;Key2VectorIndexPairT&gt; Key2VectorIndexPairVectorT; bool Key2VectorIndexPairComparator(const Key2VectorIndexPairT&amp; pair1, const Key2VectorIndexPairT&amp; pair2) { return pair1.first &lt; pair2.first; } ... Key2VectorIndexPairVectorT sortedVector; sortedVector.reserve(originalVector.capacity()); // Assume "original" vector contains unsorted elements. for (int i = 0; i &lt; originalVector.size(); ++i) { const TheStruct&amp; theStruct = originalVector[i]; sortedVector.insert(Key2VectorIndexPairT(theStruct.key, i)); } std::sort(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairComparator); ... const long keyToSearchFor = 20; const Key2VectorIndexPairVectorT::const_iterator cItorKey2VectorIndexPairVector = std::lower_bound(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairT(keyToSearchFor, 0 /* Provide dummy index value for search */), Key2VectorIndexPairComparator); if (cItorKey2VectorIndexPairVector-&gt;first == keyToSearchFor) { const int vectorIndex = cItorKey2VectorIndexPairVector-&gt;second; const TheStruct&amp; theStruct = originalVector[vectorIndex]; // Now do whatever you want... } else { // Could not find element... } </code></pre> <p>This yielded a modest performance gain for me. Before the total time for my calculations were 3.75 milliseconds and now it is down to 2.5 milliseconds.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAndrew
    1. USAndrew
    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
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POC++ std::map creation taking too long?
      1. USAndriy Tylychko
      1. VTFavorite
    2. VO
      singulars
      1. POC++ std::map creation taking too long?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POC++ std::map creation taking too long?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou don't say what `Type` is. Maybe it has an expensive copy constructor?
      singulars
      1. POC++ std::map creation taking too long?
      1. USrodrigo
    2. COSorry, "Type" is a struct that contains about 10 double values and a long value (the key). I don't even copy the Type into the map. Only the key and the corresponding index in the vector.
      singulars
      1. POC++ std::map creation taking too long?
      1. USAndrew
    3. COor more likely 1500+ calls to new.
      singulars
      1. POC++ std::map creation taking too long?
      1. USMooing Duck
 

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