การเลือกโครงสร้างข้อมูลให้เหมาะสมกับปัญหา

โครงสร้างข้อมูลที่ “ถูกต้อง” ไม่ได้ตัดสินจากว่ามันสวยหรือซับซ้อนแค่ไหน แต่ตัดสินจาก สิ่งที่คุณทำกับมันบ่อยที่สุด และการตัดสินนั้น — การมองออกว่าปัญหาจริง ๆ ต้องการอะไร — ยังคงเป็นงานของมนุษย์ ไม่ใช่ของ AI

ลองนึกภาพนี้: คุณมีลิ้นชักเก็บของอยู่สามแบบ — กล่องใส (มองเห็นทุกชิ้นทันที แต่หยิบตรงกลางต้องรื้อ), ตู้มีดัชนี (หากุญแจแล้วเจอทันที แต่ไม่รู้ว่าอะไรอยู่ข้าง ๆ อะไร), และกองที่ซ้อนกัน (หยิบบนสุดไวมาก แต่หยิบล่างสุดต้องรื้อทั้งกอง) ไม่มีลิ้นชักไหน “ดีที่สุด” — คำถามที่ถูกต้องคือ “ของชิ้นไหนที่คุณหยิบบ่อยที่สุด” โครงสร้างข้อมูลก็เหมือนกันทุกประการ Array คือกล่องใส, Hash Table คือตู้มีดัชนี, Stack คือกองที่ซ้อนกัน

แนวคิดหลัก

หัวใจของการเลือกโครงสร้างข้อมูลคือประโยคเดียว: “จงปรับให้เหมาะกับการดำเนินการที่ทำบ่อยที่สุด”

ทุกโครงสร้างเก่งบางอย่างและแย่บางอย่างเสมอ ไม่มีตัวไหนเร็วทุกการกระทำ ดังนั้นแทนที่จะถามว่า “โครงสร้างไหนดีที่สุด” ให้ถามว่า “ในโปรแกรมของฉัน ฉันทำอะไรกับข้อมูลชุดนี้บ่อยที่สุด”

เลือกโครงสร้างที่ทำให้การดำเนินการที่ “บ่อยที่สุด” ของคุณเร็ว แล้วยอมให้การดำเนินการที่ “นาน ๆ ที” ช้าลงบ้าง — นั่นคือการแลกเปลี่ยนที่คุ้มค่าเสมอ

คำถามที่ต้องตอบให้ได้ก่อน:

• ฉันต้อง ค้นด้วยกุญแจ (lookup by key) บ่อยไหม → ตารางแฮช
• ฉันต้องให้ข้อมูล เรียงลำดับอยู่ตลอด (keep sorted) ไหม → ต้นไม้ค้นหาทวิภาค (BST)
• ฉันต้องตรวจว่า มีค่านี้อยู่ไหม (membership test) บ่อยไหม → ตารางแฮช (hash set)
• ฉันเข้าถึงข้อมูลแบบ เข้าก่อนออกก่อน (FIFO) หรือ เข้าหลังออกก่อน (LIFO) → คิวหรือสแตก
• ฉันต้องดึง ค่ามากสุด/น้อยสุดซ้ำ ๆ (min/max) โดยไม่สนตัวอื่นไหม → ฮีป (Heap)
• ฉันต้องถาม ช่วงของค่า (range query) เช่น “ทุกตัวระหว่าง 10–50” ไหม → โครงสร้างที่เรียงลำดับ เช่น BST
• ฉันเข้าถึงด้วย ดัชนีตัวเลข (index) เป็นหลักไหม → อาเรย์

ทำไมความแตกต่างระหว่าง O(1), O(log n), O(n) ถึงสำคัญขนาดนี้? เพราะเมื่อ n โตขึ้น ช่องว่างระหว่างเส้นโค้งเหล่านี้ไม่ได้โตแบบเชิงเส้น — มันถ่างออกจนต่างกันเป็นพัน ๆ เท่า ลองปรับกราฟด้านล่างดู:

กรอบการตัดสินใจ

ไล่คำถามตามลำดับนี้ แล้วหยุดที่ข้อแรกที่ตรงกับงานหลักของคุณ:

1. ต้องค้น/เพิ่ม/ลบด้วยกุญแจให้เร็วที่สุด และไม่สนลำดับ? → ตารางแฮช (Hash Table) — O(1) โดยเฉลี่ย
2. ต้องให้ข้อมูลเรียงลำดับตลอด หรือต้องถามช่วงค่า / ตัวที่ใกล้เคียง? → BST (ที่สมดุล) — O(log n)
3. เข้าถึงล่าสุดก่อน (undo, ย้อนกลับ, ตรวจวงเล็บ)? → สแตก (Stack) — push/pop O(1)
4. เข้าก่อนได้ก่อน (คิวงาน, BFS, บัฟเฟอร์)? → คิว (Queue) — enqueue/dequeue O(1)
5. ต้องการค่ามากสุด/น้อยสุดซ้ำ ๆ โดยไม่ต้องเรียงทั้งหมด? → ฮีป (Heap) — insert/extract O(log n)
6. เข้าถึงด้วยดัชนีตัวเลขบ่อย และขนาดค่อนข้างคงที่? → อาเรย์ (Array) — เข้าถึง O(1)
7. เพิ่ม/ลบที่หัว-ท้ายบ่อยมาก แต่แทบไม่เข้าถึงตรงกลางด้วยดัชนี? → ลิงก์ลิสต์ (Linked List) — insert/delete ที่ปลาย O(1)

