อัลกอริทึม Python

ฟีโบนัชชีแบบเรียกตัวเองและเมโมไรเซชันใน Python

ในบทเรียนนี้ คุณจะคำนวณเลขฟีโบนัชชีแบบเรียกตัวเอง และใช้เมโมไรเซชันเพื่อไม่ต้องคำนวณผลลัพธ์ที่รู้แล้วซ้ำ

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

นิยามฟีโบนัชชีแบบเรียกซ้ำดูสวยงามแต่ช้ามาก: การหาพจน์ที่ 40 ต้องคำนวณเรื่องเล็ก ๆ เดิมซ้ำหลายร้อยล้านครั้ง memoization (การจำผลลัพธ์) แก้ปัญหานี้ได้ด้วยบรรทัดเดียว และยังสอนแนวคิดสำคัญของ dynamic programming ด้วย

ลองนึกภาพแบบนี้

memoization เหมือนนักเรียนที่จดทุกคำตอบลงสมุด ถ้ามีคนถาม fib(5) อีกครั้ง เขาไม่ต้องคิดใหม่ แค่เปิดสมุดอ่านคำตอบ ทุกคำถามจึงแก้แค่ครั้งเดียว

จากสมุดจดสู่โค้ด
@cache📓 จดคำตอบไว้ในสมุด
fibonacci(number - 1) + fibonacci(number - 2)🧮 แก้โดยใช้คำตอบของคำถามที่เล็กกว่าสองข้อ
if number < 2: return number🛑 รู้คำตอบสองข้อแรกอยู่แล้ว
fibonacci(10)⚡ คำตอบที่เล็กกว่าแต่ละข้อคำนวณแค่ครั้งเดียว: เร็ว
เก็บผลลัพธ์ไว้ตั้งแต่ครั้งแรก แล้วนำกลับมาใช้ซ้ำ
สรุปในประโยคเดียว

memoization เก็บผลลัพธ์ของการเรียกฟังก์ชันแต่ละครั้งไว้ตามอาร์กิวเมนต์ เมื่อเรียกด้วยอาร์กิวเมนต์เดิมอีก ฟังก์ชันจึงส่งกลับผลลัพธ์ที่เก็บไว้แทนการคำนวณใหม่

ประเด็นสำคัญ

  1. if number < 2: return number ให้สองพจน์แรก คือ 0 และ 1
  2. fibonacci(number - 1) + fibonacci(number - 2) ทำตามนิยามโดยตรง
  3. @cache จาก functools จำทุกผลลัพธ์ไว้ fibonacci(k) แต่ละค่าจึงทำงานแค่ครั้งเดียว
  4. ถ้าไม่มี @cache การหา fibonacci(10) ต้องเรียกฟังก์ชัน 177 ครั้ง ถ้ามีจะเหลือแค่ 11 ครั้ง

ใช้เมื่อไร?

  • ฟังก์ชันแบบเรียกซ้ำที่ต้องแก้โจทย์ย่อยเดิมซ้ำ ๆ เช่น นับเส้นทางในตาราง ทอนเหรียญ ตัดคำ
  • เรียนรู้แนวคิดเบื้องหลัง dynamic programming
  • เร่งความเร็ว pure function (ฟังก์ชันที่ให้ผลเหมือนเดิมเสมอเมื่อได้อาร์กิวเมนต์เดิม) ที่ถูกเรียกบ่อยด้วยอาร์กิวเมนต์ซ้ำ ๆ

เมื่อไรยังไม่จำเป็น

  • ฟังก์ชันที่มีผลข้างเคียง หรือให้ผลลัพธ์เปลี่ยนไปตามเวลา: แคชจะส่งกลับคำตอบเก่าที่ไม่ถูกต้องแล้ว
  • recursion ที่ลึกมาก: แม้มีแคช fib(5000) ก็อาจเกินขีดจำกัด recursion ได้ ใช้ลูปแทนจะเลี่ยงปัญหานี้

ดูการทำงาน

กด ทีละขั้น เพื่อติดตามแต่ละการเรียก สังเกตว่า fib คำนวณค่าเล็ก ๆ เดิมซ้ำแล้วซ้ำอีก นี่คือเหตุผลที่แบบธรรมดาช้า

โค้ดตัวอย่าง

รันโค้ด →
main.py
from functools import cache

@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

print(fibonacci(10))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

55

อธิบายโค้ด

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

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

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)

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ถัดไป: โครงสร้างข้อมูลสแตก (stack) ใน Python →

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด