Dynamic Array များနှင့် Amortized Analysis

နားလည်ထားရမယ့် အချက်

raw fixed-size array တစ်ခုဟာ ကြီးထွားလို့မရပါဘူး — array ပြည့်သွားပြီဆိုရင် next memory slot မှာ element အသစ်တစ်ခုအတွက် နေရာမရှိတော့ပါဘူး၊ ဘာလို့လဲဆိုတော့ အဲဒီနေရာမှာ တခြားအရာ ရှိပြီးသားဖြစ်နိုင်လို့ပါ။ Python list ဟာ dynamic array တစ်ခု ဖြစ်တာနှင့် ဒီပြဿနာကို ဖြေရှင်းပါတယ် — internal အနေနှင့် n element အတွက် n slot အတိအကျ allocate မလုပ်ဘဲ၊ capacity extra ကို over-allocate လုပ်ထားတဲ့အတွက် `.append()` call အများစုဟာ reserve ထားပြီးသား slot ထဲကို ရေးထည့်ပြီး length counter ကို တိုးလိုက်ရုံပါပဲ — ဒါက O(1) ဖြစ်ပါတယ်။ reserve ထားတဲ့ capacity ကုန်သွားမှသာ Python က block အသစ်ကြီးတစ်ခု (size ပေါ်မူတည်ပြီး ပုံမှန်အားဖြင့် 1.125x ကနေ 2x လောက် ကြီးလာတာ) ကို allocate လုပ်ပြီး ရှိပြီးသား element အားလုံးကို ထိုထဲ copy ကူးပါတယ်၊ ဒါက call တစ်ခုအတွက် O(n) ကုန်ကျပါတယ်။ resize ဟာ အမြဲတန်း ဖြစ်နေရင် naive array ထက် ဘာမှ ပိုမကောင်းနိုင်ပါဘူး၊ ဒါပေမယ့် resize တစ်ခုစီက capacity ကို နှစ်ဆလောက် ကြီးစေတဲ့အတွက် list ကြီးလာလေ resize ဖြစ်ခြင်းက exponentially ရှားလာလေပါပဲ — total append n ခုမှာ ကုန်ကျစရိတ်များတဲ့ O(n) resize တွေဟာ O(log n) ကြိမ်ပဲ ဖြစ်ပြီး total cost ဟာ O(n) ပဲ ရှိနေဆဲပါ။ append n ခုလုံးအပေါ် ပျမ်းမျှ (သို့) 'amortized' ချိန်ရင်တော့ append တစ်ခုချင်းအတွက် ပျမ်းမျှ O(1) ဖြစ်ပြီး၊ append တစ်ခုချင်းစီဟာ တစ်ခါတစ်ရံ resize ကို trigger လုပ်တဲ့ ကုန်ကျစရိတ်များတဲ့ append ဖြစ်နိုင်ပါတယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform က search index ကို ပြန်တည်ဆောက်တဲ့အခါ — catalog ထဲက lesson တိုင်းအတွက် entry တစ်ခုစီကို တစ်ခါတည်း append လုပ်သွားတဲ့အခါ — amortized O(1) append ဟာ build ကို မြန်နေအောင် ထားပေးတဲ့ အကြောင်းရင်းအတိအကျပါပဲ၊ lesson သောင်းချီရှိနေရင်တောင် Python list ဟာ occasional resize ကို ထိရောက်စွာ ကိုင်တွယ်ပေးတဲ့အတွက် total build time ဟာ lesson count နှင့်အတူ quadratically မဟုတ်ဘဲ linearly ပဲ scale ဖြစ်ပါတယ်။ list တွေဟာ append တိုင်းမှာ resize ဖြစ်ခဲ့ရင်တော့ platform တစ်ခုလုံးကို index လုပ်တာဟာ catalog ကြီးလာလေ ပိုနှေးလာလေ ဖြစ်သွားမှာဖြစ်ပြီး ဒါက ဒီ lesson ရဲ့ mental model က ship မလုပ်ခင် ဖမ်းဖမ်းမိအောင် ကူညီပေးတဲ့ hidden cost အမျိုးအစားပါပဲ။

• Python list ဟာ capacity ကို over-allocate လုပ်ထားတဲ့အတွက် .append() call အများစုသည် reserve ထားသောနေရာထဲ ရေးသွင်းရုံ O(1) ဖြစ်သည်
• Resize (element အားလုံးကို block ကြီးထဲ copy ကူးခြင်း) သည် O(n) ကုန်ကျသော်လည်း append n ခုတွင် O(log n) ကြိမ်သာ ဖြစ်သည်
• Append အားလုံးအပေါ် ပျမ်းမျှချိန်ရင် .append() သည် call တစ်ခုချင်းကွဲပြားနေသော်လည်း 'amortized O(1)' ဖြစ်သည်

အတူတူ စမ်းရေးကြည့်မယ်

import time

# Appending n items to a list -- each individual call is amortized O(1),
# so the total time to build the list grows linearly with n, not quadratically.
n = 200_000
data = []
start = time.perf_counter()
for i in range(n):
    data.append(i)  # usually O(1); occasionally O(n) when the list resizes
elapsed = time.perf_counter() - start

print(f'Appended {n} items in {elapsed:.4f} seconds')
print('List length:', len(data))

item 200,000 ခု append လုပ်ဖို့ ကြာချိန် (second ရဲ့ အစိတ်အပိုင်းငယ်လေး) ကို print ထုတ်ပြီး final length 200000 ဖြစ်ကြောင်း အတည်ပြုပေးသည်၊ occasional O(n) resize တွေက total append time ကို ကြီးမားစွာ မပေါက်ကွဲစေကြောင်း ပြသပါတယ်။

Python Docs — Data Structures — Data Structures & Algorithms