Tong hop cac luu y ve kieu du lieu dang tap hop
1. Array va List
- Array va List deu la nhung kieu du lieu duoc su dung nhieu va pho bien
1.1. Array
- Co kich thuoc co dinh
- Truy cap phan tu nhanh (O(1))
- Khong co san phuong thuc them/xoa phan tu
- Read more docs
int[] numbers = new int[3] { 1, 2, 3 };
Debug.Log(numbers[0]); // 1
Debug.Log(numbers[0]); // 1
1.2. List
- Kich thuoc linh hoat
- Them/xoa cac phan tu de dang
- Tim kiem phan tu cham hon HashSet.
- Read more docs
List<string> players = new List<string>() { "Alice", "Bob" };
players.Add("Charlie");
Debug.Log(players[1]); // Bob
players.Add("Charlie");
Debug.Log(players[1]); // Bob
1.3. Luu y khi su dung vong lap for/foreach (Read more)
- Doi voi
Array, vong lap foreach doi khi co the nhanh nhu, hoac tham chi nhanh hon, vong lap for. Dieu nay la do trinh bien dich C# toi uu hoa foreach cho mang, khien no gan nhu tuong duong voi vong lap for. Vi mang co kich thuoc co dinh va cac phan tu cua chung duoc luu tru trong mot khoi bo nho lien ke, trinh bien dich co the tao ma IL (Ngon ngu trung gian) rat hieu qua cho foreach tren mang, thuong khien no hieu qua nhu vong lap for. - Doi voi
List, vong lap for thuong nhanh hon foreach khi lap qua cac doi tuong List. Dieu nay la do foreach tao ra mot doi tuong Enumerator, co the them mot chut chi phi, trong khi for truy cap truc tiep cac phan tu theo chi muc. Viec phan bo them nay trong foreach co the anh huong mot chut den hieu suat, dac biet la trong cac tinh huong ma chi phi thu gom rac (GC) la mot moi quan tam. - Tom lai:
- Su dung for voi Lists: Doi voi cac truong hop ban dang lap lai cac danh sach lon hoac co ma nhay cam ve hieu suat, for thuong duoc uu tien cho List. Dieu nay co the tranh viec phan bo enumerator bo sung di kem voi foreach.
- Su dung foreach voi Mang: Neu ban dang lap qua cac mang, foreach thuong co hieu suat ngang bang voi for va co the giup ma cua ban de doc hon.
2. HashSet
- HashSet rat huu ich khi ban can luu cac phan tu duy nhat va thuc hien cac thao tac tap hop hieu qua
- Read more docs
HashSet<string> enemyNames = new HashSet<string>();
enemyNames.Add("Zombie");
enemyNames.Add("Skeleton");
enemyNames.Add("Orc");
// Them phan tu trung lap se khong co tac dung
enemyNames.Add("Zombie"); // Khong duoc them vao
enemyNames.Add("Zombie");
enemyNames.Add("Skeleton");
enemyNames.Add("Orc");
// Them phan tu trung lap se khong co tac dung
enemyNames.Add("Zombie"); // Khong duoc them vao
2.1 Uu diem cua HashSet
- Hieu suat cao: Cac thao tac Contains, Add, Remove co do phuc tap O(1)
- Tu dong loai bo trung lap: Dam bao moi phan tu la duy nhat
2.2 So sanh voi List
| Tinh nang | HashSet | List |
|---|---|---|
| Toc do tim kiem | O(1) | O(n) |
| Cho phep trung lap | Khong | Co |
| Thu tu phan tu | Khong dam bao | Duoc dam bao |
| Toc do them/xoa | Nhanh | Cham hon (dac biet khi xoa) |
==> Tom lai: HashSet la su lua chon tuyet voi khi ban can luu tru cac phan tu duy nhat va thuong xuyen kiem tra su ton tai cua phan tu
3. Dictionary
- La cau truc du lieu cho phep luu tru du lieu theo dang cap
key-valuevoi hieu suat truy xuat cao - Read more docs
using System.Collections.Generic;
// Khoi tao Dictionary co ban
Dictionary<string, int> playerScores = new Dictionary<string, int>();
// Khoi tao voi gia tri ban dau
Dictionary<string, string> weaponTypes = new Dictionary<string, string>() {
{"sword", "melee"},
{"bow", "ranged"},
{"staff", "magic"}
};
// Khoi tao Dictionary co ban
Dictionary<string, int> playerScores = new Dictionary<string, int>();
// Khoi tao voi gia tri ban dau
Dictionary<string, string> weaponTypes = new Dictionary<string, string>() {
{"sword", "melee"},
{"bow", "ranged"},
{"staff", "magic"}
};
playerScores.Add("Player1", 100);
playerScores.Add("Player2", 150);
// Hoac su dung indexer
playerScores["Player3"] = 200;
int score = playerScores["Player1"]; // Lay gia tri
// Kiem tra ton tai key truoc khi truy cap
if (playerScores.ContainsKey("Player2")) {
Debug.Log("Score cua Player2: " + playerScores["Player2"]);
}
playerScores.Add("Player2", 150);
// Hoac su dung indexer
playerScores["Player3"] = 200;
int score = playerScores["Player1"]; // Lay gia tri
// Kiem tra ton tai key truoc khi truy cap
if (playerScores.ContainsKey("Player2")) {
Debug.Log("Score cua Player2: " + playerScores["Player2"]);
}
3.1 Uu diem
- Truy xuat nhanh: Do phuc tap O(1) cho cac thao tac tim kiem, them, xoa
- To chuc linh hoat: De dang anh xa giua cac doi tuong game
- Hieu suat cao: Ly tuong cho he thong truy cap nhanh nhu inventory, player data, ...
3.2 Luu y quan trong
- Key phai la duy nhat: Moi key chi xuat hien mot lan trong Dictionary
- Key khong duoc null: Se gay ra exception neu co gang su dung null key
- Kiem tra ton tai: Luon kiem tra ContainsKey truoc khi truy cap de tranh KeyNotFoundException
- Hieu suat: Dictionary chiem nhieu bo nho hon List/Array nhung truy xuat nhanh hon
3.3 So sanh voi cac cau truc khac
| Tinh nang | Dictionary |
List | Array (T[]) | HashSet |
|---|---|---|---|---|
| Truy cap bang key | O(1) | Khong ho tro | Khong ho tro | Chi kiem tra ton tai |
| Truy cap bang index | Khong ho tro | O(1) | O(1) | Khong ho tro |
| Tim kiem phan tu | O(1) (by key) | O(1) | ||
| Them phan tu | O(1) | O(1)* | Kich thuoc co dinh | O(1) |
| Xoa phan tu | O(1) | Khong ho tro | O(1) | |
| Luu tru key-value | Co | Khong | Khong | Chi luu gia tri |
| Cho phep trung lap | Key phai duy nhat | Co | Co | Gia tri duy nhat |
| Bao toan thu tu | Khong dam bao | Co | Co | Khong dam bao |
| Tot cho | Tra cuu nhanh bang key | Danh sach co thu tu | Du lieu co dinh | Kiem tra ton tai nhanh |
*Ghi chu:
- = Ho tro tot
= Co the cham voi du lieu lon - = Khong ho tro
- O(1)* voi List: O(1) neu Capacity chua day, O(n) khi can mo rong
==> Tom lai: Dictionary la cong cu manh me de quan ly du lieu trong Unity, dac biet khi ban can anh xa giua cac dinh danh va gia tri voi hieu suat cao.
4. Queue
- Queue la cau truc du lieu hang doi (FIFO - First In First Out), nghia la phan tu nao duoc them vao truoc thi se duoc lay ra truoc. No huu ich khi ban can quan ly mot danh sach cac hanh dong, su kien hoac nhiem vu can xu ly theo thu tu.
- Read more docs
Queue<int> queue = new Queue<int>(); // Khoi tao queue chua so nguyen
void Add(){
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
}
int Get(){
int firstElement = queue.Dequeue(); // Lay ra 1 va xoa khoi hang doi
return firstElement; // ket qua tra ve bang 1
}
int Peek(){
int front = queue.Peek(); // Xem phan tu dau tien nhung khong xoa
return front
}
void Add(){
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
}
int Get(){
int firstElement = queue.Dequeue(); // Lay ra 1 va xoa khoi hang doi
return firstElement; // ket qua tra ve bang 1
}
int Peek(){
int front = queue.Peek(); // Xem phan tu dau tien nhung khong xoa
return front
}
Vi du su dung Queue de quan ly nhiem vu trong game
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class TaskManager : MonoBehaviour
{
Queue<string> taskQueue = new Queue<string>();
void Start()
{
// Them nhiem vu vao hang doi
taskQueue.Enqueue("Nhat vu khi");
taskQueue.Enqueue("Tan cong ke dich");
taskQueue.Enqueue("Thu thap vat pham");
StartCoroutine(ProcessTasks());
}
IEnumerator ProcessTasks()
{
while (taskQueue.Count > 0)
{
string currentTask = taskQueue.Dequeue();
Debug.Log("Thuc hien nhiem vu: " + currentTask);
yield return new WaitForSeconds(2); // Gia lap thoi gian thuc hien nhiem vu
}
Debug.Log("Hoan thanh tat ca nhiem vu!");
}
}
using System.Collections.Generic;
using UnityEngine;
public class TaskManager : MonoBehaviour
{
Queue<string> taskQueue = new Queue<string>();
void Start()
{
// Them nhiem vu vao hang doi
taskQueue.Enqueue("Nhat vu khi");
taskQueue.Enqueue("Tan cong ke dich");
taskQueue.Enqueue("Thu thap vat pham");
StartCoroutine(ProcessTasks());
}
IEnumerator ProcessTasks()
{
while (taskQueue.Count > 0)
{
string currentTask = taskQueue.Dequeue();
Debug.Log("Thuc hien nhiem vu: " + currentTask);
yield return new WaitForSeconds(2); // Gia lap thoi gian thuc hien nhiem vu
}
Debug.Log("Hoan thanh tat ca nhiem vu!");
}
}
Giai thich:
- Danh sach nhiem vu duoc quan ly bang Queue.
- Dung Coroutine de thuc hien nhiem vu tuan tu (moi nhiem vu mat 2 giay).
- Khi taskQueue.Count == 0, tat ca nhiem vu da hoan thanh.
Khi nao ta nen dung Queue trong unity?
- Quan ly danh sach nhiem vu tuan tu (nhu AI, NPC thuc hien hanh dong theo thu tu).
- Xu ly hang doi su kien (nhu log chat, thong bao he thong).
- Tao he thong Pooling (quan ly doi tuong tai su dung de toi uu hieu nang).
- Tinh toan duong di AI (bang BFS - Breadth First Search).
5. Stack
- Stack la cau truc du lieu ngan xep (LIFO - Last In First Out), tuc la phan tu nao duoc them vao sau se duoc lay ra truoc. No thich hop su dung de quan ly cac trang thai, he thong Undo/Redo hoac giai quyet bai toan de quy.
- Read more docs
Stack<int> stack = new Stack<int>(); // Khoi tao stack chua so nguyen
void Push(){
stack.Push(10);
stack.Push(20);
stack.Push(30);
}
int Pop(){
int lastElement = stack.Pop(); // Lay ra 30 va xoa khoi stack
return lastElement;
}
int Peek(){
int topElement = stack.Peek(); // Xem phan tu tren cung nhung khong xoa
return topElement;
}
void Push(){
stack.Push(10);
stack.Push(20);
stack.Push(30);
}
int Pop(){
int lastElement = stack.Pop(); // Lay ra 30 va xoa khoi stack
return lastElement;
}
int Peek(){
int topElement = stack.Peek(); // Xem phan tu tren cung nhung khong xoa
return topElement;
}
Vi du ve he thong Undo/Redo bang Stack
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class UndoRedoManager : MonoBehaviour
{
Stack<string> undoStack = new Stack<string>();
Stack<string> redoStack = new Stack<string>();
void Start()
{
PerformAction("Di chuyen len");
PerformAction("Di chuyen phai");
PerformAction("Tan cong");
Undo();
Undo();
Redo();
}
void PerformAction(string action)
{
undoStack.Push(action);
redoStack.Clear(); // Khi thuc hien hanh dong moi, khong the Redo nua
Debug.Log("Hanh dong: " + action);
}
void Undo()
{
if (undoStack.Count > 0)
{
string lastAction = undoStack.Pop();
redoStack.Push(lastAction);
Debug.Log("Undo: " + lastAction);
}
else
{
Debug.Log("Khong the Undo!");
}
}
void Redo()
{
if (redoStack.Count > 0)
{
string lastUndoneAction = redoStack.Pop();
undoStack.Push(lastUndoneAction);
Debug.Log("Redo: " + lastUndoneAction);
}
else
{
Debug.Log("Khong the Redo!");
}
}
}
using System.Collections.Generic;
using UnityEngine;
public class UndoRedoManager : MonoBehaviour
{
Stack<string> undoStack = new Stack<string>();
Stack<string> redoStack = new Stack<string>();
void Start()
{
PerformAction("Di chuyen len");
PerformAction("Di chuyen phai");
PerformAction("Tan cong");
Undo();
Undo();
Redo();
}
void PerformAction(string action)
{
undoStack.Push(action);
redoStack.Clear(); // Khi thuc hien hanh dong moi, khong the Redo nua
Debug.Log("Hanh dong: " + action);
}
void Undo()
{
if (undoStack.Count > 0)
{
string lastAction = undoStack.Pop();
redoStack.Push(lastAction);
Debug.Log("Undo: " + lastAction);
}
else
{
Debug.Log("Khong the Undo!");
}
}
void Redo()
{
if (redoStack.Count > 0)
{
string lastUndoneAction = redoStack.Pop();
undoStack.Push(lastUndoneAction);
Debug.Log("Redo: " + lastUndoneAction);
}
else
{
Debug.Log("Khong the Redo!");
}
}
}
Giai thich:
- undoStack luu tru cac hanh dong da thuc hien.
- redoStack luu tru cac hanh dong da Undo de co the Redo.
- Khi thuc hien hanh dong moi, redoStack bi xoa de tranh Redo loi.
So sanh Stack va Queue
| Dac diem | Stack (LIFO) |
Queue (FIFO) |
|---|---|---|
| Cach hoat dong | Lay phan tu cuoi cung truoc | Lay phan tu dau tien truoc |
| Phuong thuc chinh | Push(), Pop(), Peek() |
Enqueue(), Dequeue(), Peek() |
| Ung dung | He thong Undo/Redo, de quy, duyet cay | Quan ly hang doi, xu ly nhiem vu tuan tu |
Khi nao nen dung Stack trong unity?
- He thong Undo/Redo (vi du: chinh sua ban do, hanh dong nhan vat).
- Duyet cay de quy (DFS - Depth First Search).
- He thong xu ly trang thai nhan vat (State Machine).
- Quan ly lich su hanh dong cua AI.
6. LinkedList
- La mot cau truc du lieu giup quan ly danh sach lien ket 2 chieu
- Read more docs
Them phan tu
- Co nhieu cach de them phan tu
LinkedList<int> numbers = new LinkedList<int>();
// Them vao dau danh sach
numbers.AddFirst(10);
// Them vao cuoi danh sach
numbers.AddLast(20);
// Them mot phan tu sau mot node cu the
LinkedListNode<int> node = numbers.AddLast(30);
numbers.AddAfter(node, 40);
// Them mot phan tu truoc mot node cu the
numbers.AddBefore(node, 25);
// Them vao dau danh sach
numbers.AddFirst(10);
// Them vao cuoi danh sach
numbers.AddLast(20);
// Them mot phan tu sau mot node cu the
LinkedListNode<int> node = numbers.AddLast(30);
numbers.AddAfter(node, 40);
// Them mot phan tu truoc mot node cu the
numbers.AddBefore(node, 25);
Duyet LinkedList
- Su dung foreach
foreach (int number in numbers)
{
Debug.Log(number);
}
{
Debug.Log(number);
}
- Su dung while thong qua LinkedListNode
LinkedListNode<int> current = numbers.First;
while (current != null)
{
Debug.Log(current.Value);
current = current.Next;
}
while (current != null)
{
Debug.Log(current.Value);
current = current.Next;
}
Xoa phan tu
- Co nhieu cach de xoa phan tu
numbers.Remove(25); // Xoa gia tri cu the
numbers.RemoveFirst(); // Xoa phan tu dau tien
numbers.RemoveLast(); // Xoa phan tu cuoi cung
numbers.Clear(); // Xoa toan bo danh sach
numbers.RemoveFirst(); // Xoa phan tu dau tien
numbers.RemoveLast(); // Xoa phan tu cuoi cung
numbers.Clear(); // Xoa toan bo danh sach
Ung dung LinkedList trong Unity
- Quan ly danh sach hanh dong cua AI (cac hanh dong lien tuc nhu di chuyen, tan cong).
- Quan ly doi tuong trong game (danh sach quai vat, dan trong game ban sung, checkpoint).
- Trien khai Undo/Redo (lich su thao tac cua nguoi choi).
Khi nao nen dung LinkedList thay vi List?
| Tieu chi | List | LinkedList |
|---|---|---|
| Them/Xoa o giua | Cham (O(n)) | Nhanh (O(1)) |
| Truy cap phan tu | Nhanh (O(1)) | Cham (O(n)) |
| Duyet danh sach | Nhanh | Trung binh |
| Bo nho su dung | It hon | Nhieu hon (do luu Node) |
- Dung List neu ban can truy cap phan tu nhanh bang index.
- Dung LinkedList neu ban can them/xoa phan tu thuong xuyen o giua danh sach.
Ket luan
- LinkedList huu ich khi can them/xoa phan tu nhanh o giua danh sach.
- Tuy nhien, no ton bo nho hon so voi List.
- Trong Unity, nen dung cho cac he thong hang doi, undo/redo, hoac quan ly pool doi tuong.