Choosing the Right Structure (သင့်တော်တဲ့ data structure ကို ရွေးချယ်ခြင်း)

B4.1.1 (HL): Explain the properties and purpose of ADTs. B4.1.2 (HL): Evaluate linked lists. B4.1.4 (HL): Explain the structures and properties of BSTs. B4.1.6 (HL): Explain the core principles of ADTs: hash tables (hashing functions, collision resolution, load factors), mechanics of sets, HashMap/HashSet in Java.
မြန်မာလို: ADT (abstract data type: operation တွေနဲ့ သတ်မှတ်တဲ့ ဒေတာ အမျိုးအစား) တွေရဲ့ ဂုဏ်သတ္တိနဲ့ ရည်ရွယ်ချက်ကို ရှင်းပြနိုင်ရပါမယ်။ Linked list (node တွေ ချိတ်ဆက်ထားတဲ့ list) တွေကို evaluate (အားသာချက်နဲ့ အားနည်းချက်တွေကို ချိန်ဆပြီး အကဲဖြတ်) လုပ်နိုင်ရပါမယ်။ BST (binary search tree: ဘယ်ဘက် ငယ်၊ ညာဘက် ကြီးတဲ့ binary tree) တွေရဲ့ ဖွဲ့စည်းပုံနဲ့ ဂုဏ်သတ္တိတွေကို ရှင်းပြနိုင်ရပါမယ်။ ADT တွေရဲ့ အဓိက သဘောတရားတွေကို ရှင်းပြနိုင်ရပါမယ်: hash table (key-value တွေကို အမြန် ရှာနိုင်အောင် သိမ်းတဲ့ structure) တွေ (hashing function (key ကို bucket index အဖြစ် ပြောင်းတဲ့ function)၊ collision resolution (key နှစ်ခု index တူသွားရင် ဖြေရှင်းပုံ)၊ load factor (hash table ဘယ်လောက် ပြည့်နေလဲ ဆိုတာ))၊ set တွေ အလုပ်လုပ်ပုံ၊ Java ရဲ့ HashMap (Java ရဲ့ key-value hash table) နဲ့ HashSet (မထပ်တဲ့ element တွေ သိမ်းတဲ့ Java collection)။

ဒီစာမျက်နှာက HL အတွက်ပဲ ဖြစ်ပါတယ်။ SL (Standard Level) နဲ့ HL (Higher Level) ဆိုတာ IB Computer Science (နိုင်ငံတကာ ကျောင်းတွေမှာ သင်တဲ့ ကွန်ပျူတာသိပ္ပံ သင်ရိုး) သင်တန်းရဲ့ အဆင့်နှစ်ဆင့်ဖြစ်ပြီး HL အပိုင်းတွေက ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အပိုင်းတွေပါ။

အဓိက အယူအဆများ

Data structure (ဒေတာ သိမ်းဆည်းပုံ) တိုင်းမှာ အားသာချက်နဲ့ အားနည်းချက်တွေ ရှိလို့ “အကောင်းဆုံး” structure ဆိုတာ တစ်ခုတည်း မရှိပါဘူး။ ကိုယ့် program က ဘယ် operation (ဒေတာပေါ်မှာ လုပ်တဲ့ လုပ်ဆောင်ချက်) တွေ လိုလဲ၊ အဲဒီ operation တွေကို ဘယ်လောက် မကြာခဏ လုပ်လဲ နဲ့ သုံးလို့ရတဲ့ memory (မှတ်ဉာဏ်) ကို နှိုင်းယှဉ်ပြီး ရွေးပါ။ အောက်က အပိုင်းတွေမှာ အဲဒီ trade-off (တစ်ခု ရဖို့ တစ်ခု အလျှော့ပေးရတာ) တွေကို နှိုင်းယှဉ်ပြထားပါတယ်။

အဓိက နှိုင်းယှဉ်ချက် ဇယား

