ไดนามิกโปรแกรมมิงไม่ใช่เวทมนตร์ดำ

 (qsantos.fr)
2 คะแนน โดย GN⁺ 2024-01-15 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • แม้แต่ปัญหาที่มีกรณีพิเศษจำนวนมากอย่าง Advent of Code 2023 Day 12 ก็ยังจัดการด้วย ไดนามิกโปรแกรมมิง ได้ หากมองเห็นโครงสร้างที่ต้องแก้ปัญหาย่อยเดิมซ้ำ ๆ
  • แก่นสำคัญคือแยกปัญหาด้วยรีเคอร์ชันก่อน จากนั้นลดการคำนวณซ้ำด้วย เมโมอิซชัน และค่อยแปลงเป็นการคำนวณแบบวนซ้ำที่เติมค่าตามลำดับของการพึ่งพา
  • ตัวอย่าง Fibonacci แสดงให้เห็นว่ารีเคอร์ชันแบบตรงไปตรงมาจะประเมิน f(1) ซ้ำหลายครั้ง แต่ถ้าใช้แคช จะต้องประเมินเพียง ค่า n + 1 ค่า ตั้งแต่ f(0) ถึง f(n) เท่านั้น
  • Levenshtein distance และ Advent of Code Day 12 แสดงกระบวนการเปลี่ยนการเรียกรีเคอร์ชันให้เป็นการเติมอาร์เรย์ โดยใช้ ดัชนีสถานะ เช่น ความยาวสตริงหรือดัชนีกฎเป็นคีย์ของแคช
  • เมื่อเข้าใจไดนามิกโปรแกรมมิงแล้ว ไม่เพียงแต่ประสิทธิภาพจะดีขึ้น แต่ยังมองเห็น สถานะระหว่างทางและความสัมพันธ์การพึ่งพา ของอัลกอริทึม และหาโอกาสปรับแต่งหน่วยความจำได้ง่ายขึ้น

ชื่ออาจชวนสับสน แต่แนวคิดเรียบง่าย

  • ชื่อ “dynamic programming” ไม่ได้เกี่ยวโดยตรงกับความหมายแบบสมัยใหม่ของ “สไตล์การเขียนโปรแกรม” หรือ “ชนิดข้อมูลแบบไดนามิก”
  • แก่นของมันคือแนวทางออกแบบอัลกอริทึมที่แบ่งปัญหาออกเป็นปัญหาย่อยที่คล้ายกัน และนำผลลัพธ์กลับมาใช้ซ้ำ
  • มีหมายเหตุจากบรรณาธิการเพิ่มเติมว่า หากมองตามความหมายเชิงประวัติศาสตร์ของคำว่า “programming” ชื่อนี้ก็พอสมเหตุสมผล
  • จุดเริ่มต้นมักเป็นรูปแบบที่แยกปัญหาออกเป็นปัญหาเล็กลง เช่น ฟังก์ชันรีเคอร์ซีฟ
  • เมื่อปัญหาย่อยเดิมปรากฏซ้ำหลายครั้ง ก็ย่อมต้องมี การแคช เพื่อเก็บผลลัพธ์ไว้ใช้ซ้ำอย่างเป็นธรรมชาติ

มองการแคชและการแปลงเป็นวนซ้ำผ่าน Fibonacci

  • ฟังก์ชัน Fibonacci นิยามเป็น f(n) = f(n - 1) + f(n - 2) และการเขียนแบบรีเคอร์ชันตรงไปตรงมาจะคำนวณค่าเดิมซ้ำไปมา
  • f(1) เป็นค่าที่ถูกนำไปบวกในผลลัพธ์จริง ดังนั้นเมื่อ f(n) โตขึ้น จำนวนครั้งที่รีเคอร์ชันแบบตรงไปตรงมาประเมินค่าก็เพิ่มขึ้นอย่างรวดเร็ว
  • หากแคชผลลัพธ์หรือใช้เมโมอิซชัน ก็ไม่จำเป็นต้องคำนวณ f(4), f(3), f(2) ที่เคยคำนวณแล้วอีก
  • วิธีนี้จะประเมินเพียง 7 ค่า ตั้งแต่ f(0) ถึง f(6) และในกรณีทั่วไปจะลดลงเหลือเพียง n + 1 ครั้ง
  • หากก้าวต่อไปอีกขั้น แล้วเติมค่าที่ต้องใช้ตามลำดับตั้งแต่ f(0), f(1) เป็นต้นไป ก็จะไม่ต้องมีการเรียกรีเคอร์ชันอีก
    • F[2] = F[1] + F[0]
    • F[3] = F[2] + F[1]
    • และคำนวณต่อแบบเดียวกันจนได้ F[6] = 8
  • สำหรับ Fibonacci ไม่จำเป็นต้องเก็บทั้งอาร์เรย์ แค่เก็บ ค่าก่อนหน้าและค่าก่อนหน้านั้น สองค่าก็พอ
  • ลำดับขั้นนี้แสดงเส้นทางอย่างเป็นระบบจากนิยามทางคณิตศาสตร์ไปสู่การเขียนแบบวนซ้ำ

