Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>Here is another way that relies on memorising all the numbers already explored. I obtain a factor x4-5, which is oddly stable against DrAsik's code for 1000 and 1000000, I expected the cache to be more efficient the more numbers we were exploring. Otherwise, the same kind of classic optimizations have been applied. BTW, if the compiler accepts NRVO <em>(/RNVO ? I never remember the exact term)</em> or rvalue references, we wouldn't need to pass the vector as an <em>out</em> parameter.</p> <p>NB: micro-optimizations are still possible IMHO, and moreover the caching is naive as it allocates much more memory than really needed.</p> <pre><code>enum Status { never_seen, being_explored, happy, unhappy }; char const* toString[] = { "never_seen", "being_explored", "happy", "unhappy" }; inline size_t sum_squares(size_t i) { size_t s = 0; while (i) { const size_t digit = i%10; s += digit * digit; i /= 10; } return s ; } struct Cache { Cache(size_t dim) : m_cache(dim, never_seen) {} void set(size_t n, Status status) { if (m_cache.size() &lt;= n) { m_cache.resize(n+1, never_seen); } m_cache[n] = status; // std::cout &lt;&lt; "(c[" &lt;&lt; n &lt;&lt; "]&lt;-"&lt;&lt;toString[status] &lt;&lt; ")"; } Status operator[](size_t n) const { if (m_cache.size() &lt;= n) { return never_seen; } else { return m_cache[n]; } } private: std::vector&lt;Status&gt; m_cache; }; void search_happy_lh(size_t upper_bound, std::vector&lt;size_t&gt; &amp; happy_numbers) { happy_numbers.clear(); happy_numbers.reserve(upper_bound); // it doesn't improve much the performances Cache cache(upper_bound+1); std::vector&lt;size_t&gt; current_stack; cache.set(1,happy); happy_numbers.push_back(1); for (size_t i = 2; i&lt;=upper_bound ; ++i) { // std::cout &lt;&lt; "\r" &lt;&lt; i &lt;&lt; std::flush; current_stack.clear(); size_t s= i; while ( s != 1 &amp;&amp; cache[s]==never_seen) { current_stack.push_back(s); cache.set(s, being_explored); s = sum_squares(s); // std::cout &lt;&lt; " - " &lt;&lt; s &lt;&lt; std::flush; } const Status update_with = (cache[s]==being_explored ||cache[s]==unhappy) ? unhappy : happy; // std::cout &lt;&lt; " =&gt; " &lt;&lt; s &lt;&lt; ":" &lt;&lt; toString[update_with] &lt;&lt; std::endl; for (size_t j=0; j!=current_stack.size(); ++j) { cache.set(current_stack[j], update_with); } if (cache[i] == happy) { happy_numbers.push_back(i); } } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

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