Structure	Search (ရှာခြင်း)	Insert (ထည့်ခြင်း)	Delete (ဖျက်ခြင်း)	Sorted (စီပြီးသား) ဖြစ်လား	ထပ်တာ ရလား	Memory	အသင့်တော်ဆုံး နေရာ
Array (အရွယ်အစား ပုံသေ၊ အမျိုးအစားတူ ဒေတာစု)	O(n)	O(n)*	O(n)*	မဟုတ်ဘူး (sort လုပ်ထားရင်တော့ ဟုတ်တယ်)	ရတယ်	ပုံသေ၊ ကျစ်လစ်တယ်	အရွယ်အစား ပုံသေ collection (ဒေတာအစု)၊ index (နေရာအမှတ်) နဲ့ ယူသုံးခြင်း
ArrayList (ကြီးလာ၊ သေးသွားနိုင်တဲ့ list)	O(n)	O(1) amortized (အကြိမ်များစွာကို ပျမ်းမျှ ကြည့်ရင်၊ အဆုံးမှာ)	O(n)	မဟုတ်ဘူး	ရတယ်	Dynamic (ကြီးလာ၊ သေးသွားနိုင်)၊ အပို memory နည်းနည်း လိုတယ်	ကြီးလာနေတဲ့ list၊ အဆုံးမှာ မကြာခဏ ထပ်ထည့်ခြင်း
Singly linked list (တစ်ဘက်တည်း ချိတ်ဆက်ထားတဲ့ linked list)	O(n)	head (list ရဲ့ ရှေ့ဆုံး node) မှာ O(1)	O(n)**	မဟုတ်ဘူး	ရတယ်	Node (ဒေတာ သိမ်းထားတဲ့ အကွက်) တစ်ခုစီမှာ pointer (reference ရဲ့ နောက်နာမည်: object ရှိရာ memory နေရာကို ညွှန်းတဲ့ တန်ဖိုး) အပို တစ်ခု	ရှေ့ဆုံးမှာ မကြာခဏ ထည့်၊ ဖယ်ခြင်း
Doubly linked list (နှစ်ဘက်လုံး ချိတ်ဆက်ထားတဲ့ linked list)	O(n)	head/tail (ရှေ့ဆုံး/နောက်ဆုံး node) မှာ O(1)	reference ရှိရင် O(1)**	မဟုတ်ဘူး	ရတယ်	Node တစ်ခုစီမှာ pointer နှစ်ခု	အစွန်း နှစ်ဘက်လုံးမှာ မကြာခဏ ထည့်၊ ဖယ်ခြင်း
Stack (အပေါ်ကနေပဲ ထည့်၊ ထုတ်တဲ့ အထပ်)	O(n)	O(1) push (အပေါ်ဆုံးမှာ ထည့်ခြင်း)	O(1) pop (အပေါ်ဆုံးကနေ ဖယ်ထုတ်ခြင်း)	မဟုတ်ဘူး	ရတယ်	အနည်းဆုံး	LIFO (နောက်ဆုံးဝင်တာ အရင်ထွက်): undo (နောက်ဆုံး လုပ်ခဲ့တာကို ပြန်ဖျက်ခြင်း)၊ backtracking (နောက်ပြန်ဆုတ်ပြီး တခြား လမ်း စမ်းခြင်း)၊ ကွင်းစ ကွင်းပိတ် စစ်ခြင်း
Queue (အရင်ထည့်တာ အရင်ထွက်တဲ့ တန်း)	O(n)	O(1) enqueue (နောက်ဆုံးမှာ ထည့်ခြင်း)	O(1) dequeue (ရှေ့ဆုံးကနေ ထုတ်ခြင်း)	မဟုတ်ဘူး	ရတယ်	အနည်းဆုံး	FIFO (အရင်ဝင်တာ အရင်ထွက်): scheduling (ဘယ် process ကို CPU အချိန် ပေးမလဲ ဆုံးဖြတ်ခြင်း)၊ BFS (အနီးဆုံး node တွေကို အရင် သွားကြည့်တဲ့ ရှာနည်း)၊ buffer (ဒေတာကို ခဏ သိမ်းထားတဲ့ နေရာ)
BST (balanced) (ဘယ်ညာ ညီမျှနေတဲ့ binary search tree)	O(log n)	O(log n)	O(log n)	ဟုတ်တယ် (in-order: ဘယ်၊ node၊ ညာ အစဉ်နဲ့ ဖတ်ရင်)	မရဘူး	Node တစ်ခုစီမှာ pointer နှစ်ခု	မြန်မြန် ရှာခြင်း + sorted output (program က ထုတ်ပြတဲ့ ရလဒ်)
HashSet	ပျမ်းမျှ O(1)	ပျမ်းမျှ O(1)	ပျမ်းမျှ O(1)	မဟုတ်ဘူး	မရဘူး	Hash table ရဲ့ အပို memory	ပါမပါ စစ်ခြင်း (membership testing)၊ ထပ်နေတာတွေ ဖယ်ခြင်း
HashMap	key (value ကို ပြန်ရှာဖို့ သုံးတဲ့ တန်ဖိုး) နဲ့ ရှာရင် ပျမ်းမျှ O(1)	ပျမ်းမျှ O(1)	ပျမ်းမျှ O(1)	မဟုတ်ဘူး	Key: မရဘူး၊ Value: ရတယ်	Hash table ရဲ့ အပို memory	Key နဲ့ value ကို ရှာခြင်း၊ ရေတွက်ခြင်း

* Array မှာ သတ်မှတ်ထားတဲ့ နေရာ တစ်ခုမှာ ထည့်တာ၊ ဖျက်တာက element (အစုထဲက အချက်) တွေကို ရွှေ့ပေးရပါတယ်။ ** Node ကို ညွှန်းတဲ့ reference ရှိပြီးသား ဆိုရင် linked list delete က O(1) ပါ၊ ဒါပေမဲ့ အဲဒီ node ကို အရင် ရှာရရင်တော့ O(n) ပါ။

