မြန်မာဘာသာဖြင့်လွယ်ကူစွာလေ့လာနိုင်ရန်အတွက် စီလျှော်အောင်ဘာသာပြန်ပေးထားတာဘဲဖြစ်ပါတယ်။ မှားယွှင်းလွှဲချော်နေတာတွေ့လျှင် PR ဖွင့်ပီးကူညီပြင်ဆင်ပေးနိုင်ပါတယ်။ Data structure ကိုစိတ်ဝင်စားတဲ့အသိမိတ်ဆွေတွေကိုလဲ ဒီ repo ကိုပြန်လည်ဝေမျှနိုင်ပါတယ်။
ဘာသာပြန်အစအဆုံးကို YGNCode မှာဖတ်ရှုနိုင်ပါတယ်။
Wikipeda မှာတော့ Data Structure ဆိုတာ Data တွေကို Store (သိမ်းဆည်းဖို့) နှင့် efficiently access/modification လုပ်နိုင်တဲ့ Data Organization တစ်ခုဖြစ်တယ်လို့မှတ်သားရပါတယ် (ဘာသာပြန်တာမှားကောင်းမှားနိုင်လို့ ကိုယ်တိုင် Wikipedia မှာရှာဖွေဖတ်ရှုစေချင်ပါတယ်)။
ကျွန်တော်တို့ Data တွေကို နည်းမျိုးစုံနှင့်ဖော်ပြနိုင်တယ်။ ဒါပေမယ့် ဒီ data ကဘာလဲ အဲ့ဒါကိုဘယ်နေရာအတွက်သုံးမှာလဲပေါ်မူတည်ပြီးတော့ ဘယ်လို data structure ကိုအသုံးပြုမလဲဆိုတာကိုဆုံးဖြတ်ရပါမယ်။ Data Structure တွေမှာလည်း သူ့အားသာတဲ့အပိုင်း၊ အားနည်းတဲ့အပိုင်းရှိတာမို့လို့ ကိုယ်အသုံးပြုလိုတဲ့အပေါ်မူတည်ပြီးအသင့်တော်ဆုံး data structure ကိုယူသုံးရပါမယ်။
အဲဒီအားသာချက်၊ အားနည်းချက်တွေကိုနားလည်ဖို့ရာအတွက် algorithms အကြောင်းနည်းနည်းပြောလိုက်ရအောင်။
ပထမဆုံး Algorithm ဆိုတာဘာလဲက စမယ်။ Algorithm ဆိုတာ ဒါပြီးရင် ဒါလုပ် ဒါပြီးရင် ဒါလုပ်ဆိုတဲ့ sets of operations တွေကိုထွင်ပြီးခေါ်ထားတာပါဘဲ။
Data structure နှင့် Algorithm တွေ ဘယ်လိုဆက်စပ်နေလဲဆိုလျှင် Data structure တွေကို algorithm တွေနှင့်တည်ဆောက်ထားတာဖြစ်ပြီးတော့ algorithm တွေကို data structure တွေနှင့် တည်ဆောက်ထားတာဖြစ်ပါတယ်။ (အပြန်အလှန်ပဲပေါ့)
လုပ်စရာအလုပ်တစ်ခုပေးလိုက်ပေးလိုက် အဲဒါကိုဖြေရှင်းဖို့ မြောက်များစွာသောနည်းတွေရှိပါတယ်။ လူတွေက ယေဘုယျအားဖြင့် (ပုံမှန်အသုံးလိုတဲ့) အလုပ် တစ်ခုပေးလိုက်တယ်ဆိုလျှင် တစ်ယောက်တစ်မျိုးစီ အဲ့ အလုပ် ကိုဖြေရှင်းဖို့နည်းတွေထွက်လာပါတယ်။
ဥပမာ၊ unsorted item တွေကို sort လုပ်ဖို့ရာအတွက် algorithms တွေက နည်းတာမဟုတ်ဘူး... အောက်က sorting algorithm တချို့ကို ကြည့်လိုက်ရအောင်...
Insertion Sort, Selection Sort, Merge Sort, Bubble Sort, Heap Sort,
Quick Sort, Shell Sort, Timsort, Bucket Sort, Radix Sort, ...
ဒီ sorting နည်းတွေထဲမှာဆိုလျှင် တချို့ algorithm တွေက တချို့ algorithm တွေထက် ပိုမြန်တယ်။ တချို့ algorithm က memory အသုံးပြုမှုနည်းတယ်။ တချို့ algorithm က လွယ်လွယ်ကူကူ implement လုပ်နိုင်တယ်။ တချို့က dataset နှင့် ပတ်သက်တဲ့ assumption ပေါ်အခြေခံထားတယ်။
ဒီ algorithm တွေမှာ တခုနှင့်တခု ပိုကောင်းတာ ပိုဆိုးတာတွေရှိတယ်။ ဒါကြောင့် ဒီ algorithm တွေကို ကိုယ့်လိုအပ်ချက်ပေါ်မူတည်ပြီး ဘယ်ဟာကို သုံးရမလဲဆိုပြီး ဆုံးဖြတ်ဖို့ရာအတွက် တိုင်းတာဖို့ နည်းတစ်ခုလိုတယ်။ Algorithm တွေရဲ့ ပျမ်းမျှနှင့် အဆိုးဆုံးအခြေအနေ စွမ်းဆောင်ရည်တွေကို တိုင်းတာဖို့ရာအတွက် "Big-O" လို့ခေါ်တဲ့ တိုင်းတာမှုကို သုံးတယ်။
အခု အောက်မှာ Big O Notation အကြောင်း နည်းနည်းထပ်ရှင်းပြမယ်...
Algorithm တစ်ခုနှင့်တစ်ခု ဘယ် algorithm ကပိုမြန်တယ်/ပိုနှေးတယ်ဆိုတာတွေကို ယေဘူယျအားဖြင့်တိုင်းတာဘဲ ဖြစ်ဖြစ် အချင်းချင်းဘယ်ဟာကတော့ပိုနှေးတယ်ပိုမြန်တယ်ဆိုတာပြီး Disucss လုပ်တဲ့နေရာမှာဘဲဖြစ်ဖြစ် Big-O Notatio ကို ကျွန်တော်တို့အသုံးပြုကြတယ်။
Big-O ဆိုတာ သင်္ချာသင်္ကေတတစ်ခုပါဘဲ။ ဒါကို computer science မှာ algorithm တစ်ခုမှာ input (ပေးလိုက်တဲ့ number) (N) အရေအတွက်ပေါ်မူတည်ပြီး algorithms တွေရဲ့ အမျိုးအစားကို ခွဲခြားတဲ့နေရာမှာသုံးကြတယ်။
Big-O ကို ကျွန်တော်တို့ အဓိကသုံးတဲ့ တိုင်းတာမှုနှစ်ခုရှိတယ်... အဲ့ဒါကဘာတွေလဲဆိုလျှင် Time complexity နှင့် Space complexity ဖြစ်တယ်။ အောက်မှာအဲ့နှစ်ခုရဲ့ ဆိုလိုရင်းကို တစ်ချက်နည်းနည်းထပ်ပြောပြထားတယ်။
Time complexity ဆိုတာ algorithm မှာ ပေးလိုက်တဲ့ items ပေါ်မူတည်ပြီး operate လုပ်တဲ့အရေအတွက်ကိုတွက်တာကိုပြောတာဖြစ်တယ်။
Space complexity ဆိုတာ ပေးလိုက်တဲ့ items ပေါ်မူတည်ပြီး memory ဘယ်လောက်အသုံးပြုလဲဆိုပြီး တွက်တာကိုပြောတာဖြစ်တယ်။
ဘာလို့ Time complexity နှင့် Space complexity ကိုခွဲထားတာလဲဆိုလျှင် algorithm တွေက operate လုပ်တာနည်းပေမယ့် memory space အများကြီးယူနိုင်တယ် တစ်ခုနှင့်တစ်ခုမတူဘူး ဒါကြောင့်ကိုယ်လိုအပ်တဲ့နေရာမှာ ဒီနှစ်ခုထဲကတစ်ခုပိုကောင်းလျှင်ရတယ်ဆိုတာမျိုးတွေရှိလာလျှင် ရွေးချယ်နိုင်အောင်ကြောင့်ဖြစ်တယ်။
အောက်ဖော်ပြပါ table မှာ အသုံးများတဲ့ (common ဖြစ်တဲ့) Big-O တွေကို ကြည့်ကြည့်ရအောင်...
| အခေါ်အဝေါ် | သင်္ကေတ | အဆိုး/အကောင်း/အကြိုး/အကြောင်း |
|---|---|---|
| Constant | O(1) | AWESOME!! |
| Logarithmic | O(log N) | GREAT! |
| Linear | O(N) | OKAY |
| Linearithmic | O(N log N) | UGH... |
| Polynomial | O(N ^ 2) | SHITTY |
| Exponential | O(2 ^ N) | HORRIBLE |
| Factorial | O(N!) | WTF |
ကျနော်တို့ပြောနေတဲ့ operations တွေကဘယ်လိုလဲဆိုတဲ့ idea ရအောင် အောက်ဖော်ပြပါ နမူနာ (N) numbers of items ကိုကြည့်ကြည့်လိုက်ကြရအောင်
N = 5 10 20 30
-----------------------------------------------------------------------
O(1) 1 1 1 1
O(log N) 2.3219... 3.3219... 4.3219... 4.9068...
O(N) 5 10 20 30
O(N log N) 11.609... 33.219... 84.638... 147.204...
O(N ^ 2) 25 100 400 900
O(2 ^ N) 32 1024 1,048,576 1,073,741,824
O(N!) 120 3,628,800 2,432,902,0... 265,252,859,812,191,058,636,308,480,000,000
ခင်ဗျားတွေ့ခဲ့တဲ့အတိုင်းဘဲ data အသေးအဖွဲ့လေးတောင် အပိုအလုပ်တွေအများကြီးလုပ်နေရတယ်။
Data structures နှင့်ဆို ခင်ဗျားလုပ်ဆောင်နိုင်တဲ့ အဓိက ၄ မျိုးရှိတယ်။ ဘာတွေလဲဆိုလျှင် Accessing (သုံး/access လုပ်), Searching (ရှာ), Inserting (ထပ်ထည့်တာ) နှင့် Deleting (ဖြုတ်ထုတ်တာ) တို့ဖြစ်တယ်။
ခင်ဗျား data structure တွေကိုသုံးတဲ့နေရာမှာသတိထားရမှာက တချို့လုပ်ဆောင်ချက်တွေမှာ တချို့ data structure တွေကကောင်းပီးတော့ တချို့လုပ်ဆောင်ချက်တွေမှာ မကောင်းတာမျိုးရှိတယ်ဆိုတာဘဲ။
အောက်က နမူနာ တချက်ကြည့်ကြည့်ရအောင်
Accessing Searching Inserting Deleting
-------------------------------------------------------------------------
Array O(1) O(N) O(N) O(N)
Linked List O(N) O(N) O(1) O(1)
Binary Search Tree O(log N) O(log N) O(log N) O(log N)
ပုံမှန်နားလည်လွယ်တဲ့စကားနဲ့ဆိုရင်
Accessing Searching Inserting Deleting
-------------------------------------------------------------------------
Array AWESOME!! OKAY OKAY OKAY
Linked List OKAY OKAY AWESOME!! AWESOME!!
Binary Search Tree GREAT! GREAT! GREAT! GREAT!
နောက်တဆင့်ဆက်သွားကြမယ်ဆိုရင် တချို့ actions တွေက average performance နှင့် worst case scenario performance မှာ တမျိုးစီမတူတာမျိုးရှိတယ်။ (Average မှာအရမ်းမြန်ပီး worst case မှာအရမ်းနှေးတာမျိုးပေါ့)
Perfect data structure ဆိုတာမရှိပါဘူး... ကိုယ့် data ပေါ်မူတည်ပီးကိုယ်ဘာလုပ်ချင်တယ်ဆိုတဲ့ပေါ်မူတည်ပီးတော့ ရွေးကြရတာပါ။ ဒါကြောင့်မလို့ မတူညီတဲ့ ယေဘူယျ data structure တွေကိုသိထားဖို့လိုတာပါ။ ဒါမှခင်ဗျားရွေးချယ်နိုင်မှာကိုး။
/*** ===================================================================== ***\
** - MEMORY -------------------------------------------------------------- **
* ========================================================================= *
* _.-.. *
* ,'9 )\)`-.,.--. *
* `-.| `. *
* \, , \) *
* `. )._\ (\ *
* |// `-,// *
* ]|| //" *
** hjw "" "" **
\*** ===================================================================== ***/
တကယ်တော့ ကွန်ပျူတာရဲ့ memory ဆိုတာကြီးကပျင်းစရာကြီး။ သူ့မှာ တန်းစီနေတဲ့အကွက်တွေရှိတယ် အဲ့ထဲကိုခင်ဗျားသိမ်းချင်တဲ့ အချက်အလက်တွေကိုထည့်ထားလို့ရတယ်။ ခင်ဗျားသိမ်းထားတဲ့ memory ရဲ့ address ကိုတော့မှတ်ထားရမှာပေါ့။
Memory ရဲ့တန်းစီနေတဲ့အကွက်တွေ ဆိုတာကိုအောက်ကလိုမျိုးဆိုပီးတချက်တွေးကြည့်လိုက်ရအောင်...
Values: |1001|0110|1000|0100|0101|1010|0010|0001|1101|1011...
Addresses: 0 1 2 3 4 5 6 7 8 9 ...
Programming languages တွေမှာဘာလို့ zero ကနေ index စလဲလို့ခင်ဗျားတွေးဖူးတယ်ဆိုရင် အဖြေက memory အလုပ်လုပ်တဲ့ပုံစံကြောင့်ပါဘဲ။ ခင်ဗျား memory ရဲ့ပထမအကွက်ကို read ချင်တယ်ဆိုရင် ၀ ကနေ ၁ ကို read ရမယ်။ ဒုတိယအကွက်ကို ဆိုရင်တော့ ၁ ကနေ ၂ ကိုပေါ့။
ခင်ဗျားကွန်ပျူတာက အခုကျနော်နမူနာပြထားတာထက်အများကြီးပိုတယ်။ ဒါတွေကို read တာက အပေါ်ကရှင်းပြထားတဲ့ပုံစံအတိုင်းဘဲဆက်သွားရမှာပေါ့။
ခင်ဗျားစက်ပေါ်မှာ run နေတဲ့ program တွေကို physical data structure အနေနှင့်သိမ်းထားရရင် Memory ကတယ့်ကသိုင်းကရိုင်းဘဲဗျ။ abstraction အလွှာလွှာမပါဘဲနှင့်ဆိုရင် သူ့ကိုသုံးဖို့ တော်တော်ခက်ခဲမယ်။
Abstraction ဆိုတာ ဘာမှန်းမသိသေးရင် ဒီ YouTube video ကိုကြည့်ဖို့တိုက်တွန်းပါတယ်။
ဒီ abstractions ၂ ခုက နောက်ထက် ရည်ရွယ်ချက် ၂ ခုကိုဖြစ်စေတယ်
-
memory ထဲမှာ data store လုပ်ပီး အကျိုးရှိရှိ နှင့်(သို့) မြန်ဆန်စွာ အသုံးပြုနိုင်အောင်လုပ်တာ
-
memory ထဲမှာ data store လုပ်ပီး လွယ်ကူစွာအသုံးပြုနိုင်အောင်လုပ်တာ