Databases
StackOverflow2013
Postsdbo
POWhy is the recursive version of this function faster?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy is the recursive version of this function faster?
    primarykey
    data
    text
    <p>Here is a simple class for iterating over a multidimensional numeric range:</p> <pre><code>#include &lt;array&gt; #include &lt;limits&gt; template &lt;int N&gt; class NumericRange { public: // typedef std::vector&lt;double&gt;::const_iterator const_iterator; NumericRange() { _lower.fill(std::numeric_limits&lt;double&gt;::quiet_NaN()); _upper.fill(std::numeric_limits&lt;double&gt;::quiet_NaN()); _delta.fill(std::numeric_limits&lt;double&gt;::quiet_NaN()); } NumericRange(const std::array&lt;double, N&gt; &amp; lower, const std::array&lt;double, N&gt; &amp; upper, const std::array&lt;double, N&gt; &amp; delta): _lower(lower), _upper(upper), _delta(delta) { _state.fill(std::numeric_limits&lt;double&gt;::quiet_NaN()); _next_index_to_advance = 0; } const std::array&lt;double, N&gt; &amp; get_state() const { return _state; } void start() { _state = _lower; } bool in_range(int index_to_advance = N-1) const { return ( _state[ index_to_advance ] - _upper[ index_to_advance ] ) &lt; _delta[ index_to_advance ]; } void advance(int index_to_advance = 0) { _state[ index_to_advance ] += _delta[ index_to_advance ]; if ( ! in_range(index_to_advance) ) { if (index_to_advance &lt; N-1) { // restart index_to_advance _state[index_to_advance] = _lower[index_to_advance]; // carry index_to_advance; advance(index_to_advance+1); } } } private: std::array&lt;double, N&gt; _lower, _upper, _delta, _state; int _next_index_to_advance; }; int main() { std::array&lt;double, 7&gt; lower{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0}; std::array&lt;double, 7&gt; upper{1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0}; std::array&lt;double, 7&gt; delta{0.03, 0.06, 0.03, 0.06, 0.03, 0.06, 0.03}; NumericRange&lt;7&gt; nr(lower, upper, delta); int c = 0; for (nr.start(); nr.in_range(); nr.advance()) { const std::array&lt;double, 7&gt; &amp; st = nr.get_state(); ++c; } std::cout &lt;&lt; "took " &lt;&lt; c &lt;&lt; " steps" &lt;&lt; std::endl; return 0; } </code></pre> <p>When I replace the <code>advance</code> function with a non-recursive variant, the runtime <em>increases</em>:</p> <pre><code>void advance(int index_to_advance = 0) { bool carry; do { carry = false; _state[ index_to_advance ] += _delta[ index_to_advance ]; if ( ! in_range(index_to_advance) ) { if (index_to_advance &lt; N-1) { // restart index_to_advance _state[index_to_advance] = _lower[index_to_advance]; // carry ++index_to_advance; carry = true; // advance(index_to_advance); } } } while (carry); } </code></pre> <p>Runtimes were taken using unix user time via the command <code>time</code>. The code was compiled using gcc-4.7 with options <code>-std=c++11 -O3</code> (but I think it should work with <code>c++0x</code> on gcc-4.6). The recursive version took 13s and the iterative version took 30s. Both require the same number of <code>advance</code> calls to terminate (and if you print the <code>nr.get_state()</code> array inside the <code>for(ns.start()...)</code> loop, both do the same thing).</p> <p>This is a fun riddle! Help me figure out why recursive would be more efficient / more optimizable.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USuser
    1. USuser
    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. POWhy is the recursive version of this function faster?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhy is the recursive version of this function faster?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWhy is the recursive version of this function faster?
      1. USmjhennig
      1. VTFavorite
    1. COTry profiling. `valgrind --callgrind` is an good profiler.
      singulars
      1. POWhy is the recursive version of this function faster?
      1. USn.m.
    2. COPersonally I like gdb. Break + backtrace
      singulars
      1. POWhy is the recursive version of this function faster?
      1. USDavid Stone
    3. COThe performance I'm seeing is inconsistent. For the iterative version, I either get 30 or 100 seconds on different runs. Perhaps there is a subtle caching issue.
      singulars
      1. POWhy is the recursive version of this function faster?
      1. USVaughn Cato
 

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