BST ရဲ့ မြန်နှုန်းက tree ရဲ့ ဘယ်ညာ ညီမျှမှု (balance) ပေါ် မူတည်ပါတယ်။ Skewed (တစ်ဘက်ကို စောင်းနေတဲ့) BST မှာ operation အားလုံး O(n) အထိ နှေးသွားပါတယ်: linked list နဲ့ အတူတူပါပဲ။ O(log n) ဆိုတဲ့ တန်ဖိုးတွေက tree က တော်တော်လေး ညီမျှနေတယ်လို့ ယူဆထားတာပါ။

ဆုံးဖြတ်ချက် ချဖို့ Flowchart (လုပ်ငန်းစဉ်ကို သင်္ကေတတွေနဲ့ ဆွဲပြတဲ့ ပုံ)

ဒီမေးခွန်းတွေကို သုံးပြီး ရွေးစရာတွေကို တဖြည်းဖြည်း ကျဉ်းအောင် လုပ်ပါ။ မေးခွန်း 1 ကနေ စပါ: “Yes” (ဟုတ်တယ်) ဆိုရင် structure တစ်ခုဆီ ရောက်ပြီး “No” (မဟုတ်ဘူး) ဆိုရင် နောက်မေးခွန်းကို ဆက်သွားပါ။

ပုံထဲက English မေးခွန်းတွေရဲ့ အဓိပ္ပာယ် (“Yes” က ဟုတ်တယ်၊ “No” က မဟုတ်ဘူး):

“Do you need key-value pairs?”: key-value pair (key နဲ့ value တစ်တွဲ) တွေ လိုသလား။
“Do you need only unique elements?”: မထပ်တဲ့ element တွေပဲ လိုသလား။ “order does not matter” က အစဉ် အရေးမကြီးဘူး၊ “you need sorted order” က sorted အစဉ် လိုတယ်။
“Do you need LIFO (last in, first out) access?”: LIFO ပုံစံနဲ့ ယူသုံးဖို့ လိုသလား။
“Do you need FIFO (first in, first out) access?”: FIFO ပုံစံနဲ့ ယူသုံးဖို့ လိုသလား။
“Do you need fast search?”: မြန်မြန် ရှာဖို့ လိုသလား။ “by key/value in O(1)” က key/value နဲ့ O(1) မှာ၊ “in sorted order, O(log n)” က sorted အစဉ်နဲ့ O(log n) မှာ၊ “by index in O(1)” က index နဲ့ O(1) မှာ။
“Do you need frequent insertion/deletion?”: မကြာခဏ ထည့်၊ ဖျက် လုပ်ဖို့ လိုသလား။ “at the front” က ရှေ့ဆုံးမှာ၊ “at both ends” က အစွန်း နှစ်ဘက်လုံးမှာ၊ “at the end” က အဆုံးမှာ၊ “in sorted position” က sorted နေရာမှာ။
“Is the size known and fixed?”: အရွယ်အစားကို သိပြီး ပုံသေ ဖြစ်သလား။

အဖြစ်များတဲ့ Trade-off များ

Trade-off	ရှင်းလင်းချက်
မြန်နှုန်း နဲ့ memory	Hash table တွေက O(1) lookup (တန်ဖိုးကို ရှာယူခြင်း) ကို ပေးပေမယ့် ဗလာ bucket (hash table ထဲမှာ ဒေတာ သိမ်းတဲ့ အကွက်) တွေအတွက် memory ကို အလဟဿ ဖြုန်းပါတယ်။ Linked list တွေက element တစ်ခုစီအတွက်ပဲ memory သုံးပေမယ့် pointer အပိုတွေ လိုပါတယ်။
Sorted နဲ့ မြန်နှုန်း	BST တွေက sorted အစဉ်ကို ထိန်းထားပေမယ့် operation တွေက O(log n) ပါ။ HashSet တွေက O(1) ပေးပေမယ့် အစဉ် မရှိပါဘူး။
ပုံသေ နဲ့ dynamic	Array တွေက မြန်ပြီး ကျစ်လစ်ပေမယ့် အရွယ်အစား ပြောင်းလို့ မရပါဘူး။ ArrayList နဲ့ linked list တွေကတော့ လိုသလောက် ကြီးလာပါတယ်။
ရိုးရှင်းမှု နဲ့ ပြောင်းလွယ်မှု	Stack နဲ့ queue တွေက item (အချက်) တွေကို ထည့်ပုံ၊ ဖယ်ပုံကို ကန့်သတ်ထားလို့ လိုအပ်တဲ့ ယူသုံးမယ့် အစဉ်ကို မပျက်အောင် ထိန်းပေးပါတယ်။

အဆင့်ဆင့် ရှင်းပြထားတဲ့ ဥပမာများ

ဥပမာ 1: အလုပ် တစ်ခုအတွက် structure ရွေးခြင်း

အခြေအနေ တစ်ခုစီအတွက် အသင့်တော်ဆုံး data structure ကို ရွေးပြီး ဘာကြောင့်လဲ ရှင်းပြပါ။

အခြေအနေ A: Browser history (ကြည့်ခဲ့တဲ့ ဝဘ်စာမျက်နှာ မှတ်တမ်း၊ back ခလုတ်)

