0Pricing
DSA Interview Prep · บทเรียน

การจดจำผลลัพธ์: แคชผลลัพธ์จากการเรียกซ้ำ

ใช้ @functools.lru_cache และดิกชันนารี memo ที่สร้างเองกับฟีโบนัชชีและการปีนบันได เพื่อตัดการคำนวณซ้ำแบบเลขชี้กำลัง

การจดจำผลลัพธ์: แคชผลลัพธ์จากการเรียกซ้ำ เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

ปัญหาของการเรียกซ้ำซ้ำซ้อน

ฟีโบนัชชีแบบเรียกซ้ำอย่างตรงไปตรงมาคำนวณค่าเดิมซ้ำหลายครั้ง fib(5) เรียก fib(4) และ fib(3); fib(4) เรียก fib(3) และ fib(2) — ดังนั้น fib(3) จึงถูกคำนวณสองครั้ง ความซ้ำซ้อนนี้เพิ่มขึ้นแบบเอ็กซ์โพเนนเชียล: fib(40) ทำให้เกิดการเรียกใช้ฟังก์ชันมากกว่าหนึ่งพันล้านครั้ง การจดจำผลลัพธ์ แก้ปัญหานี้ด้วยการจัดเก็บผลลัพธ์แต่ละค่าในครั้งแรกที่คำนวณ ดังนั้นการเรียกครั้งถัดไปจะดึงค่าจากแคชในเวลา O(1) แทนที่จะคำนวณใหม่

# Count calls without memoisation
call_count = [0]

def fib_plain(n):
    call_count[0] += 1
    if n <= 1: return n
    return fib_plain(n-1) + fib_plain(n-2)

fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40

การจดจำผลลัพธ์ด้วยพจนานุกรมแบบเขียนเอง

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

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(10))   # 55
print(fib_memo(50))   # 12586269025
print(fib_memo(100))  # huge number — still fast!

ตัวตกแต่ง functools.lru_cache

ไพธอนมี @functools.lru_cache(maxsize=None) ให้ใช้ (และมีในรูป @functools.cache ตั้งแต่ไพธอน 3.9 ขึ้นไป) เพื่อทำการจดจำผลลัพธ์โดยอัตโนมัติ การเพิ่มตัวตกแต่งนี้ไว้เหนือฟังก์ชันจะเก็บแคชการเรียกใช้ทั้งหมดตามอาร์กิวเมนต์ของฟังก์ชัน maxsize=None หมายถึงแคชมีขนาดไม่จำกัด — ชุดอาร์กิวเมนต์ที่ไม่ซ้ำกันทุกชุดจะถูกเก็บแคชไว้ วิธีนี้เปลี่ยนฟังก์ชันแบบเรียกซ้ำใด ๆ ให้เป็นเวอร์ชันที่จดจำผลลัพธ์ได้ด้วยโค้ดเพียงหนึ่งบรรทัด

import functools

@functools.lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(50))   # 12586269025
print(fib(100))  # 354224848179261915075
print(fib.cache_info())  # CacheInfo(hits=..., misses=..., maxsize=None, currsize=...)

การปีนบันได (LeetCode 70)

LeetCode 70 'การปีนบันได': คุณสามารถปีนครั้งละ 1 หรือ 2 ขั้นได้ มีกี่วิธีที่จะไปถึงขั้นที่ n ปัญหานี้คือฟีโบนัชชีในรูปแบบหนึ่ง: ways(n) = ways(n-1) + ways(n-2) กรณีฐานคือ: ways(0) = 1 (มีหนึ่งวิธีในการอยู่ที่พื้นเดิม) และ ways(1) = 1 เมื่อใช้การจดจำผลลัพธ์ จะใช้เวลา O(n) และพื้นที่ O(n)

import functools

@functools.lru_cache(maxsize=None)
def climbStairs(n):
    if n <= 1:
        return 1
    return climbStairs(n-1) + climbStairs(n-2)

for i in range(1, 8):
    print(f'climbStairs({i}) = {climbStairs(i)}')