สรุปเป็นผังการตัดสินใจ

เริ่มต้น: การดำเนินการที่ทำ "บ่อยที่สุด" ในโปรแกรมของฉันคืออะไร?
│
├─ ค้น/เพิ่ม/ลบด้วยกุญแจ ไม่สนลำดับ ─────────────────► Hash Table   O(1) เฉลี่ย
├─ ต้องเรียงลำดับตลอด / ถามช่วงค่า ──────────────────► BST (สมดุล)  O(log n)
├─ ตรวจสมาชิก (มี/ไม่มี) จำนวนมาก ────────────────────► Hash Set    O(1) เฉลี่ย
├─ เข้าถึงล่าสุดก่อน (LIFO) ─────────────────────────► Stack        O(1)
├─ เข้าก่อนออกก่อน (FIFO) ───────────────────────────► Queue        O(1)
├─ ต้องการมากสุด/น้อยสุดซ้ำ ๆ ────────────────────────► Heap        O(log n)
├─ เข้าถึงด้วยดัชนีตัวเลข ขนาดคงที่ ───────────────────► Array       O(1)
└─ เพิ่ม/ลบที่ปลายบ่อย ไม่ค่อยเข้าถึงกลาง ─────────────► Linked List O(1) ที่ปลาย

เคล็ดลับ: ถ้าตอบได้มากกว่าหนึ่งข้อ (เช่น ต้องทั้งค้นด้วยกุญแจ และ เรียงลำดับ) มักแปลว่าคุณต้องใช้ สองโครงสร้างร่วมกัน เช่น dict คู่กับ heap — อย่ากลัวที่จะผสม

ตารางการตัดสินใจตาม “รูปแบบการเข้าถึง”

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

รูปแบบการเข้าถึง (access pattern)	ตัวอย่างคำถามในโค้ด	โครงสร้างที่เหมาะ	ต้นทุน
Random access ด้วยดัชนี	“ตัวที่ 5000 คือค่าอะไร”	Array	O(1)
Ordered iteration (เรียงลำดับ)	“ไล่ทุกตัวจากน้อยไปมาก”	BST สมดุล / Array ที่เรียงแล้ว	O(n) ไล่ทั้งหมด, O(log n) ต่อการแทรก
Membership test (มี/ไม่มี)	“ค่านี้เคยเห็นหรือยัง”	Hash Set	O(1) เฉลี่ย
FIFO (เข้าก่อนออกก่อน)	“ใครมาก่อนได้บริการก่อน”	Queue / deque	O(1)
LIFO (เข้าหลังออกก่อน)	“ย้อนกลับการกระทำล่าสุด”	Stack	O(1)
Min / Max ซ้ำ ๆ	“ใครสำคัญที่สุดตอนนี้”	Heap (priority queue)	O(log n)
Prefix / Range query	“ทุกค่าระหว่าง 100–500”	BST สมดุล (หรือ Trie ถ้าเป็น string prefix)	O(log n + k)

ตารางเปรียบเทียบต้นทุนการดำเนินการ

โครงสร้าง	เข้าถึง (access)	ค้นหา (search)	เพิ่ม (insert)	ลบ (delete)	เรียงลำดับ?	ใช้ทำอะไรทั่วไป
Array (อาเรย์)	O(1)	O(n)	O(n)	O(n)	ไม่ (ตามที่ใส่)	เข้าถึงด้วยดัชนี, ข้อมูลขนาดคงที่
Linked List (ลิงก์ลิสต์)	O(n)	O(n)	O(1)*	O(1)*	ไม่	เพิ่ม/ลบที่ปลายบ่อย ๆ
Stack (สแตก)	O(n)	O(n)	O(1)	O(1)	ไม่ (LIFO)	undo, ย้อนกลับ, ตรวจวงเล็บ
Queue (คิว)	O(n)	O(n)	O(1)	O(1)	ไม่ (FIFO)	คิวงาน, BFS, บัฟเฟอร์
Hash Table (ตารางแฮช)	—	O(1) เฉลี่ย	O(1) เฉลี่ย	O(1) เฉลี่ย	ไม่	ค้นด้วยกุญแจ, นับความถี่, แคช, membership test
BST (สมดุล)	O(log n)	O(log n)	O(log n)	O(log n)	ใช่	เรียงลำดับตลอด, ถามช่วงค่า, min/max
Heap (ฮีป)	O(n)**	O(n)	O(log n)	O(log n)***	ไม่ (แค่รากรับประกัน)	ดึงค่ามากสุด/น้อยสุดซ้ำ ๆ, priority queue

* ลิงก์ลิสต์เพิ่ม/ลบเป็น O(1) ก็ต่อเมื่อ “มีตัวชี้ไปยังตำแหน่งนั้นอยู่แล้ว” ถ้าต้องไล่หาตำแหน่งก่อนจะเป็น O(n)

** Heap เข้าถึง “ค่าที่รากเท่านั้น” (min หรือ max) ได้ใน O(1) แต่เข้าถึงตัวอื่นต้องไล่ O(n) — heap ไม่รับประกันลำดับของตัวที่เหลือ

*** หมายถึงการลบตัวที่รากออก (heappop) เท่านั้น การลบตัวที่อยู่ตรงกลางฮีปโดยรู้แค่ค่ายังต้องค้นก่อนซึ่งเป็น O(n)