လိုအပ်ချက်: သွားကြည့်တဲ့ စာမျက်နှာတွေကို ထည့်သွားပြီး ယခင် စာမျက်နှာကို ပြန်သွားနိုင်ရမယ်
ပုံစံ: last in, first out (နောက်ဆုံးဝင်တာ အရင်ထွက်)
အကောင်းဆုံး ရွေးချယ်မှု: Stack။ စာမျက်နှာ တစ်ခုစီကို push လုပ်ပြီး ပြန်သွားဖို့ pop လုပ်ပါ

အခြေအနေ B: Print job queue (print ထုတ်ဖို့ စောင့်နေတဲ့ အလုပ် တန်း)

လိုအပ်ချက်: ရောက်လာတဲ့ အလုပ်တွေကို ထည့်သွားပြီး ရောက်လာတဲ့ အစဉ်အတိုင်း လုပ်ရမယ်
ပုံစံ: first in, first out (အရင်ဝင်တာ အရင်ထွက်)
အကောင်းဆုံး ရွေးချယ်မှု: Queue။ အလုပ်အသစ်တွေကို enqueue လုပ်ပြီး လုပ်ဖို့ dequeue လုပ်ပါ

အခြေအနေ C: Spell checker (စာလုံးပေါင်း စစ်တဲ့ program) ရဲ့ အဘိဓာန်

လိုအပ်ချက်: စကားလုံး တစ်လုံး အဘိဓာန်ထဲမှာ ရှိမရှိကို အရမ်း မြန်မြန် စစ်နိုင်ရမယ်
ပုံစံ: ပါမပါ စစ်ခြင်း (membership testing)၊ အစဉ် မလို
အကောင်းဆုံး ရွေးချယ်မှု: HashSet။ contains က O(1)၊ ထပ်နေတာ မရှိ

အခြေအနေ D: ကျောင်းသား အမှတ်စာရင်း စာအုပ်

လိုအပ်ချက်: ကျောင်းသား တစ်ယောက်ရဲ့ grade (အမှတ်) ကို နာမည်နဲ့ ရှာနိုင်ရမယ်
ပုံစံ: key (နာမည်) ကို value (grade) နဲ့ တွဲထားခြင်း
အကောင်းဆုံး ရွေးချယ်မှု: HashMap။ key နဲ့ ရှာရင် O(1)

အခြေအနေ E: သီချင်း ခေါင်းစဉ်အလိုက် စီထားတဲ့ playlist (သီချင်းစာရင်း)

လိုအပ်ချက်: သီချင်းတွေကို အစဉ်တကျ စီထားရမယ်၊ သီချင်းအသစ်တွေကို မှန်ကန်တဲ့ နေရာမှာ ထည့်ရမယ်၊ အစဉ်အတိုင်း ပြရမယ်
ပုံစံ: ထည့်လို့ရတဲ့ sorted collection
အကောင်းဆုံး ရွေးချယ်မှု: BST။ Sorted နေရာမှာ O(log n) နဲ့ insert လုပ်ပြီး ပြဖို့ in-order traversal (ဘယ်၊ node၊ ညာ အစဉ်နဲ့ node တွေကို သွားကြည့်ခြင်း) ကို သုံးပါ

အခြေအနေ F: Sensor (ပတ်ဝန်းကျင် အပြောင်းအလဲကို ထောက်လှမ်းတဲ့ ကိရိယာ) ရဲ့ နောက်ဆုံး ဖတ်ချက် 100 ခုကို မှတ်ထားခြင်း

လိုအပ်ချက်: အရွယ်အစား ပုံသေ buffer၊ index နဲ့ မြန်မြန် ယူသုံးနိုင်ရမယ်
ပုံစံ: အရွယ်အစား ပုံသေ၊ index နဲ့ ယူသုံးခြင်း
အကောင်းဆုံး ရွေးချယ်မှု: Array။ အရွယ်အစားကို သိပြီးသား၊ index နဲ့ ယူရင် O(1)

ဥပမာ 2: မြန်နှုန်း နှိုင်းယှဉ်ချက်

ဒီဥပမာက element 1000 ပါတဲ့ collection တစ်ခုပေါ်မှာ အဖြစ်များတဲ့ အလုပ်တွေအတွက် structure အမျိုးမျိုးက operation ဘယ်နှစ်ခု လိုလဲ တိုင်းကြည့်ပါတယ်။

အလုပ်	Array	LinkedList	BST (balanced)	HashSet
Element ရှာခြင်း	ပျမ်းမျှ 500 (linear: n နဲ့ အချိုးကျ)	ပျမ်းမျှ 500 (linear)	ပျမ်းမျှ 10 (log2 1000)	ပျမ်းမျှ 1 (hash)
အဆုံးမှာ ထည့်ခြင်း	1 (နေရာ ရှိရင်)	1 (tail reference ရှိရင်)	ပျမ်းမျှ 10	ပျမ်းမျှ 1
Sorted နေရာမှာ ထည့်ခြင်း	ပျမ်းမျှ 500 (ရွှေ့ရ)	ပျမ်းမျှ 500 (traverse လုပ်ရ)	ပျမ်းမျှ 10	မသက်ဆိုင် (အစဉ် မရှိ)
သတ်မှတ်ထားတဲ့ element ကို ဖျက်ခြင်း	ပျမ်းမျှ 500 (ရွှေ့ရ)	ပျမ်းမျှ 500 (traverse လုပ်ရ)	ပျမ်းမျှ 10	ပျမ်းမျှ 1
Sorted output ရယူခြင်း	n log n (အရင် sort လုပ်ရ)	n log n (အရင် sort လုပ်ရ)	n (in-order traversal)	n log n (အရင် sort လုပ်ရ)