# 1,2,3,5,8,13,21

การทอนเหรียญ (LeetCode 322)

LeetCode 322 'การทอนเหรียญ': เมื่อกำหนดชนิดเหรียญและยอดเงินเป้าหมาย ให้หาจำนวนเหรียญขั้นต่ำ การเรียกซ้ำจากบนลงล่างที่จดจำผลลัพธ์ใช้ dp(amount) = 1 + min(dp(amount - coin)) สำหรับเหรียญที่ใช้ได้แต่ละชนิด กรณีฐานคือ dp(0) = 0 ให้เก็บแคชของยอดเงินย่อยแต่ละค่า หากยอดเงินย่อยใดเป็นไปไม่ได้ ให้คืนค่าอนันต์ การจดจำผลลัพธ์เปลี่ยนการลองทุกกรณีแบบเอ็กซ์โพเนนเชียลให้เป็นเวลา O(amount × len(coins))

import functools

def coinChange(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')
        return 1 + min(dp(rem - c) for c in coins)

    result = dp(amount)
    return result if result != float('inf') else -1

print(coinChange([1, 5, 11], 15))  # 3 (5+5+5)
print(coinChange([1, 2, 5], 11))   # 3 (5+5+1)
print(coinChange([2], 3))          # -1

การแบ่งคำ (LeetCode 139) พร้อมการจดจำผลลัพธ์

LeetCode 139 'การแบ่งคำ': ตรวจสอบว่าสตริงสามารถแบ่งออกเป็นคำในพจนานุกรมได้หรือไม่ การเรียกซ้ำจากบนลงล่าง: can_break(s, start) จะลองคำนำหน้าทุกแบบ s[start:end]; หากคำนั้นอยู่ในพจนานุกรมและ can_break(s, end) เป็นจริง ให้คืนค่าเป็นจริง หากไม่มีการจดจำผลลัพธ์ จะใช้เวลา O(2^n); เมื่อใช้การจดจำผลลัพธ์ (เก็บแคชของดัชนีเริ่มต้นแต่ละค่า) จะกลายเป็น O(n² × L) โดย L คือความยาวคำสูงสุด

import functools

def wordBreak(s, wordDict):
    word_set = set(wordDict)

    @functools.lru_cache(maxsize=None)
    def can_break(start):
        if start == len(s):
            return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and can_break(end):
                return True
        return False

    return can_break(0)

print(wordBreak('leetcode', ['leet', 'code']))    # True
print(wordBreak('applepenapple', ['apple','pen'])) # True
print(wordBreak('catsandog', ['cats','dog','sand','and','cat']))  # False

การจดจำผลลัพธ์เทียบกับการสร้างตาราง

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

# Memoisation (top-down)
import functools
@functools.lru_cache(maxsize=None)
def fib_td(n):
    if n <= 1: return n
    return fib_td(n-1) + fib_td(n-2)

# Tabulation (bottom-up)
def fib_bu(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_td(20), fib_bu(20))   # 6765 6765
# Both O(n) time; fib_bu avoids recursion limit

การเพิ่มประสิทธิภาพพื้นที่: ตัวแปรแบบเลื่อนค่า

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

# Fibonacci with O(1) space
def fib_o1(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

for i in range(8):
    print(f'fib({i})={fib_o1(i)}', end='  ')
print()

# Climbing stairs O(1) space
def climbStairs_o1(n):
    if n <= 1: return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
print(climbStairs_o1(10))  # 89

lru_cache เทียบกับฟังก์ชันปิดเทียบกับพจนานุกรมส่วนกลาง

มีสามวิธีในการทำการจดจำผลลัพธ์ด้วยตนเอง พจนานุกรมส่วนกลางเรียบง่าย แต่ทำให้ขอบเขตของมอดูลมีข้อมูลปะปน ฟังก์ชันปิดจะเก็บแคชไว้ภายในฟังก์ชัน ป้องกันการรั่วไหล แต่ต้องใช้ตัวห่อหุ้ม @lru_cache เป็นวิธีที่สะอาดที่สุด — ตัวตกแต่งหนึ่งตัวแทนที่โค้ดโครงทั้งหมดได้ ในบริบทการสัมภาษณ์ ให้เริ่มด้วย @lru_cache เว้นแต่ผู้สัมภาษณ์จะขอให้เขียนการทำงานด้วยตนเองโดยเฉพาะ

import functools

# 1. Global dict (messy)
memo_global = {}
def fib_global(n):
    if n in memo_global: return memo_global[n]
    if n <= 1: return n
    memo_global[n] = fib_global(n-1) + fib_global(n-2)
    return memo_global[n]

# 2. Closure (cleaner scope)
def make_fib():
    cache = {}
    def fib(n):
        if n in cache: return cache[n]
        if n <= 1: return n
        cache[n] = fib(n-1) + fib(n-2)
        return cache[n]
    return fib
fib_closure = make_fib()

# 3. lru_cache (best)
@functools.lru_cache(maxsize=None)
def fib_cached(n):
    if n <= 1: return n
    return fib_cached(n-1) + fib_cached(n-2)

print(fib_global(30), fib_closure(30), fib_cached(30))  # all 832040

เมื่อการจดจำผลลัพธ์ไม่ช่วย

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

# Memoisation DOES help: overlapping sub-problems (Fibonacci)
# fib(n) reuses fib(n-2), fib(n-3), etc.

# Memoisation does NOT help: distinct sub-problems (permutations)
# Each unique (remaining_elements, target) pair is truly distinct
# The exponential complexity comes from the state space itself

print('Memoisation: useful when SAME sub-problem recurs multiple times')
print('Not useful: when every sub-problem is unique to one recursive path')

สรุป: รายการตรวจสอบการจดจำผลลัพธ์

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

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้

ทบทวนบทเรียน

ในบทเรียนนี้ คุณได้เรียนรู้ว่า: การจดจำผลลัพธ์จะจัดเก็บผลลัพธ์ของปัญหาย่อยเพื่อหลีกเลี่ยงการคำนวณซ้ำ ทำให้การเรียกซ้ำแบบเอ็กซ์โพเนนเชียลกลายเป็นเวลาแบบพหุนาม, @functools.lru_cache เป็นเครื่องมือไพธอนตามแบบแผนที่ใช้เพียงหนึ่งบรรทัด และ การจดจำผลลัพธ์ (จากบนลงล่าง) กับการสร้างตาราง (จากล่างขึ้นบน) เป็นสองรูปแบบของ DP — การจดจำผลลัพธ์ต่อยอดได้ง่ายกว่า ส่วนการสร้างตารางหลีกเลี่ยงปัญหาความลึกของสแตก ขอแสดงความยินดี — คุณเรียนจบโมดูลการเรียกซ้ำและตารางแฮชแล้ว

คำถามที่พบบ่อย

บทเรียน “การจดจำผลลัพธ์: แคชผลลัพธ์จากการเรียกซ้ำ” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “การจดจำผลลัพธ์: แคชผลลัพธ์จากการเรียกซ้ำ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “การจดจำผลลัพธ์: แคชผลลัพธ์จากการเรียกซ้ำ”

ใช้ @functools.lru_cache และดิกชันนารี memo ที่สร้างเองกับฟีโบนัชชีและการปีนบันได เพื่อตัดการคำนวณซ้ำแบบเลขชี้กำลัง คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน

บทเรียน “การจดจำผลลัพธ์: แคชผลลัพธ์จากการเรียกซ้ำ” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม

ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. กรอบการเรียกซ้ำ: กรณีฐาน ความเชื่อมั่น การสร้าง
  2. การแสดงภาพสแตกการเรียก
  3. การแลกเปลี่ยนระหว่างแบบเรียกซ้ำกับแบบวนซ้ำ
  4. การจดจำผลลัพธ์: แคชผลลัพธ์จากการเรียกซ้ำ
← กลับไปที่ DSA Interview Prep