“เรียงลำดับ?” หมายถึงโครงสร้างนั้นรักษาลำดับการเรียงให้โดยอัตโนมัติหรือไม่ — ตารางแฮชไม่รับประกันลำดับใด ๆ ส่วน BST ให้ลำดับเรียงได้ฟรี ส่วน heap รับประกันแค่ว่า “รากคือสุดขั้ว” เท่านั้น ไม่ใช่ทั้งกอง

ลองเล่นกับตารางแฮชด้านล่าง สังเกตว่าเมื่อใส่ข้อมูลมากเกินขนาดตาราง จะเกิด collision (ชนกันในช่องเดียว) ซึ่งเป็นเหตุผลที่ตารางแฮชในโลกจริงต้องขยายขนาดเป็นระยะ:

และลองเทียบกับลิงก์ลิสต์ — สังเกตว่า prepend (เพิ่มที่หัว) เร็วคงที่ แต่ append (เพิ่มที่ท้าย) หรือเข้าถึงกลางลิสต์ต้องไล่ทีละโหนด:

หกสถานการณ์

1. กระดานคะแนน (leaderboard) ที่ต้องแสดงอันดับเรียงจากมากไปน้อยตลอดเวลา งานหลักคือ “ดึงค่ามากสุด” และ “คงลำดับเรียง” ขณะที่คะแนนเปลี่ยนตลอด → ใช้ โครงสร้างที่เรียงลำดับ เช่น BST สมดุล (หรือ heap ถ้าต้องการแค่ค่าสูงสุด) แทรกคะแนนใหม่และอ่านลำดับได้ใน O(log n) ส่วนการเรียง list ใหม่ทุกครั้งจะเป็น O(n log n) ต่อรอบ — ช้าเกินไป

2. ประวัติการ undo ในโปรแกรมแก้ไขข้อความ ทุกครั้งที่ผู้ใช้กด undo เราต้องการ “การกระทำล่าสุด” ก่อนเสมอ — นี่คือ LIFO → ใช้ สแตก (Stack) push ทุกการกระทำ แล้ว pop ตัวบนสุดเมื่อ undo ทั้งคู่เป็น O(1)

3. ค้นเบอร์โทรจากสมุดโทรศัพท์ด้วยชื่อ งานหลักคือ “ให้ชื่อ → คืนเบอร์” ด้วยความเร็วสูงสุด และไม่สนลำดับ → ใช้ ตารางแฮช (Hash Table / dict) ค้นด้วยกุญแจได้ O(1) โดยเฉลี่ย ส่วนการไล่หาทีละคนใน list เป็น O(n)

4. แคชของ “รายการที่เพิ่งเปิดล่าสุด” (recent items) ที่เก็บได้จำกัด N รายการ งานหลักคือ “เพิ่มตัวใหม่ที่ปลายหนึ่ง และทิ้งตัวเก่าสุดที่อีกปลาย” — เข้า–ออกคนละด้าน คือ FIFO → ใช้ คิว (Queue) โดยเฉพาะ deque ที่เพิ่ม/ลบสองปลายได้ O(1) (ใน Python คือ collections.deque(maxlen=N) ที่ทิ้งตัวเก่าให้เองอัตโนมัติ) ลองดูพฤติกรรม FIFO ในวิดเจ็ตนี้:

5. เว็บอีคอมเมิร์ซที่ต้องถามบ่อยว่า “สินค้าราคาระหว่าง 100–500 บาทมีอะไรบ้าง” งานหลักคือ range query บนค่าตัวเลข → ใช้ BST สมดุล (หรือ sorted array ถ้าข้อมูลนิ่งไม่ค่อยเปลี่ยน) ไล่หาขอบเขตล่าง-บนได้ใน O(log n) แล้วเก็บตัวที่อยู่ในช่วงอีก O(k) ตัว รวม O(log n + k) ตารางแฮชทำแบบนี้ไม่ได้เลยเพราะไม่มีลำดับให้ไล่

6. ระบบตรวจจับ “ผู้ใช้ที่เคยลงทะเบียนซ้ำ” จาก user ID ที่ไหลเข้ามาเป็นล้าน ๆ รายการ งานหลักคือ membership test: “ID นี้เคยเห็นมาก่อนหรือยัง” ล้วน ๆ ไม่สนลำดับ ไม่สนค่าอื่นเลย → ใช้ Hash Set (เช่น set() ใน Python) ตรวจสอบได้ O(1) โดยเฉลี่ยต่อรายการ ถ้าใช้ list แล้ว in จะเป็น O(n) ต่อการตรวจหนึ่งครั้ง — ล้านรายการก็กลายเป็น O(n²) ทันที

โจทย์จากโลกจริง

ระบบจัดคิวงานพิมพ์ตามลำดับความสำคัญ (priority print queue)

โจทย์: เครื่องพิมพ์ในออฟฟิศรับงานเข้ามาเรื่อย ๆ แต่ละงานมี “ระดับความสำคัญ” งานสำคัญต้องได้พิมพ์ก่อนเสมอ ไม่ว่ามาถึงทีหลังหรือไม่

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

โครงสร้างที่ถูก (แต่ไม่ชัดเจนในทันที): สิ่งที่เราทำบ่อยที่สุดมีแค่สองอย่าง — “เพิ่มงานใหม่” และ “ดึงงานสำคัญสุดออก” เราไม่เคยต้องการให้ “ทุกตัวเรียงครบ” เลย เราต้องการแค่ตัวที่สำคัญที่สุดตัวเดียว → คำตอบคือ ฮีป (Heap / priority queue) ซึ่งเพิ่มงานและดึงตัวสำคัญสุดได้ใน O(log n) โดยไม่ต้องเรียงทั้งกอง