ขยายไปยังตัวอย่าง edit distance

  • edit distance ของสองสตริงคือจำนวนครั้งแก้ไขน้อยที่สุดที่ต้องใช้เพื่อเปลี่ยนสตริงหนึ่งให้เป็นอีกสตริงหนึ่ง
  • ปัญหาจะต่างกันไปตามชนิดของการแก้ไขที่อนุญาต
    • ถ้าอนุญาตเฉพาะการแทนที่อักขระ จะเป็น Hamming distance
    • ถ้าอนุญาตการแทรกและการลบด้วย จะเป็น Levenshtein distance
  • Levenshtein distance สามารถแบ่งเป็นปัญหาเล็กลงได้โดยอิงจากอักขระตัวสุดท้ายของสตริง A, B
    • ถ้าอักขระสุดท้ายเหมือนกัน ก็ละสองตัวนั้นออกแล้วใช้ระยะของสตริงที่เหลือ
    • ถ้าอักขระสุดท้ายต่างกัน ก็เลือกต้นทุนต่ำสุดจากการแทนที่ การลบ หรือการแทรก
    • ถ้า A ว่าง ก็ต้องแทรกอักขระทั้งหมดของ B ดังนั้นต้นทุนคือ b
    • ถ้า B ว่าง ก็ต้องลบอักขระทั้งหมดของ A ดังนั้นต้นทุนคือ a
  • หากยกนิยามนี้ไปเขียนเป็นรีเคอร์ชันใน Python ตรง ๆ จะช้ามากเมื่อเจอสตริงยาวหรือสตริงที่ต่างกันมาก
  • ถ้า Fibonacci แตกเป็นประมาณสองกิ่งในแต่ละชั้นของ call tree รีเคอร์ชันนี้ก็อาจแตกเป็น สามกิ่ง ได้ตามกรณี
  • เมื่อติด functools.cache ของ Python ก็จะนำผลคำนวณของชุดสตริงย่อยเดิมกลับมาใช้ซ้ำได้
  • การเขียนที่ดีกว่าคือไม่สร้างสตริงใหม่ตลอดเวลา แต่ส่งสตริงต้นฉบับ A, B พร้อมความยาวสตริงย่อย a, b เข้าไปแทน
  • ในขั้นสุดท้ายสามารถสร้างอาร์เรย์ cache แบบ 2 มิติขึ้นมาเอง แล้วเติมค่าตามลำดับให้ cache[a][b] = levenstein(A[:a], B[:b])
  • เวอร์ชันแบบวนซ้ำจะไล่ a และ b ตั้งแต่ 0 ถึงความยาวสตริง โดยอ้างอิงค่าจากแถวก่อนหน้าและคอลัมน์ก่อนหน้าที่ถูกเติมไว้แล้ว