O(1) ဆိုတာ “ချက်ချင်း” လို့ မဆိုလိုပါဘူး။ Input size (program ထဲ ထည့်ပေးတဲ့ ဒေတာ ပမာဏ) ကြီးလာလည်း အချိန် မတိုးဘူးလို့ ဆိုလိုတာပါ။ Collection သေးရင် hash table lookup က array ကို index နဲ့ ယူတာထက် နှေးနိုင်ပေမယ့် collection ကြီးလာရင်တော့ အများကြီး ပိုကောင်းပါတယ်။

ဥပမာ 3: မှားတဲ့ structure နဲ့ မှန်တဲ့ structure

import java.util.ArrayList;
import java.util.HashSet;

public class DuplicateCheck {
    // SLOW approach: ArrayList contains() is O(n) per check
    public static boolean hasDuplicatesSlow(String[] words) {
        ArrayList<String> seen = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            if (seen.contains(w)) {    // O(n) each time
                return true;
            }
            seen.add(w);
        }
        // for-each version: for (String w : words) { ... }
        return false;
    }

    // FAST approach: HashSet contains() is O(1) per check
    public static boolean hasDuplicatesFast(String[] words) {
        HashSet<String> seen = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            if (seen.contains(w)) {    // O(1) each time
                return true;
            }
            seen.add(w);
        }
        // for-each version: for (String w : words) { ... }
        return false;
    }

    public static void main(String[] args) {
        String[] words = {"apple", "banana", "cherry", "date", "banana"};
        System.out.println("Slow: " + hasDuplicatesSlow(words));
        System.out.println("Fast: " + hasDuplicatesFast(words));
    }
}

# SLOW approach: "in" on a plain list is O(n) per check (like ArrayList contains)
def has_duplicates_slow(words):
    seen = []
    for i in range(len(words)):
        w = words[i]
        if w in seen:     # O(n) each time
            return True
        seen.append(w)
    # for-each version: for w in words:
    return False

# FAST approach: "in" on a set is O(1) per check (Python's set is like HashSet)
def has_duplicates_fast(words):
    seen = set()
    for i in range(len(words)):
        w = words[i]
        if w in seen:     # O(1) each time
            return True
        seen.add(w)
    # for-each version: for w in words:
    return False

words = ["apple", "banana", "cherry", "date", "banana"]
print("Slow:", has_duplicates_slow(words))    # Python prints True/False with a capital letter
print("Fast:", has_duplicates_fast(words))

Output:

Slow: true
Fast: true

Method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း) နှစ်ခုလုံးက အဖြေ အတူတူ ပေးပေမယ့် ArrayList နည်းက စုစုပေါင်း O(n^2) ဖြစ်ပါတယ် (စကားလုံး n လုံး ရှိပြီး တစ်လုံးစီက အရင် စကားလုံး n လုံးအထိ စစ်ရလို့ပါ)။ HashSet နည်းက စုစုပေါင်း O(n) ပါ (စကားလုံး n လုံး ရှိပြီး တစ်လုံးစီကို O(1) နဲ့ စစ်လို့ပါ)။ စကားလုံး 10,000 ဆိုရင် ArrayList နည်းက comparison (တန်ဖိုး နှစ်ခုကို နှိုင်းယှဉ်ခြင်း) 50,000,000 အထိ လိုနိုင်ပြီး HashSet နည်းက 10,000 လောက်ပဲ လိုပါတယ်။

Quick Check (အမြန် စစ်ဆေးမေးခွန်း)

Q1. ကျောင်းသား တစ်ယောက်ရဲ့ grade ကို သူ့နာမည်နဲ့ ရှာဖို့ ဘယ် structure က အသင့်တော်ဆုံးလဲ။

Q2. Application တစ်ခုမှာ နောက်ဆုံး လုပ်ခဲ့တာကို အရင် ပြန်ဖျက်ပေးတဲ့ "undo" feature တစ်ခု လိုပါတယ်။ ဘယ် structure က အသင့်တော်ဆုံးလဲ။

Q3. Spell checker တစ်ခုက စကားလုံး 1 သန်း ပါတဲ့ အဘိဓာန်ထဲမှာ စကားလုံး တစ်လုံး ရှိမရှိ စစ်ဖို့ လိုပါတယ်။ ဘယ်ဟာက အမြန်ဆုံး lookup ကို ပေးသလဲ။