import heapq

pq = []
heapq.heappush(pq, (1, "พิมพ์สลิป"))      # (ความสำคัญ, งาน) — O(log n)
heapq.heappush(pq, (5, "พิมพ์สัญญาด่วน"))
heapq.heappush(pq, (3, "พิมพ์รายงาน"))

# ดึงงานสำคัญสุด (เลขน้อย = สำคัญสุดใน min-heap) — O(log n)
print(heapq.heappop(pq))   # (1, 'พิมพ์สลิป')

บทเรียน: เมื่อคุณ “ต้องการตัวสุดขั้วเพียงตัวเดียวซ้ำ ๆ” (มากสุด/น้อยสุด) อย่ารีบเรียงทั้งกอง — heap ให้สิ่งที่คุณต้องการพอดี ด้วยราคาที่ถูกกว่ามาก

ข้อควรระวัง: heap ไม่ใช่ทางเลือกที่ดีถ้าคุณต้องการ “ไล่ทุกตัวตามลำดับ” บ่อย ๆ (นั่นคืองานของ BST หรือ sorted list) heap เก่งแค่ “สุดขั้วตัวเดียว ครั้งแล้วครั้งเล่า”

แบบฝึกหัด

ตอบว่าใช้โครงสร้างใด และ เพราะอะไร (ดูจากการดำเนินการที่บ่อยที่สุด)

1. ระบบตรวจว่าวงเล็บ ()[]{} ในโค้ดเปิด-ปิดถูกคู่กันหรือไม่ ควรใช้โครงสร้างใด?

เฉลย

สแตก (Stack) — เมื่อเจอวงเล็บเปิดให้ push เมื่อเจอวงเล็บปิดให้ pop ตัวบนสุดมาตรวจว่าเข้าคู่กันไหม เราสนแค่ “ตัวที่เปิดล่าสุด” เสมอ ซึ่งเป็นพฤติกรรม LIFO push/pop เป็น O(1)

2. เก็บรายชื่อนักศึกษาพร้อมรหัส และต้องค้น “รหัสนี้คือใคร” บ่อยมากแบบสุ่ม ควรใช้โครงสร้างใด?

เฉลย

ตารางแฮช (Hash Table / dict) ที่ใช้รหัสเป็นกุญแจ ค้นด้วยกุญแจได้ O(1) โดยเฉลี่ย ไม่ต้องสนลำดับ การไล่หาใน list จะเป็น O(n) ต่อการค้นหนึ่งครั้ง

3. ระบบจองคิวร้านอาหาร ใครมาก่อนได้ก่อน ควรใช้โครงสร้างใด?

เฉลย

คิว (Queue) — มาก่อนได้ก่อนคือ FIFO เพิ่มลูกค้าที่ท้ายแถวและเรียกลูกค้าที่หัวแถว ทั้งคู่เป็น O(1) (ใช้ collections.deque)

4. ต้องเก็บอุณหภูมิรายชั่วโมงทั้งปี และมักถามว่า “ค่าที่ดัชนีชั่วโมงที่ 5000 คือเท่าไร” ควรใช้โครงสร้างใด?

เฉลย

อาเรย์ (Array / list) — การเข้าถึงด้วยดัชนีตัวเลขเป็น O(1) และข้อมูลมีขนาดค่อนข้างคงที่ ไม่จำเป็นต้องใช้โครงสร้างที่ซับซ้อนกว่านี้

5. ต้องเก็บราคาสินค้าและถามบ่อยว่า “สินค้าทั้งหมดที่ราคาอยู่ระหว่าง 100–500 บาทมีอะไรบ้าง” ควรใช้โครงสร้างใด?

เฉลย

BST ที่สมดุล (หรือโครงสร้างที่เรียงลำดับ) เพราะการถาม “ช่วงของค่า (range query)” ทำได้มีประสิทธิภาพบนข้อมูลที่เรียงอยู่แล้ว O(log n + k) เมื่อ k คือจำนวนผลลัพธ์ ตารางแฮชทำไม่ได้เพราะไม่รักษาลำดับ

6. โค้ดต่อไปนี้ตรวจว่า user ID ซ้ำหรือไม่ในสตรีมข้อมูล 1 ล้านรายการ:

seen = []

def is_duplicate(user_id):
    if user_id in seen:      # ?
        return True
    seen.append(user_id)
    return False

ความซับซ้อนรวมของการประมวลผลทั้งสตรีมคือเท่าไร และจะแก้ให้เร็วขึ้นอย่างไร?

เฉลย

user_id in seen บน list เป็น O(n) เพราะต้องไล่ทีละตัว เมื่อเรียกซ้ำ n ครั้งกับ list ที่โตขึ้นเรื่อย ๆ รวมทั้งหมดจะกลายเป็น O(n²) — กับ 1 ล้านรายการคือช้ามาก

แก้ได้โดยเปลี่ยน seen จาก list เป็น set (Hash Set):

seen = set()

def is_duplicate(user_id):
    if user_id in seen:      # O(1) เฉลี่ย
        return True
    seen.add(user_id)        # O(1) เฉลี่ย
    return False

ตอนนี้ทั้งสตรีมรวมเป็น O(n) เพราะงานหลักคือ membership test ซึ่งเป็นงานถนัดของ hash set โดยตรง

