ทำไมต้องเรียนโครงสร้างข้อมูลและขั้นตอนวิธีในยุคที่ AI เขียนโค้ดได้

ในยุคที่ AI ร่างโค้ดให้เราได้ในไม่กี่วินาที คำถามที่นักศึกษาปี 1 มักถามคือ “ยังต้องเรียนโครงสร้างข้อมูลและขั้นตอนวิธี (Data Structures & Algorithms — DSA) อยู่ไหม?” คำตอบสั้น ๆ คือ ต้อง — แต่เหตุผลเปลี่ยนไป จากเดิมที่เราเรียนเพื่อ “เขียนโค้ดเป็น” วันนี้เราเรียนเพื่อ “ตัดสินได้ว่าโค้ดที่ได้มานั้นดีจริงหรือไม่” ยิ่ง AI เขียนโค้ดได้เก่งขึ้นและเร็วขึ้นทุกปี งานของมนุษย์ก็ยิ่งเลื่อนขึ้นไปอยู่ที่ชั้น “ตรวจสอบและตัดสินใจ” มากกว่า “พิมพ์”

แนวคิดหลัก

AI ทำให้ต้นทุนของการ “พิมพ์โค้ด” ถูกลงมาก ทักษะเชิงกลไก เช่น จำ syntax หรือพิมพ์ลูปได้คล่อง จึงมีมูลค่าทางตลาดลดลง แต่สิ่งที่ AI ทำแทนเราไม่ได้คือการ ตัดสินใจว่าโค้ดที่ได้มานั้นถูกต้อง มีประสิทธิภาพ และเชื่อถือได้หรือไม่

AI ทำให้การเขียนโค้ดถูกลง แต่ทำให้ความเข้าใจเชิงลึกมีค่ามากขึ้น

บทบาทของคุณกำลังเปลี่ยนจาก ผู้เขียน (writer) ไปสู่ ผู้ตัดสิน (judge) ผู้ที่ไม่เข้าใจ DSA อย่างลึกซึ้งจะกลายเป็นเพียง ผู้รับ (recipient) ที่ก็อปปี้คำตอบของ AI มาวางโดยไม่รู้ว่ามันจะพังเมื่อข้อมูลโตขึ้นหรือไม่ มีบั๊กซ่อนอยู่หรือเปล่า

เป้าหมายของวิชานี้คือฝึก สัญชาตญาณ (intuition) ก่อนการท่องจำ — ให้คุณ “รู้สึก” ได้ว่าวิธีไหนจะไปรอดเมื่อระบบโต ไม่ใช่แค่จำสูตรมาตอบข้อสอบ

สามทักษะที่ AI แทนไม่ได้

1. สัญชาตญาณด้านความซับซ้อน (Complexity Intuition)

ลองนึกภาพเปรียบเทียบง่าย ๆ: การหาเพื่อนคนหนึ่งในห้องเรียน 30 คน ใช้เวลาไม่กี่วินาที แต่การหาคน ๆ เดียวในเมืองที่มีประชากร 10 ล้านคน โดยเดินไปถามทีละคน อาจใช้เวลาทั้งชีวิตไม่จบ ความต่างไม่ได้อยู่ที่ “ความขยัน” แต่อยู่ที่ อัตราการเติบโต ของงานเมื่อขนาดปัญหาโตขึ้น — นี่คือสิ่งที่ Big-O พยายามจับให้เราเห็น

ตารางข้างล่างแสดงจำนวนการดำเนินการโดยประมาณของแต่ละคลาสความซับซ้อน เมื่อ n โตขึ้น:

n	O(1)	O(log n)	O(n)	O(n log n)	O(n²)	O(2ⁿ)
10	1	~3	10	~33	100	1,024
100	1	~7	100	~664	10,000	~10³⁰
10,000	1	~13	10,000	~133,000	100,000,000	ทำไม่ไหวจริง
10,000,000	1	~23	10,000,000	~233,000,000	~10¹⁴	ทำไม่ไหวจริง

สังเกตแถวสุดท้าย: เมื่อ n = 10 ล้าน อัลกอริทึม O(n²) ต้องทำงานราว 10¹⁴ ครั้ง — ต่อให้คอมพิวเตอร์ทำได้พันล้านครั้งต่อวินาที ก็ยังกินเวลาเป็นวัน ส่วน O(2ⁿ) ที่ n เพียง 100 ก็ให้ตัวเลขที่ใหญ่เกินจำนวนอะตอมในเอกภพที่สังเกตได้แล้ว

ลองกดสลับเส้นกราฟด้านบนเพื่อดูว่าเส้นแต่ละแบบทิ้งห่างกันเร็วแค่ไหนเมื่อ n เพิ่มขึ้น — นี่คือสิ่งที่คุณต้อง “รู้สึก” ได้โดยไม่ต้องคำนวณทุกครั้ง

