ฟีโบนัชชีแบบเรียกตัวเองและเมโมไรเซชันใน Python
ในบทเรียนนี้ คุณจะคำนวณเลขฟีโบนัชชีแบบเรียกตัวเอง และใช้เมโมไรเซชันเพื่อไม่ต้องคำนวณผลลัพธ์ที่รู้แล้วซ้ำ
บทนำ
ปัญหาที่ต้องแก้
นิยามฟีโบนัชชีแบบเรียกซ้ำดูสวยงามแต่ช้ามาก: การหาพจน์ที่ 40 ต้องคำนวณเรื่องเล็ก ๆ เดิมซ้ำหลายร้อยล้านครั้ง memoization (การจำผลลัพธ์) แก้ปัญหานี้ได้ด้วยบรรทัดเดียว และยังสอนแนวคิดสำคัญของ dynamic programming ด้วย
ลองนึกภาพแบบนี้
memoization เหมือนนักเรียนที่จดทุกคำตอบลงสมุด ถ้ามีคนถาม fib(5) อีกครั้ง เขาไม่ต้องคิดใหม่ แค่เปิดสมุดอ่านคำตอบ ทุกคำถามจึงแก้แค่ครั้งเดียว
@cache📓 จดคำตอบไว้ในสมุดfibonacci(number - 1) + fibonacci(number - 2)🧮 แก้โดยใช้คำตอบของคำถามที่เล็กกว่าสองข้อif number < 2: return number🛑 รู้คำตอบสองข้อแรกอยู่แล้วfibonacci(10)⚡ คำตอบที่เล็กกว่าแต่ละข้อคำนวณแค่ครั้งเดียว: เร็วmemoization เก็บผลลัพธ์ของการเรียกฟังก์ชันแต่ละครั้งไว้ตามอาร์กิวเมนต์ เมื่อเรียกด้วยอาร์กิวเมนต์เดิมอีก ฟังก์ชันจึงส่งกลับผลลัพธ์ที่เก็บไว้แทนการคำนวณใหม่
ประเด็นสำคัญ
if number < 2: return numberให้สองพจน์แรก คือ 0 และ 1fibonacci(number - 1) + fibonacci(number - 2)ทำตามนิยามโดยตรง@cacheจากfunctoolsจำทุกผลลัพธ์ไว้fibonacci(k)แต่ละค่าจึงทำงานแค่ครั้งเดียว- ถ้าไม่มี
@cacheการหาfibonacci(10)ต้องเรียกฟังก์ชัน 177 ครั้ง ถ้ามีจะเหลือแค่ 11 ครั้ง
ใช้เมื่อไร?
- ฟังก์ชันแบบเรียกซ้ำที่ต้องแก้โจทย์ย่อยเดิมซ้ำ ๆ เช่น นับเส้นทางในตาราง ทอนเหรียญ ตัดคำ
- เรียนรู้แนวคิดเบื้องหลัง dynamic programming
- เร่งความเร็ว pure function (ฟังก์ชันที่ให้ผลเหมือนเดิมเสมอเมื่อได้อาร์กิวเมนต์เดิม) ที่ถูกเรียกบ่อยด้วยอาร์กิวเมนต์ซ้ำ ๆ
เมื่อไรยังไม่จำเป็น
- ฟังก์ชันที่มีผลข้างเคียง หรือให้ผลลัพธ์เปลี่ยนไปตามเวลา: แคชจะส่งกลับคำตอบเก่าที่ไม่ถูกต้องแล้ว
- recursion ที่ลึกมาก: แม้มีแคช
fib(5000)ก็อาจเกินขีดจำกัด recursion ได้ ใช้ลูปแทนจะเลี่ยงปัญหานี้
ดูการทำงาน
กด ทีละขั้น เพื่อติดตามแต่ละการเรียก สังเกตว่า fib คำนวณค่าเล็ก ๆ เดิมซ้ำแล้วซ้ำอีก นี่คือเหตุผลที่แบบธรรมดาช้า
โค้ดตัวอย่าง
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))
ผลลัพธ์จากการรัน
55
อธิบายโค้ด
เดคอเรเตอร์ @cache จะจำผลลัพธ์ของฟังก์ชันสำหรับแต่ละค่าที่รับเข้ามาโดยอัตโนมัติ เมื่อคำนวณ fibonacci(8) แล้ว การเรียกครั้งต่อ ๆ ไปจะได้ผลลัพธ์ทันที เวลาทำงานจึงลดจากแบบเอกซ์โพเนนเชียลเหลือ O(n) โดยแลกกับหน่วยความจำ O(n) สำหรับเก็บผลลัพธ์
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
recursion ที่ไม่มีแคช
โปรแกรมคำนวณค่าเดิมซ้ำแล้วซ้ำอีก และ fib(40) ใช้เวลาหลายวินาที
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- เลขฟีโบนัชชี คืนค่าเลขฟีโบนัชชีลำดับที่ n ง่าย
- นับลำดับการทอยลูกเต๋า นับจำนวนลำดับการทอยลูกเต๋าแบบมีลำดับที่ได้ผลรวมตามที่กำหนด ปานกลาง