7. ต้องสร้างปุ่ม “ย้อนกลับ” และ “ไปข้างหน้า” (back/forward) แบบเดียวกับเบราว์เซอร์ ในหน้าประวัติการเข้าเว็บ ควรใช้โครงสร้างใด?

เฉลย

สแตกสองอัน — อันหนึ่งเก็บประวัติ “ย้อนกลับได้” อีกอันเก็บประวัติ “ไปข้างหน้าได้” เมื่อกด back ให้ pop จากสแตกแรกแล้ว push เข้าสแตกที่สอง (และกลับกันเมื่อกด forward) เป็นรูปแบบ LIFO สองทิศทาง push/pop ทั้งหมด O(1)

8. ทำนายผลลัพธ์ของโค้ดนี้ (โดยไม่รันจริง):

import heapq

pq = []
for value in [7, 2, 9, 1, 5]:
    heapq.heappush(pq, value)

result = []
while pq:
    result.append(heapq.heappop(pq))

print(result)

เฉลย

[1, 2, 5, 7, 9]

heapq ใน Python เป็น min-heap โดยดีฟอลต์ — ไม่ว่าจะ push ตามลำดับใด heappop จะดึงค่าน้อยที่สุดที่เหลืออยู่ออกมาเสมอทีละตัว ดังนั้นการ push แล้ว pop ทั้งหมดจึงเท่ากับการเรียงจากน้อยไปมาก (แต่ทำแบบนี้เพื่อ “เรียง” ทั้งลิสต์ไม่คุ้ม — ถ้าต้องการแค่เรียง ใช้ sorted() ซึ่งเป็น O(n log n) เหมือนกันแต่ตรงไปตรงมากว่า จุดแข็งจริงของ heap คือกรณีที่ข้อมูลไหลเข้ามาเรื่อย ๆ แล้วต้องดึง “ตัวน้อยสุดตอนนี้” สลับกับการเพิ่มตัวใหม่)

วิพากษ์โค้ดจากปัญญาประดิษฐ์

คุณขอให้ AI ทำระบบ “นับโหวต” ที่ต้องคืน “ตัวเลือกที่ได้คะแนนสูงสุด” ตลอดเวลา AI ตอบกลับมาว่า:

votes = []   # เก็บเป็นลิสต์ของชื่อตัวเลือก

def add_vote(choice):
    votes.append(choice)

def winner():
    # นับมือทุกครั้งที่ถามผู้ชนะ
    counts = {}
    for v in votes:               # O(n)
        counts[v] = counts.get(v, 0) + 1
    best = None
    for choice, c in counts.items():   # O(m)
        if best is None or c > counts[best]:
            best = choice
    return best

ลองตัดสิน: AI ใช้ list ดิบเก็บโหวตทุกใบ แล้วต้องนับใหม่ทั้งหมดทุกครั้งที่ถามผู้ชนะ — ถ้ามีโหวตล้านใบและถามผู้ชนะบ่อย ๆ จะเป็น O(n) ต่อการถามหนึ่งครั้ง การดำเนินการที่บ่อยที่สุดคือ “เพิ่มโหวต” และ “ถามผู้ชนะ” เราควรเก็บ จำนวนนับ ไว้ใน dict ตั้งแต่แรก ไม่ใช่เก็บโหวตดิบ จงเขียนใหม่ให้การถามผู้ชนะเร็วขึ้น

เฉลย

import heapq
from collections import Counter

counts = Counter()    # ตัวเลือก -> จำนวนโหวต

def add_vote(choice):
    counts[choice] += 1        # O(1)

def winner():
    return counts.most_common(1)[0][0]   # คืนตัวที่มากสุด

ใช้ Counter (ซึ่งคือ dict) เก็บจำนวนนับโดยตรง การเพิ่มโหวตเป็น O(1) ไม่ต้องเก็บโหวตดิบทุกใบอีกต่อไป

ถ้าต้องถาม “ผู้ชนะ” ถี่มากจนแม้แต่การไล่หาตัวมากสุดยังแพง ให้เพิ่ม heap (priority queue) ควบคู่กับ dict เพื่อให้ดึงตัวสูงสุดเป็น O(log n) — นี่คือกรณีที่ list เดี่ยว ๆ ผิด แต่ dict (และอาจ heap) คือคำตอบที่ถูก

🎮 เกมเดฟ: การเลือกโครงสร้างข้อมูลให้เหมาะกับระบบเกม

เกมหนึ่งเกมถามคำถามหลักของบทเรียนนี้ซ้ำนับสิบครั้งต่อเฟรม — อินเวนทอรี, การตรวจการชนกัน, ลำดับการผลัดตา (turn order), คูลดาวน์ของสกิล, และระบบ undo/rewind ล้วนเป็นคำถามเดียวกันคือ “การดำเนินการไหนเกิดขึ้นบ่อยที่สุด” ที่ซ่อนอยู่ในคราบของระบบเกม ถ้าเลือกโครงสร้างผิด เกมที่รันลื่นตอนมี entity แค่ 10 ตัว จะสะดุดทันทีที่มี 500 ตัว — ไม่ใช่เพราะ logic ผิด แต่เพราะชั้นข้อมูล (data layer) ถูกปรับให้เหมาะกับรูปแบบการเข้าถึงที่ผิดตั้งแต่แรก

ตัวอย่างจากของจริง: ลำดับการผลัดตา + การค้นหา entity ด้วย id ในเกมแทกติก

