title: Counting the length of the Collatz sequence - custom iterator produces slowdown?
body: <p>I've been solving the UVA problem #100 - <a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;problem=36" rel="nofollow">"The 3n + 1 problem"</a>. This is their "sample" problem, with a very forgiving time limit (limit of 3 sec, their <a href="https://uva.onlinejudge.org/data/p100.c.html" rel="nofollow">sample solution</a> with no caching at all runs in 0.738 sec, my best solution so far run in 0.016 sec), so I thought however I'd experiment with the code, I should always fit in the limit. Well, I was mistaken.</p>
  
  <p>The problem specification is simple: each line of input has two numbers <code>i</code> and <code>j</code>, and the output should print these numbers followed by the maximum length of the Collatz sequence whose beginning is in between <code>i</code> and <code>j</code> inclusive.</p>
  
  <p>I've prepared four solutions. They are quite similar and all produce good answers.</p>
  
  <p><a href="http://ideone.com/CEgpur" rel="nofollow">The first solution</a> caches up to <code>0x100000</code> sequence lengths in a <code>vector</code>. Length of <code>0</code> means the length for the sequence that starts at this particular number has not yet been calculated. It runs fast enough - 0.03 sec.</p>
  
  <p><a href="http://ideone.com/k8YvIH" rel="nofollow">The second solution</a> is quite similar, only it caches every singe length in a sparse array implemented with an <code>unordered_map</code>. It runs fairly slower than the previous solution, but still fits well in the limit: 0.28 sec.</p>
  
  <p>As an exercise, I also wrote <a href="http://ideone.com/06etzG" rel="nofollow">the third solution</a>, which based on the second one. The goal was to use the <code>max_element</code> function, which only accepts iterators. I couldn't use <code>unordered_map::iterator</code>, for incrementing such iterator is, AFAIK, linear in map size; therefore, I wrote a custom iterator, operating on an abstract "container" that "holds" the sequence length of every possible number (but in fact calculates them and caches them only as needed). In it's core, it's actually the same <code>unordered_map</code> solution - only there's an extra layer of iterators added on the top. The solution did not fit in the 3 sec. limit.</p>
  
  <p>And now comes the thing I can't understand. While obviously the third solution is overcomplicated on purpose, I could hardly believe that an extra layer of iterators could produce such a slowdown. To check this out, I added a same iterator layer to the <code>vector</code> solution. This is <a href="http://ideone.com/Gzu3KH" rel="nofollow">my fourth solution</a>. Judging from what this iterator idea did to my <code>unordered_map</code> solution, I expected a considerable slowdown here as well; but oddly enough, this did not happen at all. This solution runs almost as fast as the plain <code>vector</code> one, in 0.035 sec.</p>
  
  <p>How is this possible? What exactly is responsible for the slowdown in the third solution? How is it possible that overcomplicating two similar solutions in an exactly the same way slows one of them down very much, and hardly harms the other at all? Why adding the iterator layer to the <code>unordered_map</code> solution made it not fitting in time, and doing the same to the <code>vector</code> solution hardly slowed it down at all?</p>
  
  <p>EDIT:</p>
  
  <p>I found out that the problem seems to be most visible if the input contains many repetitive lines. I tested all four solutions on my machine against the input of <code>1 1000000</code>, repeated 200 times. The solution with a plain vector processed all of them in 1.531 sec. The solution with the vector and the additional iterator layer took 3.087 sec. The solution with the plain unordered map took 33.821 sec. And the solution with the unordered map and the additional iterator layer managed took more than <strong>half an hour</strong> - I halted it after 31 minutes 0.482 sec! I tested it on Linux mint 17.2 64 bit, g++ version Ubuntu 4.8.4-2ubuntu1~14.04 with flags -std=c++11 -O2, processor Celeron 2955U @1.4 GHz x 2</p>