Q4. မြန်မြန် ရှာနိုင်ရမယ်၊ မြန်မြန် ထည့်နိုင်ရမယ်၊ ပြီးတော့ sorted output ကိုလည်း ထုတ်ပေးနိုင်ရမယ့် structure တစ်ခု လိုပါတယ်။ ဘယ်ဟာက အသင့်တော်ဆုံးလဲ။

Q5. Printer တစ်လုံးက အလုပ်တွေကို ပို့လိုက်တဲ့ အစဉ်အတိုင်း လုပ်ပါတယ်။ ဒါကို ဘယ် structure က ကိုယ်စားပြုသလဲ။

Trace Exercise (code ကို တစ်ဆင့်ချင်း လိုက်ကြည့်ခြင်း)

အခြေအနေ တစ်ခုစီအတွက် အသင့်တော်ဆုံး data structure နဲ့ သူ့ရဲ့ အဓိက အားသာချက်ကို ဖြည့်ပါ။ Structure နာမည်နဲ့ အားသာချက် နှစ်ခုလုံးကို English လို ရိုက်ထည့်ပါ။

အခြေအနေ	အသင့်တော်ဆုံး structure	အဓိက အားသာချက်
List ထဲက ထပ်နေတဲ့ email လိပ်စာတွေကို ဖယ်ခြင်း
Customer service ticket (ဖောက်သည်တွေရဲ့ အကူအညီ တောင်းခံချက်) တွေကို ရောက်လာတဲ့ အစဉ်အတိုင်း ဆောင်ရွက်ခြင်း
စာအုပ် တစ်အုပ်ထဲမှာ စကားလုံး တစ်ခုစီ ဘယ်နှစ်ကြိမ် ပါလဲ ရေတွက်ခြင်း
Browser ရဲ့ back/forward history မှာ ရှေ့နောက် သွားခြင်း
နာမည်အလိုက် စီထားပြီး မြန်မြန် ရှာနိုင်တဲ့ ဖုန်းစာအုပ်ကို သိမ်းခြင်း

Structure တစ်ခုစီပေါ်က operation တစ်ခုစီရဲ့ time complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ) ကို ဖြည့်ပါ။

Operation	Array	LinkedList	BST (balanced)	HashSet
Search
Insert			O(log n)
Delete (value နဲ့)

Code Completion (code ကွက်လပ် ဖြည့်ခြင်း)

ထပ်နေတာ ရှာတဲ့ အလုပ်အတွက် မှန်ကန်တဲ့ structure ကို ရွေးသုံးတဲ့ code ကို ပြည့်စုံအောင် ဖြည့်ပါ။

Array ထဲမှာ ထပ်နေတဲ့ တန်ဖိုး ရှိမရှိကို အမြန်ဆုံး နည်းနဲ့ စစ်ပါ:

public static boolean hasDuplicates(int[] arr) {
    <Integer> seen = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        int val = arr[i];
        if (seen.(val)) {
            return true;
        }
        seen.(val);
    }
    return false;
}

Character (စာလုံး ဒါမှမဟုတ် သင်္ကေတ) တွေ ဘယ်နှစ်ကြိမ် ပါလဲ ရေတွက်ဖို့ HashMap ကို သုံးတဲ့ code ကို ပြည့်စုံအောင် ဖြည့်ပါ။

String (စာသား) တစ်ခုထဲမှာ character တစ်ခုစီ ဘယ်နှစ်ကြိမ် ပါလဲ ရေတွက်ပါ:

HashMap<Character, Integer> freq = new HashMap<>();
for (int i = 0; i < text.length(); i++) {
    char c = text.charAt(i);
    if (freq.(c)) {
        freq.put(c, freq.get(c) + );
    } else {
        freq.(c, 1);
    }
}

Spot the Error (အမှား ရှာခြင်း)

ထပ်နေတာ စစ်တဲ့ ဒီ code က မှန်မှန်ကန်ကန် အလုပ်လုပ်ပေမယ့် array ကြီးကြီးတွေအတွက် အရမ်း နှေးပါတယ် (element 100,000 အတွက် မိနစ်ချီ ကြာပါတယ်)။ Bug (code ထဲက အမှား) က structure ကို မှားရွေးထားတာပါ:

1public static boolean hasDuplicates(int[] arr) { 2 ArrayList<Integer> seen = new ArrayList<>(); 3 for (int i = 0; i < arr.length; i++) { 4 int val = arr[i]; 5 if (seen.contains(val)) return true; 6 seen.add(val); 7 } 8 return false; 9}

မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

ဒီ print queue က အလုပ်တွေကို မှားတဲ့ အစဉ်နဲ့ လုပ်နေပါတယ်: ပထမဆုံး ပို့လိုက်တဲ့ အလုပ်အစား နောက်ဆုံး ပို့လိုက်တဲ့ အလုပ်ကို အရင် print ထုတ်နေပါတယ်:

1// Print queue: should process first-come, first-served 2Stack<String> printJobs = new Stack<>(); 3printJobs.push("Report.pdf"); 4printJobs.push("Photo.jpg"); 5String next = printJobs.pop(); // gets Photo.jpg, not Report.pdf

