เเนวคิด Abstraction นํามา Implement Data Structure ยังไงกันนะ ?
Introduction
หลายคนคงสงสัยว่า เราในฐานะ Developer ที่ใช้ ภาษา Javascript บน Node environment สร้าง Web application ใช้งาน Tools ต่างๆ เช่น React, Express ทําไมจําเป็นจะต้องมาสนใจในเรื่อง Data structure เพราะ บางคนอาจจะไม่เคยเจอสถานการณ์ ที่จําเป็นจะต้องใช้ ต้องรู้ หรือถามตัวเองว่า จะเสียเวลาศึกษาดีไหม ?
Why Data structure ?
ในโลกของ Programming ให้ความสําคัญกับ เรื่องของ Data structure เพราะ Data structure เป็นวิธีการจัดเก็บข้อมูลในระดับพื้นฐานของ Program เพื่อให้สามารถใช้งานได้อย่างมีประสิทธิภาพ บ่อยครั้งที่การเลือก Data structure ที่เหมาะสม เป็นจุดเริ่มต้นของ Software ที่มีประสิทธิภาพ โดยบทความนี้จะบอกเล่าถึง Data structure ที่ถูกใช้ในสถาการณ์ต่างๆ ในโลกของความเป็นจริง ซึ่งจะ Focus ไปที่ Linear data structure พร้อมยกตัวอย่างประกอบเป็น Code ภาษา Typescript
Why Learn Data structure ?
- ก้าวเป็น Software Engineering ที่ดีขึ้น
- Data structure เป็นส่วนประกอบพื้นฐานสําคัญของ Algorithms ที่สําคัญ เเละ มีประโยชน์มากมาย เช่น เราคงไม่สามารถศึกษา เเละ เข้าใจ Path Finding, Dijkstra ถ้าไม่มีความรู้ เรื่อง Graph
- Technical interview ในการทดสอบ Technical interview จําเป็นจะต้องใช้ความรู้ในเรื่อง Data structure เพื่อผ่านบททดสอบ
Why Typescript ?
- Javascript อยู่ทุกที่ เเละเป็นส่วนสําคัญที่หลีกเลี่ยงไม่ได้ ใน Modern web application
- Typescript สามารถใช้พัฒนาได้ทั้ง Client, Server side ทําให้สามารถใช้ได้ ทั้ง Frontend developer, Backend developer
- Typescript ดีกว่า Javascript ในทุกๆด้าน เพราะ มีส่วนสําคัญทั้งหมดของ javascript เเละ ยังเพิ่มส่วนประกอบ อีกหลายอย่าง เช่น Interfaces, Generics, ความเป็น Strongly Typed ซึ่งช่วยเพิ่มประสิทธิภาพให้ การพัฒนา Software
ดังนั้นเราที่หนีไม่พ้น Javascript อยู่เเล้ว การศึกษา Data structure ด้วย Typescript จึงเป็นสิ่งที่ผมอยากจะเเนะนํา สําหรับเราที่เป็น Developer
Abstract Data Type
ในเเต่ล่ะ Programming language จะมีสิ่งที่เรียกว่า Built In Type ซึ่งก็คือ Type พื้นฐานที่ภาษาเหล่านั้นมีมาให้ เช่น Number, String, Boolean ใน Typescript เเต่ในบางสถานการณ์ เราจําเป็นจะต้องสร้าง User Defined Type ขึ้นมา เพื่อใช้งานในการเเก้ปัญหา Type เหล่านี้ คือการ Implement Data structure ที่ไม่มีอยู่ใน Built in type ขึ้นมา ตามความเหมาะสม เเละ ความต้องการของผู้ใช้ ซึ่งถูกเรียกว่า ADT โดยยึดหลักการ Abstraction
จากภาพด้านบนจะเห็นว่า ผู้ใช้ จะใช้งาน ADT ผ่าน Interface ด้วย Public function โดยส่วน Implementation จะถูกซ่อนเอาไว้ด้วย Abstraction โดยมี Data structure เป็นพื้นฐานในการ Design ADT
จากภาพด้านบนจะเห็นว่า Physical data structure คือ linked list โดยมี ADT เป็น List
Linear Data Structure
Linear Data Structure คือ data structure ที่มีรูปเเบบการเรียงตัวกันเป็นลําดับ เเละ เส้นตรง มักมีลําดับก่อนหลัง ข้อมูลมีการเรียงตัวเเบบ 1 มิติ เเละ ไม่เป็นลําดับขั้น ทําให้การ traverse อ่านข้อมูลเป็นเเบบ linear เนื่องจาก memory ที่เรียงตัวกัน ตัวอย่างเช่น Array, Linked list, Stack, Queue
ตารางนี้ เเสดงให้เห็นถึง Linear ADT ว่าสามารถ Implement ได้ด้วย Data structure ชนิดไหน
Array
Array เป็น Data structure พื้นฐาน มีขนาดที่ Fixed เเละ มี Collection ของ Element ที่เรียงลําดับ เหมาะสําหรับ collection ที่รู้ขนาด เเละ ขนาดไม่เปลี่ยนเเปลงบ่อยนัก เเละ ยังสามารถนําไป implement เป็น Data structure ชนิดอื่นๆ ได้อีกมาก เเละ Array ยังเป็น Data structure ที่ถูกพบได้ในเเถบทุกที่ เเละ ใช้กันเเพร่หลายที่สุดด้วย
Typescript
- Array ใน typescript เป็น dynamic array โดย default
Usage of array
- Mathematical operations ตัวอย่างเช่นการคํานวณ เเบบ metrix
- Storing large data sets เป็น collection ต่างๆ ที่มีขนาดใหญ่ เช่นพวกข้อมูลที่ได้มาจาก database
- Image processing รูปภาพต่างๆ ถูกเก็บเป็นข้อมูลพื้นฐาน(pixel) เเบบ array หลายมิติ ทําให้สามารถจัดการ เปลี่ยนเเปลงรูปภาพได้ เช่น digital compression
Time Complexity
List
List เป็น Data structure ที่ อเนกประสงค์ เเละ มีความสําคัญมากในการพัฒนา software ถูกใช้งานในการเก็บ เเละ จัดการข้อมูลที่เป็นลําดับต่อเนื่อง เเล้ว List ยังมีเเยกประเภทอีกหลายประเภท เช่น Linked list, Doubly linked list
Usage of list
- Task management เกิดขึ้นโดย Tasks ถูกสร้าง เเละ เรียงลําดับโดย User ซึ่งเราสามารถทําได้ ตั้งเเต่ add, remove, reorder, mark as complete or incomplete
- Social media feeds ตัวอย่างที่สําคัญเลยคือ Twitter ใช้ในการเก็บ เเละ เเสดง User’s feed เเบบ Real time ซึ่งเรามั่นใจได้เลยว่า content ต่างๆ จะอยู่ในลําดับที่ถูกต้อง
- Shopping carts สามารถถูก Implement ด้วย Linked list data structure เพื่อเพิ่มประสิทธิภาพ เวลามี Operation ต่างๆ โดยจะมี Performance มากกว่า Implement ด้วย Array
Time Complexity
Stack
Stack รูปเเบบของข้อมูลจะเป็นเเบบ LIFO Last In — First Out จําเป็นอย่างมากในการเก็บข้อมูลที่ ให้ความสําคัญต่อ stage and order
Typescript
- บน typescript เราสามารถ implement stack ขึ้นมาได้จาก ทั้ง array เเละ linked list
- ในกรณีที่เป็น linked list ต้อง implement linked list ADT ขึ้นมาก่อน เเลัวนํามา implement stack ต่อ
Usage of stack
- Undo/Redo in Text editor ใช้เก็บ change stage ต่างๆในการเเก้ไข text เพื่อใช้ undo/redo
- Web browser history จะเก็บข้อมูลเป็น Stack เช่น เวลาเรากดย้อนกลับ Broswer จะเปิดหน้าที่เเล้วที่เราเคยเข้า ซึ่งก็คือ Data บนสุดของ Stack
Time Complexity
Stack Implementation using array
export class Stack {
data: any[];
constructor() {
this.data = [];
}
push(value: any) {
this.data.push(value);
}
pop(): any {
if (this.isEmpty()) {
return null;
}
return this.data.pop();
}
peek(): any {
if (this.isEmpty()) {
return null;
}
return this.data[this.data.length - 1];
}
toArray(): any[] {
return [...this.data].reverse();
}
}Queue
Queue รูปเเบบของข้อมูลจะเป็นเเบบ FIFO First In — First Out จําเป็นอย่างมากในการเก็บข้อมูลที่ ให้ความสําคัญต่อลําดับการทํางาน ก่อน หลัง
Typescript
- บน typescript เราสามารถ implement queue ขึ้นมาได้จาก ทั้ง array เเละ linked list
- ในกรณีที่เป็น linked list ต้อง implement linked list ADT ขึ้นมาก่อน เเลัวนํามา implement stack ต่อ
Usage of queue
- Queuing job การทํางานที่ต้องมีลําดับ ประเภทต่างๆ นึกถึง queue ของ printer ก็ได้
- Gaming user action การทํา action ก่อน เเละ หลัง ของเกม
- Message queue (Handling messages) ใช้ใน message app ต่างๆ ที่เก็บข้อความที่ได้รับเข้า queue ไว้ เเสดงผลออกมาให้ถูกลําดับขั้น เป็นรูปเเบบของ message queue
Time Complexity
Queue Implementation using array
export class Queue<T> {
list: T[];
constructor() {
this.list = [];
}
enqueue(item: T): Queue<T> {
this.list = [...this.list, item];
return this;
}
dequeue(): T {
const item = this.list[0];
this.list = this.list.slice(1);
return item;
}
toString(): string {
return this.list.toString();
}
}Non-Linear Data Structure (Extra)
Non Linear Data Structure คือ Data structure ที่มีรูปเเบบของการเรียงตัวเเบบ หลายมิติ เเละ มีลําดับขั้น ไม่สามารถทําการ traverse เพียงครั้งเดียวเเลัว อ่านข้อมูลได้ทั้ง structure ตัวอย่างเช่น Graph, Tree
Tree
Tree เป็น data structure ใช้กับข้อมูลที่ เป็นลําดับขั้นโดยธรรมชาติ หรือ เเสดงความสัมพันธ์ นอกจากนี้ tree ยังมีอีกมากมายหลายชนิดอีกมาก ซึ่งถูกใช้เพื่อประโยชน์ที่เเตกต่างกัน
Usage of tree
- Database indexing ใช้ B-trees, B+ trees มาช่วยเรื่อง speed ของ operation(search, insert, delete) ต่างๆ ในการทํา database index ใน relational database เพื่อจัดการข้อมูลขนาดใหญ่มากๆ ให้มีประสิทธิภาพ
- File systems น่าจะเห็นภาพง่ายๆ ลองนึกถึง Folder ซ้อนกันหลายๆ ชั้น เเล้วข้างในมีหลาย folder ซ้อนกันอีกที
- AI decision making Decision tree ใช้ใน machine learning สําหรับ classification task
Heap
Heap เป็น Data structure เเบบ Tree base โดยที่มีหน้าตาเหมือน Tree เเต่ส่วนใหญ่จะสมส่วน เเละ ถูกใช้งานในทางที่ต่างจาก Tree นอกจากนั้นยังมี Heap เเยกย่อยออกไปอีกหลายชนิด ซึ่งถูกใช้งานที่เฉพาะเจาะจงลงไป
Usage of heap
- Memory management บน Executable program ทั้งหลาย จะสามารถใช้ Heap ในการ Allocate memory (Heap-based memory) เรียกว่า Heap storage ซึ่งจะเป็น dynamically-allocated memory จะถูก manage อัตโนมัติ โดย OS หรือ Memory manager library
- Priority queue ถูก Implement ด้วย Heap เพื่อเข้าไปหาค่าที่ สูงที่สุด ไปจน ค่าน้อยที่สุด
- Task scheduling เนื่องจาก Implement priority queue เเล้ว จึงสามารถจัด schedule ของ Task ได้ โดยขึ้นอยู่กับ priority ว่าจะทํา Task ไหนก่อน โดยจะทําจากค่ามาก ไปค่าน้อย
Graph
Graph เป็น data structure สําหรับ ตรวจสอบความสัมพันธ์ เเละ หาเส้นทาง
Usage of graph
- Recommendation engines ใช้ Graph เพื่อจัดเก็บความสัมพันธ์รอบๆ เเละ นํามาใช้เเนะนําตามความสัมพันธ์ เช่น ระบบ เเนะนําเพื่อนบน Social media application
- Pathfinding algorithms จะใช้ Graph เป็น Data structure เพื่อใช้ในการคํานวณ เช่น การหา Shortest Path, Single Source Shortest Path, Random Walk
Hash Table
Hash table เป็น Data structure ประเภทหนึ่งที่ใช้เก็บและค้นหาข้อมูลได้เร็วมาก หลักการคือนำ Key ของข้อมูลที่จะจัดเก็บมาทำการคำนวนโดยใช้ hash function map กับ hash table ทําให้เมื่อ นํา Key มาผ่าน Hash function จะสามารถเข้าถึงข้อมูลได้ทันที
Usage of hash table
- Search engines จะใช้ Hash table ทําหน้าที่เป็น Index เพื่อ Map key เข้ากับ value ซึ่งจะช่วยให้เข้าถึงข้อมูลได้อย่างรวดเร็ว เเม้ข้อมูลจะมีมหาศาล Search engines ก็ยังจะทํางานได้อย่างรวดเร็ว
- Caching systems จะใช้ Hash table เก็บ เเละ จัดการ ข้อมูล cache เพื่อตอบสนอง Request ที่มีจํานวนมาก ส่วนนี้ทําให้ระบบ มีประสิทธิภาพมากขึ้น
- Programming language interpreters or compilers จะ Implement Symbol tables ด้วย Hash table เพื่อจัดการ หรือ ค้นหา Variables, Function, Symbols ต่างๆ ที่มีใน Source code
Conclusion
บทความนี้เขียนขึ้นมาเพื่อบอกเล่า ความสําคัญของ Data structure ผ่านการตั้งคําถามว่า ทําไม Developer ถึงควรศึกษา โดยเเนะนํา ภาษาเป็น Typescript รวมไปถึงเเนวคิดการ Implementation Abstract Data Type ด้วย เเนวคิด Abstraction บนรากฐานของ Data structure นั้นๆ ที่สามารถประยุกต์ใช้ตามความต้องการเพื่อ เเก้ไขปัญหา พร้อมกับยกตัวอย่างประกอบร่วมกับ Data structure ชนิดต่างๆ ว่าถูกใช้งานยังไงบน โลกความเป็นจริง ผมหวังว่าบทความนี้จะเป็นประโยชน์ กับผู้อ่านทุกคนนะครับ
