ที่เก็บข้อมูลมาตรฐาน และตัวอย่าง 15-puzzle

นึกภาพก่อน

ถุง กล่องแบ่งช่อง และแถวคอยคิว เก็บของได้เหมือนกัน แต่หยิบของออกมาได้ไม่เหมือนกัน ถุงหยิบอะไรออกมาก็ได้ไม่มีลำดับ กล่องแบ่งช่องบอกได้ว่าของชิ้นที่สามคืออะไร ส่วนแถวคอยต้องให้คนแรกออกก่อน

ที่เก็บข้อมูลในโปรแกรมก็เช่นกัน การออกแบบโครงสร้างข้อมูลให้ตรงงานต้องเริ่มจากรู้จักรูปแบบพื้นฐานก่อน

ชนิดของข้อมูล

ข้อมูลพื้นฐาน: int, double, char, boolean
คลาสมาตรฐานในคลัง: String, Color, BigDecimal, ArrayList, HashMap
ออกแบบและสร้างเอง: สิ่งที่วิชานี้สอน

ที่เก็บข้อมูลพื้นฐาน 5 แบบ

ที่เก็บ	อันดับ	ข้อมูลซ้ำ	ลักษณะ
Collection	ไม่มี	ซ้ำได้	กลุ่มของข้อมูล
Set	ไม่มี	ซ้ำไม่ได้	เซต
List	มี	ซ้ำได้	รายการ แต่ละตัวมีตำแหน่ง
Stack	เรียงซ้อน	ซ้ำได้	LIFO เข้าหลังออกก่อน
Queue	เรียงตามลำดับเข้า	ซ้ำได้	FIFO เข้าก่อนออกก่อน

วิธีสร้างที่เก็บ

ที่เก็บแบบเดียวกันสร้างได้หลายวิธี:

Array (อาเรย์)
Linked list (รายการโยง)
Tree (ต้นไม้)
Hash table (ตารางแฮช)
อื่น ๆ เช่น graph

ดังนั้นมีสองคำถามที่แยกกัน: จะใช้ที่เก็บ แบบไหน (บริการที่ต้องการ) และจะ สร้างด้วยอะไร (ความเร็วและเนื้อที่) ชื่อคลาสใน Java บอกทั้งสองอย่าง เช่น ArrayList = List ที่สร้างด้วยอาเรย์, LinkedList = List ที่สร้างด้วยการโยง, HashSet และ TreeSet = Set ที่สร้างด้วยตารางแฮชและต้นไม้

วิชานี้ใช้รูปแบบเดียวกัน:

บท	ที่เก็บ	คลาสที่สร้าง
2	Collection	ArrayCollection
3	Collection, Set	LinkedCollection, LinkedSet
4	List	ArrayList, SinglyLinkedList, LinkedList
5	Stack	ArrayStack, sLinkStack
6	Queue	ArrayListQueue, LinkedListQueue, ArrayQueue

โครงสร้างข้อมูลที่ดี

ให้บริการที่ต้องการได้ครบ
ใช้งานง่าย
ใช้เนื้อที่น้อย
ทำงานเร็ว

สองข้อหลังมักขัดกัน จึงต้องเลือกให้เหมาะกับงาน

ตัวอย่าง: 15-puzzle

เกมเลื่อนแผ่นตัวเลข 15 แผ่นในตาราง 4×4 ให้เรียงลำดับ โปรแกรมแก้ปัญหาแบบลองทุกทาง:

เริ่มจากตารางตั้งต้น ใส่ลงใน Queue
นำตารางออกจาก Queue ทีละตาราง ลองเลื่อนช่องว่าง 4 ทิศ ได้ตารางใหม่สูงสุด 4 แบบ
ใส่ตารางใหม่ต่อท้าย Queue แล้ววนทำจนพบตารางคำตอบ

Queue ทำให้ตารางที่เกิดก่อนถูกขยายก่อน จึงพบคำตอบที่ใช้จำนวนการเลื่อนน้อยที่สุด

ปัญหาคือ ตารางเดิมเกิดซ้ำได้หลายครั้ง (เลื่อนไปแล้วเลื่อนกลับ) จึงใช้ Set จำตารางที่เคยสร้างแล้ว:

java

if (!set.contains(b2)) {
  set.add(b2);
  queue.enqueue(b2);
}

วิธีสร้าง Set มีผลแค่ไหน

สไลด์ทดลองแก้โจทย์เดียวกันโดยเปลี่ยนเฉพาะคลาสที่ใช้สร้าง Set แล้วจับเวลา (วินาที):

จำนวนตารางที่สร้าง	ArraySet	BSTSet	AVLSet	HashSet
552	0.03	0.02	0.04	0.05
5,242	1.94	0.22	0.18	0.12
132,049	1819.6	7.08	5.71	2.56

ข้อมูลน้อยไม่ต่างกัน แต่เมื่อข้อมูลมากขึ้น ArraySet ใช้เวลาครึ่งชั่วโมง ขณะที่ HashSet ใช้ไม่ถึง 3 วินาที ทั้งที่โปรแกรมหลักเหมือนกันทุกบรรทัด เพราะ contains ของ ArraySet ต้องไล่ดูทีละตัว ยิ่งข้อมูลมากยิ่งช้า

จุดที่มักพลาด

1. สลับ Collection กับ Set

ทั้งคู่ไม่มีอันดับ ต่างกันที่ Set ห้ามซ้ำ

2. สลับ Collection กับ List

ทั้งคู่ซ้ำได้ ต่างกันที่ List มีอันดับ (มี index) จึงมีบริการ get(i), add(i, e) ซึ่ง Collection ไม่มี

3. คิดว่าชื่อที่เก็บบอกวิธีสร้าง

"List" บอกแค่บริการ จะสร้างด้วยอาเรย์หรือการโยงก็ได้

4. คิดว่าวิธีสร้างต่างกันแล้วผลลัพธ์ต่างกัน

ผลลัพธ์เหมือนกัน ต่างกันที่เวลาและเนื้อที่

ที่มา: COLLECTION_1_2n.pdf หน้า 1–23 และ STACK_5 (1).pdf หน้า 2–4 (ตารางสรุปเส้นทาง)