Software Engineering အင်တာဗျူးတွေမှာ မေးလေ့ရှိတဲ့ မေးခွန်းတခု

Alibaba တို့၊ Amazon တို့လိုမျိုး ecommerce တခုမှာ user က သူသုံးချင်တဲ့ budget ပမာဏတခု သတ်မှတ်ပြီး ပစ္စည်းတွေ ပြခိုင်းတယ်ဆိုပါတော့။ ကျွန်တော်တို့က အဲဘတ်ဂျက်နဲ့ အနီးစပ်ဆုံး ပစ္စည်းတွေကို ပြမယ်။

ဒီအတွက် ဖြေရှင်းနည်းက SQL query မှာ price နဲ့ budget ခြားနားချက်ကို Absolute function သုံးတွက်ပြီး ရလာတဲ့ တန်ဖိုးကို sorting criteria အဖြစ် ထားလိုက်ရင် အိုကေပါပြီ။ ဒါပေမယ့် ဆိုပါတော့။ price နဲ့ sort ထားတဲ့ product တွေက sequential list တခုထဲကို ရောက်နှင့်နေပြီ။ budget နဲ့ အနီးစပ်ဆုံး product တွေကို memory ပေါ်မှာပဲ ရွေးထုတ်ပေးရတော့မယ်ဆိုရင် ဘယ်လိုဖြေရှင်းမလဲ။

ဒီပြဿနာကို K nearest Element လို့ လူသိများပါတယ်။ သူနဲ့ concept ဆင်တူတဲ့ multi-dimentional use case တွေဆိုရင် Google Search Engine မှာ query အလိုက် document တွေကို relevancy ranking စီတာ။ Google Map မှာ Places Near Me လို့ ရှာလိုက်ရင် အနီးနားက လည်ပတ်စရာတွေကို ပြပေးတာ။ recommendation ပါတဲ့ Netflix လိုမျိုး app မှာ user history, popularity နဲ့ content စသဖြင့် ဒါတွေအပေါ် မူတည်ပြီး ညွှန်းပေးတာမျိုးတွေပါ။ ဒီဥပမာတွေမှာ သုံးရမယ့် data structure နဲ့ distance တွက်တာ ကွာပေမယ့် high level concept ဆင်တူကြပါတယ်။

ဒါပေမယ့် အပေါ်ကလို budget နဲ့အနီးစပ်ဆုံး product တွေ ရွေးထုတ်တာမျိုးကတော့ ရိုးရှင်းပြီး တွက်ပျော်တဲ့ ပြဿနာမျိုးဖြစ်တာမို့ SWE အင်တာဗျူးတွေမှာ ခဏခဏ မေးတတ်ပါတယ်။ list တခု [1, 2, 4, 7, 8, 11] က price တွေဖြစ်ပြီး budget က 6 USD ဖြစ်တယ်ဆိုပါတော့။ budget နဲ့ အနီးစပ်ဆုံးပစ္စည်း 3 ခုကို ရွေးရမယ်။ နီးစပ်တဲ့ gap ချင်းတူရင် စျေးသက်သာတဲ့ ပစ္စည်းကို ဦးစားပေးမယ်။ ဘယ်လိုရွေးမလဲ။

ဖြေရှင်းနည်းက gap တွေကို အရင်တွက်လိုက်မယ်။ ဥပမာ ပစ္စည်းတခုချင်းစီက budget နဲ့ ဘယ်လောက်ဟနေလဲသိဖို့ တွက်ကြည့်ရင် [5, 4, 2, 1, 2, 5] ဆိုပြီး ရလာမယ်။

ဒီ list ကို length 3 ရှိတဲ့ window နဲ့တိုက်စစ်ကြည့်ရင် sub array [2, 1, 2] က အသေးဆုံး gap ဖြစ်တဲ့အတွက် [4, 7, 8] ပစ္စည်း ၃ ခုက အဖြေဆိုတာ ရလာမယ်။ ဒါပေမယ့် ဒီနည်းက linear scan ၂ ခါလုပ်ဖို့ လိုအပ်တဲ့အတွက် linear time complexity ဖြစ်ပြီး gap တွေတွက်ဖို့လည်း linear space complexity ရှိလိမ့်မယ်။

ပိုကောင်းတဲ့နည်းက binary search သုံးပြီး ဖြေရှင်းတာပါ။ အရင်ဆုံး maximum window size တခု သတ်မှတ်ဖို့ လိုပါတယ်။ ဘာလို့လဲဆိုရင် ဒီနည်းက smallest closest price ကို ရှာပြီး အဲဒီ price ကမှ နောက် price ၂ ခုကို ဆက်တိုက်ယူသွားမှာဖြစ်လို့ နောက်မှာ နေရာလုံလောက်အောင် မချန်ထားရင် index out of bound ဖြစ်သွားပါလိမ့်မယ်။ ဒါကြောင့် window range က smallest possible leftmost closest price နဲ့ biggest possible leftmost closest price ရဲ့ range လို့ဆိုနိုင်တယ်။

window size သတ်မှတ်ပြီးပြီဆိုရင် binary search ကို သုံးမယ်။ window ရဲ့ mid point ကိုထောက်ပြီး သူနဲ့ ကပ်ရက် price 3 ခုရဲ့ ညာဖက်အစွန် (upper bound) နဲ့ ယှဥ်ပါမယ်။ mid နဲ့ budget ကြားက gap က upper bound နဲ့ target ရဲ့ကြားက gap ထက်ကြီးနေတယ်ဆိုရင် mid အပါအဝင် ရှေ့တခြမ်းလုံးကို ပစ်လိုက်လို့ရပါပြီ။

ဘာလို့လဲဆိုတော့ list က price အပေါ် မူတည်ပြီး sort ထားတာဖြစ်လို့ upper bound က mid ထက်စာ budget နဲ့ပိုနီးစပ်နေရင် ကြားထဲက price တွေကလည်း mid ထက်ပိုနီးစပ်နေမှာမို့ပါပဲ။ တကယ်လို့ ဒါနဲ့ပြောင်းပြန် upper bound က mid နဲ့တန်းတူ budget နဲ့နီးစပ်တာ ဒါမှမဟုတ် mid လောက်ကိုမှ မနီးစပ်ဘူးဆိုရင် mid ရဲ့နောက်က price တွေ အကုန်လုံးကို ပစ်လိုက်လို့ရပါတယ်။

ဒီကနေ ရှာသွားရင်းက လက်ရှိ window ရဲ့ lower bound က smallest leftmost closest price ဆီ ရောက်လာလိမ့်မယ်။ အဲဒီကနေ ၃ ခု ဆက်ယူလိုက်ရင် အဖြေရပါပြီ။ ဒီနည်းလမ်းက ပထမပြောတဲ့ပုံစံလို linear scan လုပ်ဖို့ မလိုတဲ့အတွက် logarithmic time complexity ဖြစ်သွားပြီး memory လည်း တသမတ်တည်း ဖြစ်တဲ့အတွက် linear space ဖြစ်ပါတယ်။