Comment တွေရဲ့ အဓိပ္ပာယ်: line 1 က “print queue: အရင်ရောက်တာကို အရင် လုပ်ရမယ်”၊ line 5 က “Report.pdf မဟုတ်ဘဲ Photo.jpg ကို ရတယ်” လို့ ဆိုလိုပါတယ်။

မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)

ဒီ code က ဘာကို print ထုတ်သလဲ။

HashSet<String> set = new HashSet<>();
set.add("A");
set.add("B");
set.add("C");
set.add("A");
set.add("B");
System.out.println(set.size());
System.out.println(set.contains("D"));

Output ကို အတိအကျ ရိုက်ထည့်ပါ:

ဒီ code က ဘာကို print ထုတ်သလဲ။

Stack<String> stack = new Stack<>();
stack.push("Doc1");
stack.push("Doc2");
stack.push("Doc3");
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.size());

Output ကို အတိအကျ ရိုက်ထည့်ပါ:

Practice Exercises (လေ့ကျင့်ခန်းများ)

Core (အခြေခံ အဆင့်)

Structure ကို တွဲပါ: အခြေအနေ တစ်ခုစီအတွက် အသင့်တော်ဆုံး data structure ကို State (ဖော်ပြပါ) လုပ်ပြီး အကြောင်းပြချက် တစ်ခု ပေးပါ: (a) မထပ်ရမယ့် username (အသုံးပြုသူ အမည်) တွေကို သိမ်းခြင်း၊ (b) ဆေးရုံ လူနာတွေကို ရောက်လာတဲ့ အစဉ်အတိုင်း ဆောင်ရွက်ခြင်း၊ (c) နိုင်ငံ code တွေကို နိုင်ငံ နာမည်တွေနဲ့ တွဲခြင်း၊ (d) web browser ရဲ့ back ခလုတ်ကို တည်ဆောက်ခြင်း။
Complexity (input ကြီးလာရင် လုပ်ရတဲ့ အလုပ် တိုးလာပုံ) ဇယား: မှတ်စုတွေကို မကြည့်ဘဲ မှတ်မိသလောက်နဲ့ ဒီဇယားကို ကူးရေးပြီး ဖြည့်ပါ: Array၊ LinkedList၊ BST (balanced) နဲ့ HashSet အတွက် Search၊ Insert နဲ့ Delete complexity။
ရွေးချယ်မှုကို Justify (ဘာကြောင့် ရွေးတာလဲ အကြောင်းပြချက်နဲ့ ပြပါ) လုပ်ပါ: ဆရာ တစ်ယောက်က ကျောင်းသား အမှတ်တွေကို ArrayList<Integer> ထဲမှာ သိမ်းထားပါတယ်။ သတ်မှတ်ထားတဲ့ အမှတ် တစ်ခု (ဥပမာ 95) ရှိမရှိကို မြန်မြန် စစ်ချင်ပါတယ်။ ဒါ ဘာကြောင့် နှေးလဲဆိုတာကို Explain (ရှင်းပြပါ) လုပ်ပြီး ပိုကောင်းတဲ့ structure တစ်ခု အကြံပြုပါ။

Extension (တိုးချဲ့ အဆင့်)

မြန်အောင် Refactor (code ရဲ့ ရလဒ် မပြောင်းဘဲ ပုံစံကို ပြင်ရေးခြင်း) လုပ်ပါ: Element 10,000 ပါတဲ့ array ထဲမှာ ထပ်နေတာတွေကို LinkedList နဲ့ ရှာတဲ့ code (O(n^2)) ကို ပေးထားပါတယ်။ O(n) ရအောင် HashSet ကို သုံးပြီး ပြန်ရေးပါ။ Version တစ်ခုစီမှာ contains ကို ခေါ်တဲ့ အကြိမ်ရေကို ရေတွက်ပြီး ဘယ်လောက် ပိုကောင်းလာလဲ တိုင်းကြည့်ပါ။
Structure အများ သုံးတဲ့ ဖြေရှင်းချက်: ကျောင်း စီမံခန့်ခွဲရေး စနစ် တစ်ခုက ဒီအလုပ်တွေ လုပ်နိုင်ရပါမယ်: (a) ကျောင်းသား တစ်ယောက်ကို ID နဲ့ (မြန်မြန်) ရှာခြင်း၊ (b) ကျောင်းသား အားလုံးကို အက္ခရာစဉ်အတိုင်း ပြခြင်း၊ (c) ကျောင်းဝင်ခွင့် လျှောက်လွှာတွေကို FIFO အစဉ်နဲ့ ဆောင်ရွက်ခြင်း။ လိုအပ်ချက် တစ်ခုစီအတွက် ဘယ် structure ကို သုံးမလဲ State လုပ်ပြီး structure တစ်ခုတည်းနဲ့ သုံးခုလုံးကို ဘာကြောင့် မလုပ်နိုင်လဲ Explain လုပ်ပါ။
BST နဲ့ HashMap: ကျပန်း integer (ကိန်းပြည့်) 1000 ကို BST တစ်ခုထဲရော HashSet တစ်ခုထဲပါ ထည့်ပါ။ ပြီးရင် ကျပန်း တန်ဖိုး 100 ကို ရှာပါ။ Comparison အရေအတွက်တွေကို နှိုင်းယှဉ်ပါ။ ဘယ်အချိန်မှာ HashSet ထက် BST ကို ပိုသုံးချင်မလဲ။