ตัวอย่าง: ถ้ามีคนถามว่า “ในรายชื่อ 10 ล้านรายการ มีรายการซ้ำกันไหม” สองวิธีนี้ให้คำตอบถูกทั้งคู่

# วิธี A: เทียบทุกคู่ — O(n^2)
def has_duplicate_a(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

# วิธี B: ใช้เซต — O(n)
def has_duplicate_b(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

วิธี A กับ 10 ล้านรายการต้องทำงานราว 10^14 ครั้ง — รันเป็นวัน ๆ ส่วนวิธี B ทำงานราว 10^7 ครั้ง — เสร็จในวินาทีเดียว ผู้ที่มีสัญชาตญาณด้านความซับซ้อนจะมองออกทันทีว่าวิธี A ใช้ไม่ได้จริง โดยไม่ต้องรันด้วยซ้ำ

มาไล่ดูสถานะตัวแปรทีละขั้นของวิธี B กับข้อมูล items = [3, 7, 2, 7, 5] เพื่อให้เห็นภาพว่ามันทำงานอย่างไร:

รอบ	x	seen (ก่อนตรวจ)	`x in seen`?	seen (หลังเพิ่ม)
1	3	`{}`	False	`{3}`
2	7	`{3}`	False	`{3, 7}`
3	2	`{3, 7}`	False	`{3, 7, 2}`
4	7	`{3, 7, 2}`	True → คืนค่า `True` ทันที	—

สังเกตว่าฟังก์ชันหยุดทำงานทันทีที่เจอค่าซ้ำ (รอบที่ 4) โดยไม่ต้องไล่ดูสมาชิกที่เหลือ — นี่คือเหตุผลที่ในทางปฏิบัติ วิธี B มักเร็วกว่าค่าประมาณ O(n) เสียอีกเมื่อเจอค่าซ้ำเร็ว

2. การจำลองปัญหา (Problem Modeling)

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

ตัวอย่าง: ระบบต้องตอบคำถามว่า “ผู้ใช้คนนี้เคยกดไลก์โพสต์นี้แล้วหรือยัง” หลายล้านครั้งต่อวินาที

ถ้าจำลองด้วย list ของไลก์ การค้นหาแต่ละครั้งเป็น O(n)
ถ้าจำลองด้วย set หรือ dict (hash table) การค้นหาเป็น O(1) โดยเฉลี่ย

การเลือกโครงสร้างข้อมูลให้ถูกตั้งแต่ต้น สำคัญกว่าการเขียนโค้ดให้สวย เพราะมันกำหนดเพดานประสิทธิภาพของทั้งระบบ ลองเปรียบเทียบต้นทุนของโครงสร้างข้อมูลพื้นฐานสามแบบ:

โครงสร้างข้อมูล	ค้นหา (lookup)	แทรก (insert)	เหมาะกับ
`list` (ไม่เรียงลำดับ)	O(n)	O(1) ท้าย list / O(n) หัว list	ข้อมูลน้อย ไม่ค้นหาบ่อย
`set` / `dict` (hash table)	O(1) โดยเฉลี่ย	O(1) โดยเฉลี่ย	ต้องเช็คสมาชิกภาพหรือค้นหาบ่อย ๆ
linked list	O(n)	O(1) ถ้ารู้ตำแหน่งอยู่แล้ว (เช่นหัว list)	แทรก/ลบกลางลิสต์บ่อย โดยไม่สนใจการเข้าถึงแบบสุ่ม (random access)

ลองเพิ่มข้อมูลลงใน hash table ด้านบนดู แล้วสังเกตว่าเมื่อสอง key ตกไปอยู่ช่องเดียวกัน (collision) มันจัดการอย่างไร — นี่คือเหตุผลที่การค้นหาเป็น O(1) “โดยเฉลี่ย” ไม่ใช่ “เสมอไป”

ไม่ใช่แค่การค้นหาเท่านั้นที่ต้นทุนต่างกันตามโครงสร้างข้อมูล การ แทรก ก็เช่นกัน ลองดู linked list ด้านล่าง: แทรกที่หัว (prepend) เป็น O(1) เสมอเพราะไม่ต้องขยับใคร แต่แทรกที่ท้าย (append) โดยไม่มีตัวชี้ tail จะต้องไล่ไปจนสุดก่อน กลายเป็น O(n)

นี่คือเหตุผลที่ collections.deque ของ Python (ซึ่งออกแบบให้ทั้งสองปลายเป็น O(1)) เหมาะกับคิวงาน (job queue) มากกว่า list — เราจะกลับมาคำถามนี้อีกครั้งในแบบฝึกหัดข้อ 3

3. การตรวจสอบและแก้จุดบกพร่อง (Verification & Debugging)

ความสามารถในการอ่านโค้ดอย่างมีวิจารณญาณ ทดสอบ และหา กรณีขอบ (edge cases) ที่ AI มักมองข้าม

ตัวอย่าง: AI ให้ฟังก์ชันหาค่ากลาง (median) มาแบบนี้

def median(nums):
    nums.sort()
    mid = len(nums) // 2
    return nums[mid]

อย่าเพิ่งเชื่อเพราะมันดูสั้นและสมเหตุสมผล ลองไล่ทดสอบกับหลายกรณี:

อินพุต	ค่ากลางที่ถูกต้อง	ผลจากฟังก์ชัน	ถูกไหม
`[3, 1, 2]`	2	2	✅
`[4, 1, 3, 2]`	2.5 (เฉลี่ย 2 กับ 3)	3	❌ ไม่รองรับจำนวนสมาชิกเป็นเลขคู่
`[]`	ควร raise error หรือคืนค่าที่นิยามไว้ชัดเจน	`IndexError`	❌ ไม่ handle list ว่าง

โค้ดที่ “รันผ่าน” กับตัวอย่างง่าย ๆ (แถวแรก) ไม่ได้แปลว่า “ถูกต้อง” ผู้ตัดสินที่ดีจะหากรณีที่ทำให้มันพังก่อนที่มันจะไปพังบนระบบจริง เวอร์ชันที่แก้แล้วจะเป็นแบบนี้:

def median(nums):
    if not nums:
        raise ValueError("median of empty list")
    s = sorted(nums)
    n = len(s)
    mid = n // 2
    if n % 2 == 1:
        return s[mid]
    return (s[mid - 1] + s[mid]) / 2

วงจร AI Code Critique

นี่คือกิจกรรมหลักที่เราจะทำซ้ำตลอดทั้งคอร์ส วงจรนี้มี 4 ขั้นตอน

Prompt → Read → Judge → Improve (สั่ง → อ่าน → ตัดสิน → ปรับปรุง)

Prompt (สั่ง) — ขอให้ AI แก้ปัญหาที่ชัดเจน เช่น “เขียนฟังก์ชันหาเลขที่ปรากฏบ่อยที่สุดใน list”
Read (อ่าน) — อ่านโค้ดให้เข้าใจทุกบรรทัด ไม่ใช่แค่ดูว่ามันรันได้
Judge (ตัดสิน) — ถามว่า ความซับซ้อนเท่าไร? มีกรณีขอบที่พังไหม? เลือกโครงสร้างข้อมูลถูกหรือเปล่า?
Improve (ปรับปรุง) — สั่ง AI แก้ตามที่เราวิเคราะห์ หรือเขียนแก้เอง แล้ววนกลับไปตรวจใหม่

ตัวอย่างเดินจริง: สั่งว่า “หาเลขที่ปรากฏบ่อยที่สุด” AI ตอบมาว่า

def most_frequent(nums):
    return max(nums, key=nums.count)

Read: โค้ดสั้นและดูสวย รันผ่านกับ [1, 2, 2, 3] ได้ผลลัพธ์ 2

Judge: แต่ nums.count(x) เป็น O(n) และถูกเรียกสำหรับทุกสมาชิก ทำให้ทั้งหมดเป็น O(n^2) — ช้ามากเมื่อ list ใหญ่

Improve: ใช้ตารางนับความถี่แทน

from collections import Counter

def most_frequent(nums):
    return Counter(nums).most_common(1)[0][0]

เวอร์ชันนี้เป็น O(n) คุณเพิ่งทำหน้าที่ผู้ตัดสินสำเร็จ

ปัญหาจากโลกจริง

สมมติคุณทำฟีเจอร์ “ค้นหาสินค้าตามรหัส” ในระบบอีคอมเมิร์ซที่มีสินค้า 5 ล้านชิ้น คุณขอให้ AI เขียนสองรอบ ได้สองคำตอบที่ รันผ่านการทดสอบเล็ก ๆ เหมือนกัน

# คำตอบ 1: ค้นแบบเชิงเส้น
def find_product_v1(products, target_id):
    for p in products:
        if p["id"] == target_id:
            return p
    return None

# คำตอบ 2: สร้าง index ครั้งเดียว แล้วค้นด้วย dict
class ProductCatalog:
    def __init__(self, products):
        self.index = {p["id"]: p for p in products}

    def find(self, target_id):
        return self.index.get(target_id)

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

จำนวนสินค้า	คำตอบ 1 — O(n) ต่อการค้นหา	คำตอบ 2 — O(1) ต่อการค้นหา (หลังสร้าง index)
10	เร็วมาก (ไม่รู้สึกถึงความต่าง)	เร็วมาก
100,000	เริ่มหน่วงเมื่อค้นหาถี่	เร็วเท่าเดิม
5,000,000	ค้นหาแต่ละครั้งช้าลงหลักพันเท่า และเมื่อคูณด้วยหลายพันคำขอต่อวินาที ระบบจะล่ม	ยังคงเร็วเท่าเดิม เพราะจ่ายต้นทุนสร้าง index แค่ครั้งเดียว

คำตอบ 1 ค้นทีละ O(n) — เมื่อมีสินค้า 5 ล้านชิ้นและค้นบ่อย ระบบจะช้าจนล่ม
คำตอบ 2 จ่ายต้นทุน O(n) ครั้งเดียวตอนสร้าง index แล้วค้นแต่ละครั้งเป็น O(1) — ไหลลื่นแม้ข้อมูลโต

ผู้ตัดสินที่ดีจะถามคำถามสำคัญว่า “ฟังก์ชันนี้ถูกเรียก กี่ครั้ง และข้อมูล ใหญ่แค่ไหน” คำถามเดียวนี้แยกคำตอบที่ “รันได้” ออกจากคำตอบที่ “ใช้งานจริงได้”

เรื่องจริงอีกเรื่องหนึ่ง (สรุปจากปัญหาแบบที่พบได้ทั่วไปในระบบแจ้งเตือน): ทีมหนึ่งสร้างฟีเจอร์ “จำนวนข้อความที่ยังไม่ได้อ่าน” ด้วยการนับแถวในตาราง messages ที่ is_read = false ใหม่ทุกครั้งที่ผู้ใช้เปิดแอป วิธีนี้ใช้ได้ดีตอนทดสอบกับผู้ใช้ไม่กี่คน แต่พอมีผู้ใช้จริงหลักล้านคน แต่ละคนมีข้อความสะสมหลักหมื่น การนับกลายเป็นการสแกนตารางขนาดใหญ่ซ้ำ ๆ หลายพันครั้งต่อวินาที ฐานข้อมูลรับภาระไม่ไหวและระบบเริ่มหน่วง

ทางแก้คือเปลี่ยนจาก “คำนวณใหม่ทุกครั้ง” (O(n) ต่อการเรียกดู) เป็น “เก็บตัวนับที่อัปเดตทีละนิด” — เพิ่มคอลัมน์ unread_count ที่ +1 เมื่อมีข้อความใหม่เข้ามา และ -1 เมื่อผู้ใช้อ่าน ทำให้การอ่านค่าเป็น O(1) เสมอ ไม่ว่าผู้ใช้จะมีข้อความสะสมกี่หมื่นข้อความ นี่คือการจำลองปัญหาใหม่: จากคำถาม “นับกี่ครั้ง” ไปเป็น “ติดตามการเปลี่ยนแปลง”

แบบฝึกหัด

ข้อ 1 สองฟังก์ชันต่อไปนี้ตรวจว่ามีสมาชิกซ้ำใน list หรือไม่ อันไหน scale ได้ดีกว่า และเพราะอะไร

def dup_a(xs):
    return len(xs) != len(set(xs))

def dup_b(xs):
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            if xs[i] == xs[j]:
                return True
    return False

เฉลย

dup_a ดีกว่า — สร้าง set ครั้งเดียวเป็น O(n) แล้วเทียบความยาว ส่วน dup_b เป็น O(n^2) เพราะเทียบทุกคู่ เมื่อ n ใหญ่ dup_b ช้ากว่ามหาศาล (ข้อแม้: dup_a ต้องการให้สมาชิก hashable)

ข้อ 2 AI เขียนฟังก์ชันรวมสตริงในลูปแบบนี้ มีปัญหาด้านประสิทธิภาพอะไรซ่อนอยู่

def join_words(words):
    result = ""
    for w in words:
        result += w + " "
    return result

เฉลย

ในหลายภาษา (และในกรณีทั่วไปที่ควรระวัง) การ += สตริงสร้างสตริงใหม่ทุกครั้ง ทำให้ในกรณีเลวร้ายเป็น O(n^2) ทางที่ดีคือใช้ " ".join(words) ซึ่งเป็น O(n) และอ่านง่ายกว่า บทเรียนคือ ต้องระวังต้นทุนที่ซ่อนอยู่ในการดำเนินการที่ดู “ไม่มีพิษภัย”

ข้อ 3 ระบบต้องเก็บลำดับงานที่เข้ามาก่อนได้ทำก่อน (FIFO) และต้องเพิ่ม/ลบงานหลายล้านครั้ง ควรเลือกโครงสร้างข้อมูลใดระหว่าง list ที่ใช้ pop(0) กับ collections.deque

เฉลย

ควรใช้ deque เพราะ popleft() เป็น O(1) ส่วน list.pop(0) เป็น O(n) เนื่องจากต้องเลื่อนสมาชิกทุกตัว นี่คือตัวอย่างของ การจำลองปัญหา — เลือกโครงสร้างให้ตรงกับรูปแบบการใช้งาน (ย้อนกลับไปดู widget linked list ในหัวข้อที่ 2 ประกอบ)

ข้อ 4 ฟังก์ชันนี้หาค่ามากสุดใน list แต่มีบั๊กในกรณีขอบ จงหาให้เจอ

def my_max(xs):
    m = 0
    for x in xs:
        if x > m:
            m = x
    return m

เฉลย

บั๊กอยู่ที่ค่าตั้งต้น m = 0 ถ้าทุกค่าใน list เป็นลบ เช่น [-3, -1, -7] ฟังก์ชันจะคืน 0 ผิด ควรตั้งต้นด้วย m = xs[0] (และจัดการกรณี list ว่างแยกต่างหาก) นี่คือทักษะ การตรวจสอบและหากรณีขอบ

ข้อ 5 ฟังก์ชันคำนวณเลขฟีโบนักชีต่อไปนี้ให้คำตอบถูกต้องเสมอ แต่ AI ที่เขียนให้ไม่ได้เตือนว่ามันจะช้าแค่ไหนเมื่อ n โต จงระบุความซับซ้อนโดยประมาณ และอธิบายสาเหตุ

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

เฉลย

ความซับซ้อนคือ O(2^n) — เพราะแต่ละคอลจะแตกสาขาออกเป็นสองคอลย่อย (fib(n-1) และ fib(n-2)) และหลายคอลย่อยเหล่านั้นคำนวณ ค่าเดิมซ้ำ ๆ (เช่น fib(n-2) ถูกคำนวณใหม่ทั้งจากฝั่ง fib(n-1) และโดยตรง) ย้อนกลับไปดูตารางการเติบโตในหัวข้อ Complexity Intuition — ที่ n เพียง ~40 ฟังก์ชันนี้ก็ช้าจนสังเกตได้แล้ว ทางแก้คือ memoization (เก็บผลลัพธ์ที่เคยคำนวณ) ซึ่งลดความซับซ้อนเหลือ O(n)

ข้อ 6 ระบบบล็อกเบอร์โทรสแปม (blocklist) ต้องเช็คว่าเบอร์หนึ่ง ๆ อยู่ในลิสต์เบอร์ที่ถูกบล็อก 20 ล้านเบอร์หรือไม่ หลายพันครั้งต่อวินาที ควรเก็บเบอร์เหล่านี้ด้วยโครงสร้างข้อมูลใด เพราะอะไร

เฉลย

ควรเก็บด้วย set (hash table) เพราะการเช็คสมาชิกภาพ (number in blocked_set) เป็น O(1) โดยเฉลี่ย ไม่ว่าลิสต์จะมี 20 ล้านเบอร์หรือมากกว่านั้น ถ้าเก็บเป็น list ธรรมดา แต่ละการเช็คจะเป็น O(n) และเมื่อคูณด้วยหลายพันครั้งต่อวินาที ระบบจะรับภาระไม่ไหว (ย้อนกลับไปเล่น widget algo-hash ในหัวข้อที่ 2 เพื่อดูว่า hash table หาตำแหน่งได้เร็วเพราะอะไร)

ข้อ 7 ฟังก์ชันนี้เช็คว่าสมาชิกทุกตัวใน items_to_check อยู่ใน big_list หรือไม่ ถ้า big_list มีสมาชิกหลักล้าน และ items_to_check มีสมาชิกหลักพัน ความซับซ้อนคือเท่าไร และจะปรับปรุงอย่างไร

def contains_all(big_list, items_to_check):
    return all(item in big_list for item in items_to_check)

เฉลย

item in big_list เมื่อ big_list เป็น list คือการค้นหาเชิงเส้น O(n) และถูกเรียกซ้ำ m ครั้ง (หนึ่งครั้งต่อสมาชิกใน items_to_check) รวมเป็น O(n * m) เมื่อ n เป็นหลักล้านและ m เป็นหลักพัน นี่คือหลายพันล้านการดำเนินการ ทางแก้คือแปลง big_list เป็น set ก่อนเพียงครั้งเดียว (O(n)) แล้วเช็คสมาชิกภาพทีละตัว (O(1) ต่อครั้ง) รวมเป็น O(n + m) เท่านั้น

def contains_all(big_list, items_to_check):
    big_set = set(big_list)
    return all(item in big_set for item in items_to_check)

ข้อ 8 ทายผลลัพธ์การพิมพ์สองบรรทัดสุดท้ายของโค้ดนี้ แล้วอธิบายว่าทำไมมันไม่ใช่ ['apple'] และ ['banana'] ตามที่คนส่วนใหญ่คาดหวัง

def add_item(item, basket=[]):
    basket.append(item)
    return basket

print(add_item("apple"))
print(add_item("banana"))

เฉลย

ผลลัพธ์คือ ['apple'] แล้วตามด้วย ['apple', 'banana'] — ไม่ใช่ ['banana'] เดี่ยว ๆ เพราะค่าเริ่มต้นที่เป็น mutable (basket=[]) ถูกสร้าง ครั้งเดียว ตอนนิยามฟังก์ชัน แล้วถูกใช้ร่วมกันในทุกการเรียกที่ไม่ได้ส่ง basket มาเอง ทางแก้คือใช้ None เป็นค่าเริ่มต้น แล้วสร้าง list ใหม่ข้างในฟังก์ชัน:

def add_item(item, basket=None):
    if basket is None:
        basket = []
    basket.append(item)
    return basket

นี่คือกับดักคลาสสิกที่ AI มักไม่เตือน เพราะโค้ดต้นฉบับ “รันได้ไม่มี error” — ต้องอาศัยการทดสอบและความเข้าใจ semantics ของภาษาจริง ๆ ถึงจะจับได้

AI Code Critique

ลองทำเองเต็มวงจร

Prompt ที่ส่งให้ AI: “เขียนฟังก์ชัน Python ที่รับรายชื่ออีเมล แล้วคืนรายชื่อที่ไม่ซ้ำ โดยคงลำดับเดิมไว้”

โค้ดที่ AI ตอบกลับมา:

def unique_emails(emails):
    result = []
    for e in emails:
        if e not in result:
            result.append(e)
    return result

มันรันผ่านและคงลำดับได้จริง — แต่ในฐานะผู้ตัดสิน ลองวิเคราะห์ดูว่ามีปัญหาอะไร แล้วปรับปรุง

เฉลย

Judge: e not in result ค้นใน list เป็น O(n) และถูกเรียกทุกรอบ ทำให้ทั้งหมดเป็น O(n^2) เมื่อมีอีเมลหลายล้านรายการจะช้ามาก

Improve: ใช้ set ช่วยจำสิ่งที่เคยเห็น เพื่อให้การตรวจสอบเป็น O(1) โดยเฉลี่ย ในขณะที่ยังคงลำดับด้วย list ผลลัพธ์

def unique_emails(emails):
    seen = set()
    result = []
    for e in emails:
        if e not in seen:
            seen.add(e)
            result.append(e)
    return result

เวอร์ชันนี้เป็น O(n) — ถูกต้องเหมือนเดิม แต่ scale ได้จริง

🎮 เกมเดฟ: ตรวจจับการชนกระสุนนับพันใน Bullet-Hell / Arena Game

เกมแนว bullet-hell หรือ arena shooter มักมีศัตรูและกระสุนเป็นร้อยเป็นพันชิ้นเคลื่อนที่พร้อมกันบนจอ ทุกเฟรมเกมต้องตอบคำถามเดิมซ้ำ ๆ ว่า “วัตถุคู่ไหนชนกันบ้าง” ซึ่งมีโครงร่างปัญหาเดียวกับ “หาสมาชิกซ้ำใน list” ที่เราเจอไปแล้วในหัวข้อ Complexity Intuition โค้ดตรวจชนแบบ “เทียบทุกคู่” ที่ AI มักเสนอมาให้จะรันผ่านฉลุยตอนทดสอบกับวัตถุ 20-30 ชิ้น แต่พอเกมจริงมีกระสุนหลายพันนัดพร้อมกัน เฟรมเรตจะร่วงจนเล่นไม่ได้ — นี่คือจุดที่ผู้ตัดสิน (judge) ต้องจับได้ก่อนปล่อยโค้ดลงโปรดักชัน

from collections import defaultdict

# วิธีไร้เดียงสา: เทียบทุกคู่ของวัตถุ — O(n^2)
def find_collisions_naive(entities):
    """entities: list ของ (id, x, y, radius)"""
    hits = []
    for i in range(len(entities)):
        for j in range(i + 1, len(entities)):
            id_a, xa, ya, ra = entities[i]
            id_b, xb, yb, rb = entities[j]
            dist_sq = (xa - xb) ** 2 + (ya - yb) ** 2
            if dist_sq <= (ra + rb) ** 2:
                hits.append((id_a, id_b))
    return hits


CELL_SIZE = 32  # ขนาดช่องกริด ควรใกล้เคียงขนาดวัตถุ/รัศมีปฏิสัมพันธ์เฉลี่ย


def cell_of(x, y):
    return (int(x // CELL_SIZE), int(y // CELL_SIZE))


# วิธีสเกลได้: จัดกลุ่มวัตถุลงช่องกริด (spatial hash) แล้วเทียบเฉพาะเพื่อนบ้าน — เข้าใกล้ O(n)
def find_collisions_grid(entities):
    grid = defaultdict(list)
    for e in entities:
        _, x, y, _ = e
        grid[cell_of(x, y)].append(e)

    hits = []
    checked = set()
    for id_a, xa, ya, ra in entities:
        cx, cy = cell_of(xa, ya)
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):          # เช็คแค่ 9 ช่อง: ตัวเอง + เพื่อนบ้าน 8 ทิศ
                for id_b, xb, yb, rb in grid[(cx + dx, cy + dy)]:
                    pair = tuple(sorted((id_a, id_b)))
                    if id_a == id_b or pair in checked:
                        continue
                    checked.add(pair)
                    dist_sq = (xa - xb) ** 2 + (ya - yb) ** 2
                    if dist_sq <= (ra + rb) ** 2:
                        hits.append(pair)
    return hits

find_collisions_naive เป็น O(n²) เสมอ — วัตถุ 3,000 ชิ้นต้องเทียบราว 4.5 ล้านคู่ ทุกเฟรม ที่ 60 fps คือเกือบ 270 ล้านครั้งต่อวินาที เกมค้างแน่นอน ส่วน find_collisions_grid จัดวัตถุลง “ถัง” ตามตำแหน่งก่อน (แนวคิดเดียวกับ hash table ในหัวข้อ Problem Modeling) แล้วแต่ละวัตถุเทียบแค่กับเพื่อนบ้านในช่องใกล้เคียง ไม่ใช่ทุกชิ้นบนจอ — ถ้าจำนวนวัตถุต่อช่องคงที่โดยเฉลี่ย ความซับซ้อนรวมจะเข้าใกล้ O(n)

กริด — เข้าใกล้ O(n)

รูป: ซ้าย — ตรวจชนแบบเทียบทุกคู่ (O(n²)) เส้นเชื่อมทุกคู่วัตถุ ขวา — วัตถุกลุ่มเดียวกันถูกจัดลงกริด แล้วเทียบเฉพาะเพื่อนบ้านในช่องเดียวกัน (เข้าใกล้ O(n))

ลองปรับจำนวนวัตถุใน widget ด้านบน แล้วสังเกตว่าตัวนับจำนวนการเปรียบเทียบของแบบ “เทียบทุกคู่” พุ่งขึ้นเร็วกว่าแบบ “กริด” แค่ไหนเมื่อวัตถุเพิ่มขึ้น

เกมเดฟ ข้อ 1 เกม arena มีศัตรูและกระสุนรวม 3,000 ชิ้นบนจอ ถ้าใช้ find_collisions_naive ต้องเทียบกี่คู่โดยประมาณ แล้วถ้าเปลี่ยนไปใช้ find_collisions_grid โดยตั้ง CELL_SIZE ให้เหมาะสม (เฉลี่ยไม่กี่ชิ้นต่อช่อง) จำนวนการเทียบจะลดลงเหลือระดับไหน

เฉลย

find_collisions_naive เทียบทุกคู่ = C(3000, 2) = 3000 × 2999 / 2 ≈ 4.5 ล้านคู่ ต่อหนึ่งเฟรม ส่วน find_collisions_grid แต่ละวัตถุเทียบแค่กับเพื่อนบ้านใน 9 ช่องรอบตัว ถ้าเฉลี่ยมีไม่กี่ชิ้นต่อช่อง งานทั้งหมดจะแปรผันตรงกับ n คูณค่าคงที่เล็ก ๆ (ไม่ใช่ n²) — รวมแล้วอยู่ในระดับหมื่นถึงแสนคู่ ไม่ใช่ล้าน นี่คือความต่างระหว่าง O(n²) กับ O(n)

เกมเดฟ ข้อ 2 ในโค้ด find_collisions_grid ทำไมต้องเช็ค 9 ช่อง (ตัวเองกับเพื่อนบ้าน 8 ทิศ) แทนที่จะเช็คแค่ช่องของตัวเองอย่างเดียว

เฉลย

เพราะวัตถุอาจอยู่ใกล้ขอบของช่อง แล้ววัตถุอีกตัวที่ชนกันได้จริงอาจตกไปอยู่ในช่องข้าง ๆ ถ้าเช็คแค่ช่องตัวเอง จะพลาดการชนที่เกิดขึ้นตรงรอยต่อระหว่างช่อง (edge case ของการแบ่งกริด) การเช็ค 9 ช่องรอบตัวประกันว่าจะไม่พลาดคู่ที่อยู่ใกล้กันจริงแต่ถูกแบ่งเข้าคนละถัง

เกมเดฟ ข้อ 3 ถ้าตั้ง CELL_SIZE เล็กเกินไป (เช่น 1 pixel) หรือใหญ่เกินไป (เช่น 5000 pixel) จะเกิดอะไรขึ้นกับประสิทธิภาพของ find_collisions_grid

เฉลย

ถ้าช่องเล็กเกินไป จะมีช่องจำนวนมหาศาล วัตถุแต่ละชิ้นอาจคาบเกี่ยวหลายช่อง และการไล่ดู 9 ช่องรอบตัวก็ยังต้องทำ overhead การจัดการ dict จำนวนมาก ถ้าช่องใหญ่เกินไป วัตถุจำนวนมากจะกระจุกอยู่ในถังเดียวกัน ทำให้การเทียบภายในถังกลับไปเป็น O(n²) เหมือนเดิม จุดที่เหมาะคือตั้ง CELL_SIZE ให้ใกล้เคียงขนาด/รัศมีปฏิสัมพันธ์เฉลี่ยของวัตถุ เพื่อให้แต่ละถังมีวัตถุแค่ไม่กี่ชิ้น

เกมเดฟ ข้อ 4 กระสุนความเร็วสูงเคลื่อนที่ 200 pixel ต่อเฟรม ขณะที่ตัวผู้เล่นมีขนาดเพียง 20 pixel ถ้าใช้ find_collisions_grid ที่สร้างกริดใหม่จากตำแหน่งปัจจุบันทุกเฟรม จะเกิดปัญหาอะไร และแก้เบื้องต้นอย่างไร

เฉลย

ปัญหานี้เรียกว่า tunneling: กริดตรวจแค่ตำแหน่ง ณ ขณะหนึ่ง (discrete) ถ้ากระสุนกระโดดจากก่อนหน้าตัวผู้เล่นไปอยู่หลังตัวผู้เล่นภายในเฟรมเดียว มันจะไม่เคยอยู่ในช่อง/รัศมีเดียวกับผู้เล่นเลยแม้แต่เฟรมเดียว ทำให้พลาดการชน ทางแก้เบื้องต้นคือตรวจแบบ swept collision (เช็คเส้นทางจากตำแหน่งเก่าไปตำแหน่งใหม่ ไม่ใช่แค่จุดปลาย) หรือจำกัดความเร็วสูงสุดต่อเฟรมให้ไม่เกินขนาดวัตถุที่เล็กที่สุด นี่คือทักษะ การตรวจสอบและหากรณีขอบ ที่นำมาใช้กับระบบเกม

โจทย์ท้าทาย 1 ออกแบบระบบตรวจชนสำหรับเกม arena ที่มีศัตรู 5,000 ตัว กระสุนผู้เล่น 2,000 นัด และกำแพง/สิ่งกีดขวางคงที่หลายร้อยชิ้น ควรใช้กริดเดียวรวมทุกประเภทวัตถุ หรือแยกกริดตามประเภท เพราะอะไร

แนวทาง

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

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

แนวทาง

บอสตัวเดียวที่ใหญ่กว่าช่องกริดมากจะต้องถูกใส่ซ้ำในทุกช่องที่มันคาบเกี่ยว (อาจหลายสิบช่อง) ทำให้ทั้งการสร้างกริดและการค้นหาแพงขึ้นผิดปกติสำหรับวัตถุแค่ชิ้นเดียว ทางแก้ทั่วไปคือแยก “วัตถุใหญ่ผิดปกติ” ออกจากกริด แล้วเช็คมันแบบตรง ๆ กับวัตถุอื่นทุกชิ้น (bounding-box test ธรรมดา) เพราะจำนวนวัตถุใหญ่แบบนี้มีน้อยมาก (มักมีบอสแค่ 1-2 ตัว) ต้นทุนของการเช็คแบบ O(n) ต่อบอสหนึ่งตัวจึงยังเล็กกว่าการทำให้กริดทั้งระบบพัง

เจาะลึกเพิ่มเติม

แหล่งเรียนรู้ระดับโลกที่แนะนำให้ศึกษาต่อ (เป็นภาษาอังกฤษทั้งหมด)

MIT 6.006 Introduction to Algorithms — คอร์สเปิดบน MIT OpenCourseWare มีวิดีโอเลคเชอร์ โน้ต และโจทย์ครบ: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
Harvard CS50 — คอร์สวิทยาการคอมพิวเตอร์เบื้องต้นชื่อดัง ปูพื้นฐานการคิดเชิงคำนวณ: https://cs50.harvard.edu/x/
Stanford CS161 Design and Analysis of Algorithms — เจาะลึกการออกแบบและวิเคราะห์ขั้นตอนวิธี: https://stanford-cs161.github.io/winter2024/
CLRS — Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) — ตำราอ้างอิงมาตรฐานของวงการ เหมาะเป็นเล่มข้างตัวตลอดการเรียน DSA
Skiena — The Algorithm Design Manual (3rd ed.) — เขียนในสไตล์ “War Story” เล่าเคสจริงที่ทีมเลือกอัลกอริทึม/โครงสร้างข้อมูลผิดแล้วระบบพัง ตรงกับสัญชาตญาณที่บทเรียนนี้พยายามปลูกฝังที่สุด
Bhargava — Grokking Algorithms (2nd ed.) — อธิบายด้วยภาพประกอบและภาษาที่เข้าใจง่าย เหมาะเป็นจุดเริ่มต้นก่อนไปอ่านตำราที่เป็นทางการอย่าง CLRS
Sedgewick & Wayne — Algorithms (4th ed.) — ครอบคลุมการ implement โครงสร้างข้อมูลอย่าง hash table และ linked list ที่ใช้ในบทนี้ได้ละเอียดพร้อมโค้ดจริง