Databases
StackOverflow2013
Postsdbo
POHow to speed-up a simple method (preferably without changing interfaces or data structures)?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to speed-up a simple method (preferably without changing interfaces or data structures)?
    primarykey
    data
    text
    <p>I have some data structures: </p> <ul> <li><code>all_unordered_m</code> is a big vector containing all the strings I need (all different)</li> <li><code>ordered_m</code> is a small vector containing the indexes of a subset of the strings (all different) in the former vector</li> <li><code>position_m</code> maps the indexes of objects from the first vector to their position in the second one.</li> </ul> <p>The <code>string_after(index, reverse)</code> method returns the string referenced by ordered_m <em>after</em> <code>all_unordered_m[index]</code>.</p> <p><code>ordered_m</code> is considered circular, and is explored in natural or reverse order depending on the second parameter.</p> <p>The code is something like the following:</p> <pre><code>struct ordered_subset { // [...] std::vector&lt;std::string&gt;&amp; all_unordered_m; // size = n &gt;&gt; 1 std::vector&lt;size_t&gt; ordered_m; // size &lt;&lt; n std::tr1::unordered_map&lt;size_t, size_t&gt; position_m; const std::string&amp; string_after(size_t index, bool reverse) const { size_t pos = position_m.find(index)-&gt;second; if(reverse) pos = (pos == 0 ? orderd_m.size() - 1 : pos - 1); else pos = (pos == ordered.size() - 1 ? 0 : pos + 1); return all_unordered_m[ordered_m[pos]]; } }; </code></pre> <p>Given that:</p> <ul> <li>I do need all of the data-structures for other purposes;</li> <li>I cannot change them because I need to access the strings: <ul> <li>by their id in the all_unordered_m;</li> <li>by their index inside the various ordered_m; </li> </ul></li> <li>I need to know the position of a string (identified by it's position in the first vector) inside ordered_m vector;</li> <li>I cannot change the string_after interface without changing most of the program.</li> </ul> <p>How can I speed up the <code>string_after</code> method that is called billions of times and is eating up about 10% of the execution time?</p> <p><strong>EDIT:</strong> I've tried making <code>position_m</code> a <code>vector</code> instead of a <code>unordered_map</code> and using the following method to avoid jumps:</p> <pre><code>string_after(size_t index, int direction) const { return all_unordered_m[ordered_m[ (ordered_m.size()+position_m[index]+direction)%ordered_m.size()]]; } </code></pre> <p>The change in position_m seems to be the most effective (I'm not sure that eliminating the branches made any difference, I'm tempted to say that the code is more compact but equally efficient with that regard).</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USbaol
    1. USbaol
    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
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to speed-up a simple method (preferably without changing interfaces or data structures)?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow to speed-up a simple method (preferably without changing interfaces or data structures)?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow to speed-up a simple method (preferably without changing interfaces or data structures)?
      1. USbaol
      1. VTFavorite
    1. COFirst time I've ever seen anyone putting the *m_* (*_m* in this case) to the *right* of the member variable time.
      singulars
      1. POHow to speed-up a simple method (preferably without changing interfaces or data structures)?
      1. USViktor Sehr
    2. COSeems like I'm not Hungarian! ;)
      singulars
      1. POHow to speed-up a simple method (preferably without changing interfaces or data structures)?
      1. USbaol
    3. CO(btw: having the _m on the right let me focus on the variable name!)
      singulars
      1. POHow to speed-up a simple method (preferably without changing interfaces or data structures)?
      1. USbaol
 

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