เกมแทกติกต้องการสองอย่างทุกรอบ: “ใครผลัดตาต่อไป” (เรียงตามความเร็ว/initiative) และ “ขอยูนิตที่มี ID นี้” (เพื่อลงดาเมจ ตรวจสถานะ ฯลฯ) วิธีไร้เดียงสาคือยัดทั้งสองอย่างลงใน list เดียว:

import heapq


class Unit:
    def __init__(self, unit_id: str, name: str, speed: int) -> None:
        self.id: str = unit_id
        self.name: str = name
        self.speed: int = speed


units: dict[str, Unit] = {
    "u1": Unit("u1", "อัศวิน", speed=8),
    "u2": Unit("u2", "โจร", speed=14),
    "u3": Unit("u3", "นักเวท", speed=11),
}

# ไร้เดียงสา: list ธรรมดา เรียงใหม่ทุกรอบ — O(n log n) ต่อรอบ
turn_list: list[Unit] = list(units.values())


def naive_next_turn() -> Unit:
    turn_list.sort(key=lambda u: -u.speed)   # เรียงใหม่ "ทั้งลิสต์" ทุกครั้ง
    return turn_list[0]


# ทางแก้ที่สเกลได้: heap คีย์ด้วยความเร็ว — insert/extract O(log n) ไม่ต้องเรียงใหม่ทั้งหมด
turn_heap: list[tuple[int, str]] = []
for u in units.values():
    heapq.heappush(turn_heap, (-u.speed, u.id))


def next_turn() -> Unit:
    neg_speed, unit_id = heapq.heappop(turn_heap)
    acting: Unit = units[unit_id]                    # ค้นด้วย id: dict lookup — O(1)
    heapq.heappush(turn_heap, (neg_speed, unit_id))   # ใส่กลับคิวสำหรับรอบถัดไป
    return acting


print(next_turn().name)   # โจร (ความเร็ว 14 ได้ตาก่อน)

dict ตอบคำถาม “ขอยูนิต u3” ได้ใน O(1) — ตรงกับรูปแบบการเข้าถึงที่ทุกระบบอื่น (ดาเมจ, แอนิเมชัน, UI) ต้องการพอดี ส่วน heap ตอบคำถาม “ตอนนี้ใครเร็วที่สุด” ได้ใน O(log n) โดยไม่ต้องเรียง roster ทั้งหมดเลย ในขณะที่เวอร์ชัน list ไร้เดียงสาต้องจ่าย O(n log n) ทุก ๆ รอบ ซึ่งโอเคกับ 4 ยูนิต แต่หายนะกับ 40 ยูนิต

ลองเพิ่มยูนิตที่มีความเร็วต่างกันด้านบนดู — คิวจะจัดลำดับใหม่ตามความสำคัญเอง เหมือนกับ heap ในโค้ดทุกประการ

อินเวนทอรี (UI ช่องไอเทม) List แสดง 20 ช่องตามลำดับ

อินเวนทอรี (เช็คของคราฟต์) Dict “มีแร่เหล็ก 3 ชิ้นไหม?”

คิวรีเชิงพื้นที่ (การชนกัน) Grid / Quadtree “ใครอยู่ใกล้ (x, y)?”

ลำดับการผลัดตา Heap “ใครผลัดตาต่อไป?”

ค้นหา entity ด้วย id Dict “ขอ entity #482”

คูลดาวน์ Heap “อะไรพร้อมใช้ต่อไป?”

Undo / ย้อนเวลา Stack “ย้อนการเดินล่าสุด”

รูป: เจ็ดระบบในเกม โครงสร้างที่แต่ละระบบควรใช้ และรูปแบบการเข้าถึงที่เป็นตัวตัดสิน

สี่ระบบเพิ่มเติม สี่การตัดสินใจ

อินเวนทอรี — list หรือ dict. กริดอุปกรณ์ 20 ช่องที่ต้องแสดงช่องตามลำดับคงที่ควรใช้ list (ดัชนี i คือช่อง i, O(1)) แต่คำถาม “ผู้เล่นมี Health Potion ไหม” หรือ “มีแร่เหล็กกี่ชิ้น” ควรใช้ dict คีย์ด้วย item id — ค้นหาได้ O(1) แทนที่จะไล่ทุกช่อง อินเวนทอรีจริงส่วนใหญ่ใช้ทั้งคู่ร่วมกัน: list[Optional[Item]] สำหรับกริด UI และ dict[str, int] สำหรับนับทรัพยากรที่ซ้อนกันได้ (stackable)

