Menghitung panjang urutan Collatz - iterator khusus menghasilkan perlambatan?

Saya telah memecahkan masalah UVA #100 - "The 3n + 1 masalah". Ini adalah "contoh" masalah mereka, dengan batas waktu yang sangat mudah (batas 3 detik, mereka solusi sampel tanpa caching sama sekali berjalan dalam 0,738 detik, solusi terbaik saya sejauh ini berjalan dalam 0,016 detik), jadi saya pikir bagaimanapun saya bereksperimen dengan kode, saya harus selalu memenuhi batasnya. Ya, saya salah.

Spesifikasi masalahnya sederhana: setiap baris masukan memiliki dua angka i dan j, dan keluarannya harus mencetak angka-angka ini diikuti dengan panjang maksimum rangkaian Collatz yang awalnya berada di antara i dan j inklusif.

Saya sudah menyiapkan empat solusi. Semuanya sangat mirip dan semuanya menghasilkan jawaban yang bagus.

Solusi pertama menyimpan cache hingga 0x100000 panjang urutan dalam vector. Panjang 0 berarti panjang barisan yang dimulai pada bilangan tertentu ini belum dihitung. Ini berjalan cukup cepat - 0,03 detik.

Solusi kedua cukup mirip, hanya saja solusi ini menyimpan setiap panjang tunggal dalam array renggang yang diimplementasikan dengan unordered_map. Ini berjalan cukup lambat dibandingkan solusi sebelumnya, tetapi masih sesuai dengan batasnya: 0,28 detik.

Sebagai latihan, saya juga menulis solusi ketiga, yang didasarkan pada solusi kedua. Tujuannya adalah menggunakan fungsi max_element, yang hanya menerima iterator. Saya tidak bisa menggunakan unordered_map::iterator, untuk menambah iterator seperti itu, AFAIK, linier dalam ukuran peta; oleh karena itu, saya menulis sebuah iterator khusus, yang beroperasi pada "wadah" abstrak yang "menampung" panjang urutan setiap nomor yang mungkin (tetapi sebenarnya menghitungnya dan menyimpannya dalam cache hanya jika diperlukan). Pada intinya, ini sebenarnya solusi unordered_map yang sama - hanya saja ada lapisan iterator tambahan yang ditambahkan di atas. Solusinya tidak sesuai dalam 3 detik. membatasi.

Dan sekarang tibalah hal yang tidak dapat saya mengerti. Meskipun solusi ketiga sengaja dibuat terlalu rumit, saya hampir tidak percaya bahwa lapisan iterator tambahan dapat menyebabkan perlambatan seperti itu. Untuk memeriksanya, saya menambahkan lapisan iterator yang sama ke solusi vector. Ini adalah solusi keempat saya. Menilai dari apa yang dilakukan ide iterator ini terhadap solusi unordered_map saya, saya memperkirakan akan terjadi perlambatan yang cukup besar di sini juga; tapi anehnya, hal ini tidak terjadi sama sekali. Solusi ini berjalan hampir secepat solusi vector biasa, dalam 0,035 detik.

Bagaimana ini mungkin? Apa sebenarnya penyebab lambatnya solusi ketiga? Bagaimana mungkin memperumit dua solusi serupa dengan cara yang persis sama akan memperlambat salah satu solusi, dan hampir tidak merugikan solusi lainnya sama sekali? Mengapa menambahkan lapisan iterator ke solusi unordered_map membuatnya tidak tepat waktu, dan melakukan hal yang sama pada solusi vector hampir tidak memperlambatnya sama sekali?

Sunting:

Saya menemukan bahwa masalahnya tampaknya paling terlihat jika masukan berisi banyak baris berulang. Saya menguji keempat solusi di mesin saya terhadap input 1 1000000, diulangi 200 kali. Solusi dengan vektor biasa memproses semuanya dalam 1,531 detik. Solusi dengan vektor dan lapisan iterator tambahan membutuhkan waktu 3,087 detik. Solusi dengan peta polos tidak berurutan membutuhkan waktu 33,821 detik. Dan solusi dengan peta tidak berurutan dan lapisan iterator tambahan yang dikelola memerlukan waktu lebih dari setengah jam - Saya menghentikannya setelah 31 menit 0,482 detik! Saya mengujinya di Linux mint 17.2 64 bit, g++ versi Ubuntu 4.8.4-2ubuntu1~14.04 dengan flag -std=c++11 -O2, prosesor Celeron 2955U @1.4 GHz x 2