Challenge (စိန်ခေါ်မှု အဆင့်)

စာကြည့်တိုက် စနစ် တစ်ခုကို Design (အစီအစဉ် ဒါမှမဟုတ် model တစ်ခု ရေးဆွဲပါ) လုပ်ပါ: စာကြည့်တိုက် တစ်ခုက ဒီအလုပ်တွေ လုပ်ဖို့ လိုပါတယ်: စာအုပ် အားလုံးကို ခေါင်းစဉ်၊ စာရေးသူနဲ့ ISBN (စာအုပ် တစ်အုပ်ချင်းရဲ့ နိုင်ငံတကာ အမှတ်) တို့နဲ့ မှတ်ထားခြင်း၊ ISBN နဲ့ စာအုပ် ရှာခြင်း၊ စာရေးသူ တစ်ယောက်ရဲ့ စာအုပ် အားလုံးကို ရှာခြင်း၊ စာအုပ် ကြိုတင် မှာကြားချက်တွေကို FIFO အစဉ်နဲ့ ဆောင်ရွက်ခြင်း။ ဒီစနစ်အတွက် data structure တွေကို ဒီဇိုင်းဆွဲပါ။ လိုအပ်ချက် တစ်ခုစီအတွက် ဘယ် structure ကို သုံးမလဲ State လုပ်ပြီး ကိုယ့်ရွေးချယ်မှုတွေကို Justify လုပ်ပါ။
Exam-style question (စာမေးပွဲ ပုံစံ မေးခွန်း): “ကုမ္ပဏီ တစ်ခုက ဝန်ထမ်း record (အချက်အလက် အများကြီး စုထားတဲ့ ဒေတာ တစ်ခု) တွေကို သိမ်းထားပါတယ်။ စနစ်က ဒီအလုပ်တွေကို လုပ်နိုင်ရပါမယ်: (i) ဝန်ထမ်း အသစ်တွေ ထည့်ခြင်း၊ (ii) ဝန်ထမ်း တစ်ယောက်ကို ID နဲ့ ရှာခြင်း၊ (iii) ဝန်ထမ်း အားလုံးကို နာမည်အလိုက် စီပြီး ပြခြင်း။ ဒီစနစ်အတွက် array၊ linked list၊ BST နဲ့ HashMap ကို သုံးတာကို Evaluate (အားသာချက်နဲ့ အားနည်းချက်တွေကို ချိန်ဆပြီး အကဲဖြတ်ပါ) လုပ်ပါ။ Structure တစ်ခုစီအတွက် အားသာချက် တစ်ခုနဲ့ အားနည်းချက် တစ်ခုကို State လုပ်ပါ။ လိုအပ်ချက် သုံးခုလုံးကို ပြည့်မီစေမယ့် structure တွေရဲ့ ပေါင်းစပ်မှု တစ်ခုကို အကြံပြုပါ။” (8 marks) 8 marks ဆိုတာ IB စာမေးပွဲ ပုံစံအတိုင်း ဒီမေးခွန်းအတွက် ပေးထားတဲ့ အမှတ် 8 မှတ်ပါ။

ဆက်စပ် ခေါင်းစဉ်များ

အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: ADT စာမျက်နှာ အားလုံး။ ဒီစာမျက်နှာက အပိုင်း တစ်ခုလုံးက အသိပညာတွေကို ပေါင်းစပ်ထားပါတယ်
- What Are ADTs? (ADT ဆိုတာ ဘာလဲ): interface (class တစ်ခု implement လုပ်ရမယ့် method စာရင်း) နဲ့ implementation ကွာခြားချက်
- Linked Lists, Ordered Linked Lists, Doubly Linked Lists
- Stacks from Scratch, Queues from Scratch
- Binary Search Trees, BST Operations
- Sets and HashMaps
ဆက်စပ် ခေါင်းစဉ်: Stacks နဲ့ Queues (B2.2: အသင့်ပါတဲ့ class တွေကို သုံးခြင်း)
ဆက်စပ် ခေါင်းစဉ်: Searching Algorithms (ရှာဖွေရေး algorithm များ): မြန်နှုန်းကို ခွဲခြမ်းစိတ်ဖြာတာက structure ရွေးချယ်မှုနဲ့ ဆက်စပ်နေပါတယ်
ဆက်စပ် ခေါင်းစဉ်: Big O Notation (algorithm ရဲ့ ကြာချိန် တိုးနှုန်းကို ပြတဲ့ သင်္ကေတ): structure တွေကို နှိုင်းယှဉ်ဖို့ သုံးတဲ့ မူဘောင်ပါ