นำไปใช้กับ Advent of Code 2023 Day 12

  • โจทย์ Advent of Code วันที่ 12 ธันวาคม 2023 เป็นปัญหาแก้ nonogram แบบ 1 มิติ
  • อินพุตตัวอย่างอยู่ในรูป .??..??...?##. 1,1,3 โดย ? สามารถเป็น . หรือ # ก็ได้
  • วิธี brute force ใช้ backtracking แต่ถ้ามีเครื่องหมายคำถาม n ตัว ก็ต้องประเมินผู้สมัคร 2^n แบบ ทำให้ขยายแบบเอ็กซ์โพเนนเชียล
  • โครงสร้างของปัญหาย่อยซ้ำเริ่มปรากฏให้เห็น
    • ..#..??...?##. (1),1,3
    • .#...??...?##. (1),1,3
    • ถ้าตัดส่วนต้นที่ประมวลผลแล้วทิ้งไป ก็จะเหลือปัญหาที่แทบเหมือนกัน เช่น .??...?##. 1,3, ..??...?##. 1,3
  • ฟังก์ชัน backtracking พื้นฐานจะรับ conditions และ rules แล้วคำนวณจำนวนรูปแบบการจัดวางที่เป็นไปได้
    • ถ้าไม่มีกฎเหลืออยู่ ก็ตรวจว่ามี # อยู่ในเงื่อนไขที่เหลือหรือไม่
    • ถ้าไม่เหลือเงื่อนไข ก็ตรวจว่ายังมีกฎเหลืออยู่หรือไม่
    • ถ้าอักขระปัจจุบันเป็น . หรือ ? ก็ข้ามไปหนึ่งช่องแล้วคำนวณต่อ
    • ถ้าอักขระปัจจุบันเป็น # หรือ ? ก็ตรวจขนาดกฎถัดไปและเงื่อนไขตัวคั่น ก่อนย้ายไปยังสถานะถัดไป
  • ใน Python เพียงใส่ @cache ก็สามารถใช้เมโมอิซชันได้แล้ว
  • หากจะแปลงเป็นไดนามิกโปรแกรมมิง ก็ไม่ควรส่งสตริงและกฎที่ถูกตัดแล้วต่อ ๆ กัน แต่ใช้ offset ของสตริง i และ offset ของกฎ j เป็นสถานะแทน
  • จากนั้นสร้าง cache[i][j] ขึ้นมาเอง และแทนที่รีเคอร์ชันด้วยการคำนวณแบบวนซ้ำโดย เติมดัชนีย้อนกลับ
  • ตัวอย่างการเขียนด้วย Rust มีให้ในลิงก์ Rust implementation ภายในบทความ

สิ่งที่มองเห็นเมื่อเติมแคชด้วยตัวเอง

  • เวอร์ชันไดนามิกโปรแกรมมิงของ Advent of Code Day 12 อาจดูช้ากว่าเวอร์ชันเมโมอิซชัน
  • ความต่างนี้อาจเป็นเพราะตัวเขียน Python ยังไม่ได้ปรับให้เหมาะสม
  • การสร้างแคชด้วยตัวเองทำให้เห็นชัดขึ้นว่าค่าใดจำเป็นต้องใช้จริง
  • สำหรับปัญหา Day 12 เวอร์ชันไดนามิกโปรแกรมมิงช่วยให้เห็นว่า ต้องใช้แค่คอลัมน์ก่อนหน้า เท่านั้น
  • ดังนั้นอาร์เรย์ 2 มิติจึงสามารถเปลี่ยนเป็นอาร์เรย์ 1 มิติ 2 ชุดที่แทนคอลัมน์ก่อนหน้าและคอลัมน์ปัจจุบันได้

