PAtS.Computainment

สวัสดีครับ
จำเรื่องที่แล้วได้ไหม? ที่พูดถึงเลข fibonacci เอาไว้ และก็ทิ้งโค้ดไว้สามชุด

คราวนี้ เรามาดูกันดีกว่า ว่าโค้ดทั้งสามชุดนั้นมันเป็นยังไงกันบ้าง
ก่อนอ่าน ลองนึกๆ ดูเล่นๆ กันก่อนนะว่า อันไหนคำนวณยังไง ใช้หน่วยความจำอย่างไร

อ่ะ... อันแรก (เอาโค้ดมาเป็นรูป มีสีๆ ด้วย.. อยากได้เป็นข้อความไปดูในเอ็นทรีเก่านะครับ)


วิธีนี้ ใช้เทคนิคที่เรียกว่า recursive function หรือฟังก์ชันเรียกตัวเอง
การเขียนแบบนี้ ก็ตามนิยามของมันเลยครับ ซึ่งก็เป็นข้อดีของมัน คือ อ่านเข้าใจง่าย เขียนง่าย
แต่ มันก็มีข้อเสียครับ ลองดูรูปข้างล่างนี้ เป็นตัวอย่างการหาเลข F₅



จะเห็นว่า มันมีการเรียกฟังก์ชันอย่างซ้ำซ้อน และเยอะแยะมาก ทำให้คำนวณผลลัพธ์ออกมาช้ามาก
โดยเวลาที่ใช้ในวิธีนี้จะเติบโตแบบ exponential หรือ O(2ⁿ)
ซึ่งก็หมายความว่า ยิ่งหาตัวเลขทีอันดับมากๆ ยิ่งใช้เวลาเป็นเท่าตัว (เช่น F₅ ใช้เวลา X เท่าของ F₄)

ส่วนเรื่องหน่วยความจำที่ใช้ ดูเผินๆ จะใช้น้อย เพราะไม่มีตัวแปรในฟังก์ชันเลย
แต่จริงๆ n ก็เป็นตัวแปรนะ และการเรียกฟังก์ชันซ้ำแต่ละครั้ง
ก็ต้องใช้หน่วยความจำในการเก็บสถานะของการเรียกอีกด้วย ซึ่งถ้าสังเกตดู จะเห็นว่าจำนวนชั้นที่ลึกที่สุดของการเรียกฟังก์ชัน จะแปรตาม n แบบเชิงเส้น หรือ O(n)
ซึ่งก็คือ n ยิ่งมาก ก็ต้องใช้หน่วยความจำมากขึ้น เพื่อจัดเก็บสถานะในการเรียกฟังก์ชัน

วิธีการคิดแบบนี้นี้ มีชื่อเรียกเฉพาะว่า Tree Recursion

ถัดมา อันที่สอง


วิธีนี้ ใช้สิ่งที่เรียกว่า Lookup table (คือหาผลลัพธ์ใช้ตารางที่เก็บผลลัพธ์ที่คำนวณไว้เรียบร้อยแล้ว)
ซึ่งจะเห็นว่า การคำนวณจะถูกทำครั้งแรกที่ฟังก์ชันถูกเรียกเพียงครั้งเดียว (ถือเป็น initialization)
หลังจากนั้น ก็เอาค่าที่คำนวณไว้แล้ว มาตอบเลย


[ ภาพ: วิธีการคำนวณเพื่อทำตาราง โดยคำนวณเชิงเส้นไปเรื่อยๆ ]

ด้วยเทคนิคนี้ จึงทำให้วิธีนี้ ใช้เวลาในการคำนวณคำตอบคงที่ตลอด (ไม่นับขั้นเริ่มต้น)
นั่นก็คือ O(1) นั่นเองซึ่งก็ถือว่าเป็น order ที่เร็วที่สุด
แต่นั่น ก็ต้องแลกด้วยการใช้หน่วยความจำในการเก็บตาราง ซึ่งก็ใช้เป็น O(n)

สุดท้าย


วิธีนี้ คำนวณโดยใช้ Circular buffer เข้ามาช่วย ทำให้ใช้หน่วยความจำน้อยมาก และเป็นค่าคงที่
ซึ่งก็คือ ใช้หน่วยความจำเป็น O(1)

แต่ทุกๆ ครั้งของการเรียกฟังก์ชัน ก็ยังต้องมีการคำนวณผลใหม่ทุกครั้ง จึงทำให้การใช้เวลายังคงเป็น O(n) อยู่


ภาพ: circular buffer ที่ใช้ในตัวอย่างนี้ จะเห็นว่า ตำแหน่งที่เก็บจะวนไปเรื่อยๆ
ถ้าดูในโค้ด ก็จะเห็นว่า ผมใช้วิธีการบวก แทนลบ คือ X + 1 แทนที่จะเป็น X - 2
เพื่อหลีกเลี่ยงปัญหาเลขติดลบ ซึ่งอาจเกิดปัญหาในการ mod ขึ้นได้

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

แล้ว B มันเร็วกว่า C เสมอมั๊ย? ก็ไม่อีกนั่นแหละ
ลองคิดดูว่า ถ้าเราเรียกครั้งเดียว หา F₅ ถ้าแบบ B มันต้องคำนวณไปถึง F₄₀ ก่อน
แต่ถ้า เราเรียกซักร้อยรอบล่ะ อันนี้แบบ B ก็ควรจะเร็วกว่าแน่ๆ
ก็เหมือนกับ ระบบแคช ที่ต้องดู hit rate และผลของมัน ว่าคุ้มค่าแค่ไหน

ส่วนแบบ A นั่น ก็ใช่ว่ามันจะไม่มีประโยชน์ อย่างน้อยมันก็เข้าใจได้ง่ายหล่ะน่า
นอกจากนี้ เรายังสามารถทำอะไรคล้ายๆ กันนี้ แต่ไม่จำเป็นต้องทำการเรียกตัวเองได้ด้วย
ลองไปดูตัวอย่างโค้ด directory traversal ใน เอ็นทรีี้นี้ดูนะครับ
จะเห็นว่ามันเป็นวิธีการท่องไปตามต้นไม้แบบ DFS นั่นเอง ซึ่งสามารถเขียนแบบเรียกตัวเองได้อย่างง่ายๆ
และก็สามารถเลี่ยงโดยใช้ list/stack เข้ามาแทน (ลองดูในโค้ดผม หรือในวิกิก็ได้)


สุดท้าย.. ของแถม



ปล. มีคนตั้งข้อสังเกตเรื่องการยกตัวอย่างการหา fac ...
เรื่องของเรื่องที่ผมใช้ fibo ก็เพราะมันเห็นความแตกต่างชัดหน่อยครับ เพราะ มันไปเรียกซ้ำสองรอบแหนะ ;)

ปล2. มีอะไรผิดก็ติติงได้นะครับ ไม่ได้ใช้พวกนี้มานาน นานๆ เอามารื้อฝื้นหน่อย กันลืม