คิวรีเชิงพื้นที่ — grid หรือ quadtree. คำถาม “ศัตรูตัวไหนอยู่ในระยะประชิดผู้เล่น” ถ้าทำแบบไร้เดียงสาคือ “เช็คทุกคู่” ซึ่งเป็น O(n²) — โอเคกับ 10 ตัว แต่หายนะกับ 500 ตัว spatial hash grid จะแบ่ง entity ตาม (x // cell_size, y // cell_size) ทำให้คิวรีตรวจแค่ entity หยิบมือเดียวในเซลล์ใกล้เคียง quadtree ทำหน้าที่เดียวกันแต่รองรับความหนาแน่นไม่เท่ากัน (พื้นที่แออัดจะแบ่งย่อยลงไปอีก)

ลองสลับระหว่างโหมด brute-force กับ grid ด้านบน — entity ชุดเดียวกัน คิวรีเดียวกัน แต่งานต่อเฟรมต่างกันมาก

คูลดาวน์ — heap เมื่อมีสกิลเยอะพอ. ถ้ามีสกิลผู้เล่นแค่ 3-4 ตัว เก็บ ability -> ready_at_time ไว้ใน dict แล้วเช็คทุกตัวทุกเฟรมก็พอ — O(1) ต่อสกิล เร็วพอ ๆ กันทั้งสองแบบ แต่เกมที่มีตัวจับเวลาพร้อมกันหลายสิบตัว (เช่น status effect ของ 50 ยูนิต) จะได้ประโยชน์จาก heap คีย์ด้วย ready_at_time: “อะไรจะหมดอายุต่อไป” เป็น O(log n) แทนที่จะไล่ตัวจับเวลาทุกตัวทุกเฟรม

dict ที่อยู่เบื้องหลังการค้นหา entity ด้วย id และตารางคูลดาวน์ขนาดเล็ก — ลองดูว่าเกิดอะไรขึ้นเมื่อใส่ข้อมูลเกินจำนวนช่อง

Undo — stack เหมือนเดิมทุกที่. ฟีเจอร์ “ย้อนการเดินล่าสุด” ของเกมปริศนาก็เหมือนกับ undo ของโปรแกรมแก้ไขข้อความในบทเรียนนี้ทุกประการ: push สแนปช็อตของการเดินก่อนจะทำจริง แล้ว pop กับคืนค่าตอนย้อน เป็น LIFO, O(1) ไม่มีอะไรเฉพาะเกมเลยสักนิด — ซึ่งนั่นแหละคือบทเรียน: รูปแบบ (pattern) ย้ายข้ามโดเมนได้แม้เนื้อหาจะเปลี่ยนไป

แบบฝึกหัด

ดูฟีเจอร์เกมและรูปแบบการเข้าถึง แล้วเลือกโครงสร้างพร้อมให้เหตุผล

1. เกมโรกไลก์ต้องแสดงไอเทมในกริด UI ตามลำดับที่เก็บมา และต้องตอบทันทีว่า “มีกุญแจสำหรับประตูนี้ไหม” ควรใช้โครงสร้างใด (อาจมากกว่าหนึ่ง)?

เฉลย

ใช้ทั้งคู่ร่วมกัน: list สำหรับกริด UI ที่ต้องคงลำดับช่อง (เข้าถึงด้วยดัชนี O(1)) และ dict คีย์ด้วยประเภทไอเทมสำหรับเช็คว่ามีไอเทมประเภทนี้ไหม (O(1) แทนที่จะไล่ทุกช่องซึ่งเป็น O(n)) นี่คือตัวอย่างของ “ผสมสองโครงสร้างเข้าด้วยกัน” ตามเคล็ดลับในบทเรียนหลัก

2. เกมยิงแบบ bullet-hell มีกระสุนศัตรู 300 นัด และฮิตบ็อกซ์ผู้เล่น 1 อัน ต้องตรวจการชนทุกเฟรม ฟีเจอร์คือ “กระสุนนัดไหนซ้อนทับฮิตบ็อกซ์ผู้เล่นในเฟรมนี้” ควรใช้โครงสร้างใดและเพราะอะไร?

เฉลย

Spatial hash grid — แบ่งกระสุนตามเซลล์ แล้วคิวรีแค่เซลล์ที่ผู้เล่นอยู่กับเซลล์ข้างเคียง ได้ O(1) โดยเฉลี่ยต่อเฟรม แทนที่จะไล่เช็คกระสุนทั้ง 300 นัดทุกเฟรมซึ่งเป็น O(n) (หรือ O(n²) ถ้าต้องเช็คกระสุนชนกันเองด้วย)

3. เกม RPG แบบผลัดตา มีคาถา “เร่งความเร็ว (haste)” ที่เปลี่ยนความเร็วของยูนิตกลางการต่อสู้ ทำให้ต้องจัดลำดับ turn queue ของยูนิตนั้นใหม่ทันที ถ้าใช้ heap เป็นตัวจัดลำดับผลัดตาอยู่แล้ว จุดติดขัดคืออะไร และแก้อย่างไร?

เฉลย

Heap มาตรฐานไม่รองรับการ “ลด priority ของสมาชิกที่อยู่ในกองอยู่แล้ว” (decrease-key) อย่างมีประสิทธิภาพ — ต้องไล่หาตำแหน่งก่อนซึ่งเป็น O(n) วิธีแก้ที่นิยมคือ lazy deletion: push รายการใหม่ที่มี priority อัปเดตแล้วเข้าไปตรง ๆ (O(log n)) แล้วเก็บ “ค่าความเร็วปัจจุบัน” ของแต่ละยูนิตไว้ใน dict แยกต่างหาก เมื่อ pop รายการเก่าที่ค่าไม่ตรงกับ dict ออกมา ให้ทิ้งมันไปเงียบ ๆ แล้ว pop ตัวถัดไป (ถือว่าเป็นข้อมูลล้าสมัยแล้ว) แทนที่จะพยายามแก้ heap กลางกอง

4. เกม RPG มีตัวจับเวลาสถานะ (status effect) พร้อมกันถึง 40 ตัวทั่วสนามรบ (พิษ, ไฟไหม้, มึนงง ฯลฯ) และต้องรู้ทุกเฟรมว่า “สถานะตัวไหนจะหมดอายุต่อไป” โดยไม่ไล่เช็คทั้ง 40 ตัว ควรใช้โครงสร้างใด?

เฉลย

Heap (priority queue) คีย์ด้วยเวลาหมดอายุ (expiry time) — insert เป็น O(log n) และ peek/pop ตัวที่จะหมดอายุเร็วที่สุดก็เป็น O(log n) เหมือนกันทุกประการกับระบบคิวงานพิมพ์ตามลำดับความสำคัญในบทเรียนหลัก ต่างกันแค่ “priority” ในที่นี้คือเวลาแทนระดับความสำคัญ

โจทย์ท้าทาย

โจทย์ 1: ออกแบบชั้นข้อมูลสำหรับเกมเอาชีวิตรอดมุมมองบนลงล่างขนาดเล็ก

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

แนวทาง

• Hotbar (5 ช่อง): list ขนาดคงที่ — ต้องคงลำดับและเข้าถึงด้วยดัชนี O(1)
• จำนวนไอเทมสะสม: dict[str, int] คีย์ด้วยชนิดไอเทม — เช็ค/เพิ่ม/ลดจำนวนได้ O(1) โดยไม่สนลำดับ
• ศัตรูในระยะ 200 พิกเซล: spatial hash grid ที่แบ่งเซลล์ตามขนาดใกล้เคียงระยะแอคทิเวต แล้วคิวรีแค่เซลล์รอบผู้เล่น — ไล่เช็คศัตรูเป็นร้อยตัวทุกเฟรมแบบ O(n) จะเริ่มหน่วงเมื่อจำนวนเพิ่มขึ้น grid ทำให้เหลือแค่ไม่กี่สิบตัวต่อคิวรี
• ย้อนเวลา 10 วินาที: ไม่ใช่ stack ไม่จำกัดขนาด แต่เป็น deque ที่จำกัดความยาว (collections.deque(maxlen=600) ที่ 60 เฟรมต่อวินาที) เก็บสแนปช็อตสถานะทุกเฟรม เมื่อเต็มแล้วตัวเก่าสุดจะถูกทิ้งอัตโนมัติ — เป็น LIFO/FIFO ผสมที่มีเพดานหน่วยความจำแน่นอน

โจทย์ 2: กริดเชิงพื้นที่คุ้มไหมสำหรับเกมต่อสู้ (fighting game)?

โจทย์: ระบบฮิตบ็อกซ์ของเกมต่อสู้ต้องหาการซ้อนทับระหว่างฮิตบ็อกซ์ผู้โจมตีกับฮิตบ็อกซ์รับของตัวละครสูงสุด 8 ตัวบนจอ แต่ละตัวอาจมีฮิตบ็อกซ์ที่แอคทีฟพร้อมกันหลายอันระหว่างเฟรมของท่าโจมตี ควรสร้าง spatial hash grid สำหรับกรณีนี้ไหม หรือ brute-force ก็เพียงพอ? จงให้เหตุผลด้วยตัวเลข n

แนวทาง

ด้วย n ≤ 8 ตัวละคร และประมาณ 3 ฮิตบ็อกซ์ต่อตัว รวมประมาณ 24 กล่อง การเช็คทุกคู่แบบ brute-force คือประมาณ 24²/2 ≈ 276 การเปรียบเทียบต่อเฟรม — เร็วในระดับไมโครวินาที ไม่มีทางเป็นคอขวดที่ 60 เฟรมต่อวินาที ในขณะที่การสร้างและดูแล spatial grid มีต้นทุนจัดการเซลล์ (bucket) ที่ยังไม่คุ้มจนกว่า n จะโตขึ้นไปถึงหลักร้อย

กฎง่าย ๆ: ใช้ grid เมื่อ n โตพอที่ O(n²) จะโผล่มาให้เห็นจริงในโปรไฟเลอร์ สำหรับ roster ขนาดเล็กคงที่ของเกมต่อสู้ nested loop แบบ O(n²) ตรงไปตรงมาคือคำตอบที่ถูกต้องและไม่หรูหรา — บทเรียนเดียวกับที่คอร์สนี้ย้ำเสมอ: อย่า over-engineer เมื่อไม่จำเป็น

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

• MIT 6.006 — Introduction to Algorithms บทเรียนเปิดเรื่อง “Algorithmic Thinking, Peak Finding” และซีรีส์เรื่องโครงสร้างข้อมูล (เผยแพร่ฟรีบน MIT OpenCourseWare)
• Stanford CS161 — Design and Analysis of Algorithms หัวข้อการเลือกโครงสร้างข้อมูลและการวิเคราะห์ความซับซ้อน
• Skiena — The Algorithm Design Manual (3rd ed.) บทที่ 3 “Data Structures” — หนังสือที่เขียนกรอบ “เลือกเทคนิคไหนตอนไหน” ได้ดีที่สุดในบรรดาตำราทั้งหมด พร้อมสารบัญท้ายเล่มแบบ “war story” ที่เทียบโครงสร้างข้อมูลตามการใช้งานจริง — เหมาะกับบทเรียนนี้โดยตรง
• CLRS — Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) ส่วนที่ III “Data Structures” อธิบายการพิสูจน์ความซับซ้อนอย่างเข้มงวดของแต่ละโครงสร้าง
• Sedgewick & Wayne — Algorithms (4th ed.) บทที่ 3–4 มีโค้ด Java implementation ของทุกโครงสร้างในตารางนี้ พร้อมการทดลองวัดผลจริงเทียบกับทฤษฎี
• Big-O Cheat Sheet ที่ bigocheatsheet.com — ตารางเปรียบเทียบความซับซ้อนของโครงสร้างข้อมูลทุกตัวในที่เดียว