ปัญหาสำหรับฝึกฝนและบทสรุป

  • ไดนามิกโปรแกรมมิงไม่ใช่เรื่องง่าย ๆ แต่ก็ไม่ใช่เทคนิคที่โปรแกรมเมอร์ส่วนใหญ่เข้าถึงไม่ได้
  • หากเข้าใจวิธีแบ่งปัญหาเป็นปัญหาย่อย ก็สามารถทำให้การเขียนแบบตรงไปตรงมาดีขึ้นได้มากในหลายสถานการณ์ แม้เพียงใช้เมโมอิซชัน
  • เมื่อชำนาญขึ้น ก็จะเข้าใจตระกูลหนึ่งของอัลกอริทึม มองเห็น trade-off ได้ดีขึ้น และหาการปรับแต่งเพิ่มเติมได้
  • มีการเสนอปัญหาต่อไปนี้ไว้สำหรับฝึกฝน
  • หลังจากลงมือเขียนแล้ว ก็อย่าลืมทำ benchmark และ profiling

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-01-15
ความเห็นจาก Hacker News

  • ชอบที่บทความชี้ให้เห็นว่าอัลกอริทึม dynamic programming เป็นเพียงวิธีอันชาญฉลาดในการแคช recursion จากประสบการณ์ของผม การหา วิธีแก้แบบ recursion ให้เจอก่อนคือจุดเริ่มต้นที่ดีที่สุดในการหาแนวทาง dynamic programming และพอหาเจอแล้ว memoization ก็ทำได้ง่ายและช่วยเพิ่มความเร็วได้มาก
    บางครั้งยังเร็วกว่า dynamic programming แบบ bottom-up ด้วย เพราะคำนวณเฉพาะคำตอบที่จำเป็นจริง ๆ ประเด็นสำคัญคือ ถึงจะมี subproblem จำนวนมากใน call tree ก็ไม่เป็นไร แต่จำนวน subproblem ที่แตกต่างกัน ควรมีไม่มากนักนัก ไม่มีเหตุผลต้องแคชผลลัพธ์ที่ใช้แค่ครั้งเดียว และความยากอยู่ที่การแยกปัญหาต้นฉบับออกเป็น subproblem ที่แตกต่างกันจำนวนน้อยพอ

    • ประเด็นที่ว่าจำนวน subproblem ที่แตกต่างกันควรมีไม่มากนั้นคือหัวใจสำคัญ ส่วนที่ว่าอัลกอริทึมโดยรวมเป็น แบบ recursion หรือแบบ iteration เป็นเรื่องรอง และ dynamic programming มักเผยตัวออกมาในอัลกอริทึมแบบ recursion บ่อยกว่า
    • คำอธิบายว่า “dynamic programming คือวิธีแคช recursion” เป็นจุดที่ทำให้ผมเข้าใจได้แบบกระจ่าง ตอนเรียนมหาวิทยาลัย น่าจะเพราะตอนนั้น procedural programming เป็นกระแสหลัก ตัวอย่าง การเติมตารางแบบ bottom-up ในตำราจึงดูเหมือนเวทมนตร์
      ในทางปฏิบัติ การตัด tail call ออกไม่ได้เกิดขึ้นเสมอไป การทำแบบนั้นจึงมีเหตุผล แต่ก็ยังรู้สึกว่า ถ้าได้เรียนผ่านมุมมอง recursion แบบ top-down พร้อมแคชซึ่งเข้าใจง่ายกว่าก่อน ก็น่าจะดีกว่า
    • ตอนเรียนครั้งแรก ผมรู้สึกว่าถ้ามันเป็นเทคนิคหรูขนาดนี้ ก็น่าจะเรียกว่า array memoization หรือ call stack memoization มากกว่า ชื่อ “dynamic programming” น่าจะเก็บไว้ใช้กับอะไรที่ดีกว่านี้
    • ผมมองว่าการมอง dynamic programming ว่าเป็นแค่ recursion ที่ใส่ memoization เป็นความเข้าใจผิดที่แพร่หลาย ถ้าเรียนแบบนั้น จะเข้าใจปัญหา dynamic programming แบบ เติมอาร์เรย์สองมิติ ได้ยากมาก
      ตัวอย่างเช่นซีรีส์ LeetCode “Best Time to Buy and Sell Stock” อย่างปัญหา https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... ดูเป็นโจทย์ที่วิธีเติมอาร์เรย์เป็นธรรมชาติกว่ามาก ผมไม่เคยลองแก้ด้วย recursion และก็ไม่แน่ใจด้วยว่ามีวิธี recursion ที่เป็นธรรมชาติหรือไม่
      ลิงก์ด้านบนเป็นข้อ III แต่สำหรับคนที่เพิ่งเริ่ม ลองเริ่มจากข้อแรก https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... จะเหมาะสำหรับเริ่มต้นกับ dynamic programming
    • การบอกว่า “dynamic programming ก็แค่ caching/memoization” คล้ายกับการบอกว่า “การลงทุนก็แค่ซื้อของแล้วค่อยขายทีหลัง” มันอาจจะถูกในเชิงเทคนิคระดับหนึ่ง แต่ก็พลาด ความซับซ้อนและความยาก ของหัวข้อนี้ไปมาก จนฟังดูขำมากกว่าจะให้ความเข้าใจ

  • ที่มาของชื่อ “dynamic programming” มาจากผู้คิดค้นคือ Richard Bellman ในปี 1950 ที่ RAND เขากำลังหาชื่อสำหรับกระบวนการตัดสินใจหลายขั้นตอน โดยตอนนั้นรัฐมนตรีกลาโหม Wilson เกลียดคำว่า “research” แบบเข้าขั้น และยิ่งต้องหลีกเลี่ยงคำว่า “mathematics” มากกว่าเดิม
    Bellman ต้องการชื่อที่ใช้ปกปิดจาก Wilson และกองทัพอากาศว่า ที่ RAND กำลังทำคณิตศาสตร์กันอยู่จริง ๆ ดังนั้นแม้หัวข้อนี้จะเกี่ยวกับ planning, decision-making และ thinking แต่คำว่า “planning” ก็ไม่เหมาะด้วยหลายเหตุผล เขาเลยเลือก “programming” และเพื่อสื่อแนวคิดเรื่องหลายขั้นตอนกับการเปลี่ยนแปลงตามเวลา จึงเติมคำว่า “dynamic” ซึ่งมีความหมายที่ชัดเจนในฟิสิกส์คลาสสิกลงไป
    เขายังชอบที่คำว่า “dynamic” ในฐานะคำคุณศัพท์นำไปใช้ในความหมายลบได้ยาก และยังเป็นชื่อที่สมาชิกสภาก็คงคัดค้านได้ยากด้วย จึงใช้ dynamic programming เป็นชื่อครอบคลุมกิจกรรมของตน
    ที่มา: https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...

  • ผมชอบที่บทความนี้เริ่มจากการ แสดงปัญหาในรูปแบบ recursion ก่อน แล้วค่อย ๆ เพิ่มการแคชเข้าไป และสุดท้ายจึงลดขนาดแคชให้เหลือเท่าที่จำเป็น
    ผมเองมักพยายามพุ่งตรงไปที่วิธีแก้แบบ dynamic programming แล้วก็ติด หรือไม่ก็ฝืนอย่างมากเพื่อให้มันทำงานได้ ต่อไปผมคิดว่าจะบังคับตัวเองให้ทำตามลำดับขั้น

    • จากประสบการณ์ของผม ถ้าสอน dynamic programming แบบตัดเข้าประเด็นเลย มันจะให้ความรู้สึกเหมือนปริศนา แต่ถ้าอธิบายเป็นลำดับขั้นว่าทำไมต้องใช้ตาราง และเชื่อมแนวคิดนั้นเข้ากับ caching คนจะเข้าใจได้ดีกว่ามาก

  • หนึ่งในการประยุกต์ใช้ dynamic programming ที่ยอดเยี่ยมคือ การจัดแนวลำดับนิวคลีโอไทด์/โปรตีนแบบเป็นคู่
    https://en.wikipedia.org/wiki/Sequence_alignment
    https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor...
    https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...

    • ผมมองว่านี่เป็นอัลกอริทึมที่สำคัญที่สุดบางส่วนใน ชีวสารสนเทศศาสตร์/ชีววิทยา และขอบเขตการใช้งานก็กว้างมาก

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

    • ตัวเลือกที่เป็นไปได้คือ ลำดับฟีโบนักชี, ปัญหาการทอนเหรียญ, ปัญหากระเป๋าเป้ แบบ 0/1, การคูณลูกโซ่เมทริกซ์, ลำดับย่อยร่วมยาวที่สุด, ลำดับย่อยเพิ่มขึ้นยาวที่สุด, ปัญหาเส้นทางสั้นที่สุดอย่าง Floyd-Warshall, และระยะแก้ไข (Levenshtein distance)
      ทั้งหมดเป็นตัวอย่างคลาสสิกที่วิธีแก้แบบไร้เดียงสาไม่มีประสิทธิภาพ และดีขึ้นได้มากด้วยการเขียนโปรแกรมเชิงพลวัต
    • ในบทความเองก็ยกไว้หลายอย่าง และเป็นปัญหาที่เห็นกันบ่อยในเลกเชอร์หรือแบบฝึกหัด เช่น ลำดับย่อยร่วมยาวที่สุด, สตริงย่อยร่วมยาวที่สุด, line warp, subset sum, partition, และปัญหากระเป๋าเป้
      ดูตัวอย่างเพิ่มเติมได้ที่ https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms...
    • นอกจากปัญหาที่คนอื่นยกมาแล้ว อาจเป็น ปัญหาการจัดตารางเวลา ก็ได้ เช่น ปัญหาที่มีอีเวนต์ N รายการซึ่งทับซ้อนกันตามเวลา แล้วต้องหาวิธีจัดตารางเรียนหรือ CPU process ให้เหมาะที่สุดตามเกณฑ์อย่าง throughput
      ถ้าเพิ่มข้อจำกัดพิเศษอย่าง “สองวิชานี้ต้องเรียนคู่กัน” ก็เข้าใจว่ามันจะซับซ้อนและจัดการยากกว่าการเขียนโปรแกรมเชิงพลวัตแบบทั่วไปมาก
    • เป็นคนที่เรียนกับ Kang ที่ UCLA หรือเปล่า?

  • ดูเหมือนเว็บต้นฉบับจะรับทราฟฟิกไม่ไหว เลยทิ้งลิงก์ archive ไว้
    https://web.archive.org/web/20240114111200/https://qsantos.f...

  • ด้วยการเขียนโปรแกรมเชิงพลวัต จึงสามารถคำนวณ จำนวนสถานะกระดานโกะที่ถูกกติกา ได้ ซึ่งเป็นตัวเลขยาว 171 หลัก
    วิธีแบบตรงไปตรงมาต้องดูทุกสถานะที่เป็นไปได้ทั้งหมดของกระดาน n×n จึงใช้เวลา 3^(n^2) แต่การเขียนโปรแกรมเชิงพลวัตตัดมิติออกไปได้หนึ่งมิติในทางปฏิบัติ ทำให้ลดความซับซ้อนเวลาเหลือ O(n^5 * 5.4^n) และความซับซ้อนหน่วยความจำเหลือ O(n * 5.4^n)
    https://tromp.github.io/go/legal.html
    https://tromp.github.io/go/gostate.pdf

  • ชื่อ “Dynamic Programming” อาจฟังดูแปลก เพราะคำว่า programming ในที่นี้ไม่ได้หมายถึงสาขาการเขียนโปรแกรมคอมพิวเตอร์ แต่มีความหมายใกล้กับการทำ optimization คล้ายกับ linear programming
    มองได้ว่าการเขียนโปรแกรมเชิงพลวัตเป็นวิธีแก้ปัญหาการตัดสินใจตามเวลาแบบไม่ต่อเนื่อง กล่าวคือปัญหาในการเลือกลำดับที่เหมาะที่สุด {a_t} เพื่อทำให้ \sum_t u_t(a_t) มากที่สุดภายใต้ข้อจำกัด โดยนิยามฟังก์ชันค่า V* เป็น V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) } แล้วใช้มันเพื่อลดมิติของปัญหา optimization ลงอย่างมาก

    • จริง ๆ แล้วที่มาของชื่ออย่างเป็นทางการ https://en.wikipedia.org/wiki/Dynamic_programming#History ค่อนข้างขำ Bellman บอกว่าเขาชอบคำว่า “dynamic” เพราะเป็นคำคุณศัพท์ที่แทบเป็นไปไม่ได้จะถูกใช้ในความหมายลบ และเป็นชื่อที่แม้แต่นักการเมืองก็ไม่อาจคัดค้านได้
    • เวลาเห็นคนอื่นใช้คำว่า “การเขียนโปรแกรมเชิงพลวัต” บางทีก็ให้ความรู้สึกเหมือนพยายามทำตัวให้ดูฉลาด ทั้งที่จริงแล้วก็แค่ใช้ แนวทางที่เป็นธรรมชาติและเข้าใจได้ตรงไปตรงมา โดยสังเกตว่าปัญหาสามารถแตกออกเป็นปัญหาย่อยที่เล็กลงเรื่อย ๆ ได้ แต่กลับพูดเหมือนว่าได้ “ใช้” เทคนิคพิเศษอะไรบางอย่าง
    • น่าสนใจที่เมื่อก่อน งานประเภท การคำนวณ อะไรบางอย่าง เช่นปัญหา optimization มีอิทธิพลต่อภาพความคิดเรื่องคอมพิวเตอร์ว่าจะเอาไปทำอะไร มากกว่าปัจจุบันมาก ทุกวันนี้ส่วนใหญ่เป็นเรื่องเก็บ/ดึงข้อมูลและเครือข่าย และถึงจะมีการคำนวณอยู่ข้างในก็มักถูกห่อหุ้มไว้อย่างดี
    • คำว่า “optimization” เองก็ชวนให้เข้าใจผิดคล้ายกัน เคยมีครั้งหนึ่งที่ลงเรียนวิชาคอมพิวเตอร์ชื่อ “optimization” แล้วคาดหวังว่าจะได้เรียนอะไรอีกแบบไปเลย
    • ถ้าย้อนกลับไปอีก คำว่า “programming” อธิบายแนวคิดนี้ได้ตรงกว่า สิ่งที่ทุกวันนี้เราเรียกว่า “programming” แท้จริงแล้วคือ การเขียนโค้ด และยังแยกย่อยได้เป็นหลายแนวทาง เช่น functional, declarative, procedural programming ภายใต้ร่มคำนี้ยังมีอะไรอีกมากมาย

  • ถ้าได้ยินคำว่า “dynamic programming” แล้วคิดไปเลยว่าเป็นแค่ memoization จะถือว่าผิดไหม? ส่วนที่ขาดไปอาจเป็นการแยกปัญหาอย่างชาญฉลาดเพื่อให้ใช้ memoization ได้

    • memoization เป็นเทคนิคที่กว้างกว่านั้น มักเป็นเพียงการแคชผลลัพธ์ที่คำนวณไปแล้ว เผื่อภายหลังต้องใช้ซ้ำอีกครั้ง
      dynamic programming ใกล้เคียงกับ memoization อย่างเป็นระบบ มากกว่า โดยค่อย ๆ แก้ปัญหาย่อยที่ใหญ่ขึ้นจนไปถึงคำตอบของปัญหาทั้งหมด คำว่า “อัลกอริทึมแบบอุปนัย” ก็พอเข้ากันอยู่บ้าง เพราะอัลกอริทึม dynamic programming ทั่วไปนั้นแทบจะคล้ายกับการพิสูจน์ด้วยอุปนัยทางคณิตศาสตร์ เพียงแต่น่าเสียดายที่คำนี้มีความหมายอื่นถูกใช้อยู่แล้ว
    • ผมสอน dynamic programming แบบนั้นพอดี เริ่มจากแก้แบบเรียกซ้ำก่อน แล้วค่อยเพิ่ม memoization เข้าไป แบบนี้เรียกว่า top-down
      จากนั้นพอดูว่า recursion กับ memoization มี overhead อยู่ ถ้าสร้างตารางจากล่างขึ้นบนและตัดการเรียกซ้ำออก ก็จะกลายเป็น dynamic programming
    • ในแนวทางของผม memoization คือขั้นที่ 2 จาก 3 ขั้นของ dynamic programming ขั้นที่ 1 คือหาอัลกอริทึมแบบเรียกซ้ำ ขั้นที่ 2 คือ memoization ขั้นที่ 3 คือทำให้เป็นแบบ iterative/bottom-up และถ้าได้ก็มีขั้น 3b คือปรับใช้หน่วยความจำให้เหมาะสม
      ขั้นที่ 3 คือส่วนที่เป็นเอกลักษณ์ของ dynamic programming มากที่สุด แต่ถ้าหยุดที่ขั้น 2 ก็ยังเรียกว่าเป็น dynamic programming ได้เหมือนกัน เพียงแต่ยังไม่ประสิทธิภาพสูงสุด พูดอีกแบบคือ memoization คือการแคช ส่วนขั้นที่ 3 คือการถามว่ามีวิธีเติมแคชนั้นล่วงหน้าหรือไม่
    • ยังมีวิธีแก้แบบ dynamic programming ที่ไม่ได้อิงกับ memoization ด้วย เช่น ปัญหาหา สตริงย่อยร่วมที่ยาวที่สุด ของสองสตริง ซึ่งต้องใช้แค่ช่องทางซ้ายกับด้านบนของตารางครั้งเดียว ทำให้ memoization ไม่ได้ช่วยมากนัก
      โดยทั่วไป ถ้าปัญหาย่อยซ้อนทับกันมาก และคำตอบย่อยที่เหมาะที่สุดต้องเป็นส่วนหนึ่งของคำตอบรวมที่เหมาะที่สุด ก็มีโอกาสใช้ dynamic programming ได้ การบอกว่า memoization เท่านั้นคือ dynamic programming ก็คล้ายกับการบอกว่า hash table เท่านั้นคือ abstract data type
    • สำหรับผม ถ้าคิดแบบนั้นก็ถือว่าผิด อย่างแรกคือมีตัวอย่างโต้แย้งชัดเจนว่า memoization ใช้นอกเหนือจาก dynamic programming ได้ ในทางกลับกัน อัลกอริทึม dynamic programming ส่วนใหญ่สามารถทำได้โดยเก็บผลลัพธ์ลงตาราง แล้วค่อยหาคำตอบที่ดีที่สุดจากตารางนั้นภายหลัง
      โดยพื้นฐานแล้ว memoization เป็นกลยุทธ์สำหรับทำให้อัลกอริทึมเร็วขึ้น

  • สนุกดีที่ได้เล่น Advent of Code จบในปีนี้ เห็นได้ชัดว่าวันที่ 1 โดยเฉพาะพาร์ต 2 ยากกว่าปีก่อนมาก และผมก็เขียนถึงเรื่องนั้นไว้ที่ https://blog.singleton.io/posts/2024-01-02-advent-of-code-20... แต่การเปรียบเทียบสถิติ 2022 ปัจจุบันกับสถิติ 2023 ปัจจุบันอย่างเดียวไม่ได้ชัดเจนนัก เพราะคนมีเวลาแก้ปริศนา 2022 เพิ่มมาอีก 1 ปี
    พอลองหยิบสถิติปี 2022 ณ วันที่ 14 มกราคม 2023 https://web.archive.org/web/20230114172513/https://adventofc... มาเทียบ ก็พบว่าความต่างค่อนข้างมาก เมื่อลองวาดกราฟสถิติผู้ที่ทำพาร์ต 2 สำเร็จ https://blog.singleton.io/static/imgs-aoc23/completion.png จะเห็นว่าขนาดกลุ่มที่เริ่มในวันที่ 1 ใกล้เคียงกัน แต่จนถึงวันที่ 15 ปี 2023 ดูยากกว่าปี 2022 อย่างชัดเจน
    สัดส่วนของคนที่ทำพาร์ต 1 ได้แต่ทำพาร์ต 2 ไม่ได้ https://blog.singleton.io/static/imgs-aoc23/ratios.png ก็สูงกว่ามากในหลายวันของปี 2023 และชี้ว่าปัญหาที่ยากเป็นพิเศษคือวันที่ 5, 10, 12 และโดยเฉพาะ พาร์ต 2 ของวันที่ 22

    • Advent of Code ช่วงแรก ๆ สนุกมาก และก่อนถึงช่วงท้ายก็ยังพอเอาตัวรอดได้โดยไม่ต้องใช้เทคนิคใหญ่โต หลังจากนั้นมันยากขึ้นและสนุกน้อยลงจนเลิกไป แล้วก็ไม่ได้แตะอีกเลย
    • ปีนี้ผมเล่น Advent of Code ไปได้ไม่มากเพราะเวลาไม่พอ แต่ก็อาจกลับไปเล่นต่อทีหลัง
      อย่างไรก็ตาม ผมตกใจกับความยากของ พาร์ต 2 วันที่ 5 มาก แม้สุดท้ายจะไม่ยอมแพ้และแก้ได้ แต่ก็สงสัยว่าหรือผมพลาดอะไรพื้น ๆ ไปเลยทำให้แก้ซับซ้อนเกินจำเป็น พอรู้ว่ามันเป็นโจทย์ที่ท้าทายอยู่แล้วก็โล่งใจ
    • นี่เป็นแค่ประสบการณ์ส่วนตัว และอาจได้รับผลจากการลองทำด้วยภาษาที่ไม่ได้ใช้ประจำ แต่สำหรับผม พาร์ต 2 ของวันที่ 1 ไม่ได้ยากเท่ากับที่ คำอธิบายโจทย์ไม่เหมาะสม
      ตัวอย่างที่ให้มาคือ two1nine, eightwothree, abcone2threexyz, xtwone3four, 4nineeightseven2, zoneight234, 7pqrstsixteen แต่กลับไม่มีตัวอย่างสำคัญอย่าง oneight ถ้าไม่มีตัวอย่างแบบนี้ ก็ยากที่จะระบุได้อย่างแม่นยำว่าควรแทนค่าตัวเลขอย่างไร
    • ขอเสริมจากประเด็นนี้อีกนิด ผมมีสคริปต์สำหรับดูความคืบหน้าแยกตามวันอยู่ ถ้าดูสองคอลัมน์สุดท้ายจะเห็นชัดว่าปี 2023 โหดกว่าปี 2022 แค่ไหน โดยเฉพาะช่วงต้น
      ในปี 2022 ช่วงสองสามวันแรกคนส่วนใหญ่ยังตามต่อได้ สัดส่วนการอยู่รอดเกิน 80% ในหลายวัน และแทบทุกคนทำครบทั้งสองพาร์ตได้ ขณะที่วันที่ 1 ของปี 2023 มีเพียง 76% ของคนที่ทำพาร์ต 1 ได้ที่ทำพาร์ต 2 ต่อสำเร็จ และมีคนจำนวนมากเลิกในวันที่ 3 กับวันที่ 5
      น่าสนใจว่าช่วงสองสามวันท้ายไม่ได้ต่ำขนาดนั้น ซึ่งอธิบายได้จากการที่ Advent of Code 2023 เพิ่งผ่านมาไม่นานกว่า 2022 ในมุมมองของผม กลุ่มนี้คือคนที่ไม่ว่าจะยากแค่ไหนก็จะผ่านความท้าทายทั้งหมดไปได้ระดับหนึ่ง ส่วนคนอีกมากจะเลิกเมื่อรู้สึกว่ามันใช้เวลามากเกินไป