กำลังนับความยาวของลำดับ Collatz - ตัววนซ้ำแบบกำหนดเองทำให้เกิดการชะลอตัวหรือไม่

ฉันได้แก้ไขปัญหา UVA #100 แล้ว - "The 3n + 1 ปัญหา". นี่คือปัญหา "ตัวอย่าง" ของพวกเขา โดยมีการจำกัดเวลาให้อภัยอย่างมาก (จำกัดที่ 3 วินาที โซลูชันตัวอย่างที่ไม่มีการแคชเลย รันใน 0.738 วินาที ซึ่งเป็นทางออกที่ดีที่สุดของฉันจนถึงตอนนี้ทำงานใน 0.016 วินาที) ดังนั้นฉันคิดว่าไม่ว่าจะทดลองโค้ดอย่างไร ฉันควรจะพอดีกับขีดจำกัดเสมอ ฉันคิดผิด

ข้อกำหนดเฉพาะของปัญหานั้นเรียบง่าย: แต่ละบรรทัดอินพุตมีตัวเลข 2 ตัว i และ j และเอาต์พุตควรพิมพ์ตัวเลขเหล่านี้ตามด้วยความยาวสูงสุดของลำดับ Collatz ซึ่งจุดเริ่มต้นอยู่ระหว่าง i ถึง j รวม

ฉันได้เตรียมวิธีแก้ปัญหาไว้สี่ประการ พวกมันค่อนข้างคล้ายกันและให้คำตอบที่ดีทั้งหมด

วิธีแก้ปัญหาแรกแคชความยาวลำดับสูงสุด 0x100000 ใน vector ความยาว 0 หมายถึงยังไม่ได้คำนวณความยาวของลำดับที่เริ่มต้นที่ตัวเลขนี้ มันทำงานเร็วพอ - 0.03 วินาที

วิธีแก้ไขปัญหาที่สอง ค่อนข้างคล้ายกัน เพียงแต่แคชทุกความยาวในอาร์เรย์แบบกระจัดกระจายที่ใช้กับ unordered_map มันทำงานค่อนข้างช้ากว่าโซลูชันก่อนหน้า แต่ก็ยังพอดีในขีดจำกัด: 0.28 วินาที

เพื่อเป็นแบบฝึกหัด ฉันยังได้เขียนวิธีแก้ปัญหาที่สาม ซึ่งอิงจากวิธีแก้ปัญหาที่สอง เป้าหมายคือการใช้ฟังก์ชัน max_element ซึ่งยอมรับเฉพาะตัววนซ้ำเท่านั้น ฉันไม่สามารถใช้ unordered_map::iterator สำหรับการเพิ่มตัววนซ้ำเช่น AFAIK ขนาดแผนที่เชิงเส้น ดังนั้นฉันจึงเขียนตัววนซ้ำที่กำหนดเองซึ่งทำงานบน "คอนเทนเนอร์" แบบนามธรรมที่ "เก็บ" ความยาวลำดับของทุกจำนวนที่เป็นไปได้ (แต่อันที่จริงคำนวณและแคชไว้ตามความจำเป็นเท่านั้น) ในแกนกลางของมันจริง ๆ แล้วมันเป็นโซลูชัน unordered_map เดียวกัน - มีเพียงตัววนซ้ำเลเยอร์เพิ่มเติมที่เพิ่มไว้ด้านบน วิธีแก้ปัญหาไม่พอดีใน 3 วินาที ขีด จำกัด

และมาถึงเรื่องที่ฉันไม่เข้าใจ ในขณะที่เห็นได้ชัดว่าโซลูชันที่สามนั้นซับซ้อนเกินไปโดยตั้งใจ แต่ฉันแทบจะไม่เชื่อเลยว่าตัววนซ้ำอีกชั้นหนึ่งจะทำให้เกิดการชะลอตัวเช่นนี้ได้ เพื่อตรวจสอบสิ่งนี้ ฉันได้เพิ่มเลเยอร์ตัววนซ้ำเดียวกันให้กับโซลูชัน vector นี่คือโซลูชันที่สี่ของฉัน เมื่อพิจารณาจากสิ่งที่แนวคิดตัววนซ้ำนี้ทำกับโซลูชัน unordered_map ของฉัน ฉันคาดว่าจะมีการชะลอตัวอย่างมากเช่นกัน แต่น่าแปลกที่สิ่งนี้ไม่ได้เกิดขึ้นเลย โซลูชันนี้ทำงานเกือบเร็วเท่ากับ vector ธรรมดาใน 0.035 วินาที

สิ่งนี้เป็นไปได้อย่างไร? อะไรเป็นสาเหตุของการชะลอตัวในแนวทางที่สาม? เป็นไปได้อย่างไรที่การแก้ปัญหาสองวิธีที่คล้ายกันมากเกินไปในลักษณะเดียวกันจะทำให้โซลูชันหนึ่งทำงานช้าลงอย่างมาก และแทบจะไม่สร้างความเสียหายให้กับอีกโซลูชันเลย เหตุใดการเพิ่มเลเยอร์ตัววนซ้ำลงในโซลูชัน unordered_map จึงทำให้ไม่เหมาะสมกับเวลา และการทำแบบเดียวกันกับโซลูชัน vector แทบจะไม่ทำให้โซลูชันช้าลงเลย

แก้ไข:

ฉันพบว่าปัญหาดูเหมือนจะชัดเจนที่สุดหากอินพุตมีบรรทัดที่ซ้ำกันหลายบรรทัด ฉันทดสอบวิธีแก้ปัญหาทั้งสี่บนเครื่องของฉันกับอินพุต 1 1000000 ซ้ำ 200 ครั้ง วิธีแก้ปัญหาด้วยเวกเตอร์ธรรมดาจะประมวลผลทั้งหมดภายใน 1.531 วินาที การแก้ปัญหาด้วยเวกเตอร์และเลเยอร์ตัววนซ้ำเพิ่มเติมใช้เวลา 3.087 วินาที การแก้ปัญหาด้วยแผนที่แบบไม่เรียงลำดับธรรมดาใช้เวลา 33.821 วินาที และวิธีแก้ปัญหาด้วยแผนที่แบบไม่เรียงลำดับและเลเยอร์ตัววนซ้ำเพิ่มเติมที่จัดการใช้เวลามากกว่า ครึ่งชั่วโมง - ฉันหยุดมันหลังจาก 31 นาที 0.482 วินาที! ฉันทดสอบบน Linux mint 17.2 64 บิต, เวอร์ชัน g++ Ubuntu 4.8.4-2ubuntu1~14.04 พร้อมแฟล็ก -std=c++11 -O2, โปรเซสเซอร์ Celeron 2955U @1.4 GHz x 2