String များနှင့် String Algorithm များ

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

Python string တွေဟာ immutable ဖြစ်ပါတယ် — တစ်ခါ create လုပ်ပြီးရင် string object ရဲ့ character တွေကို in place မှာ ဘယ်တော့မှ ပြောင်းလို့မရပါဘူး။ ဒါကြောင့် string တစ်ခုပေါ်မှာ `+=` လုပ်တိုင်း ရှိပြီးသား object ကို extend လုပ်တာ မဟုတ်ဘဲ — combined result အတွက် လုံလောက်တဲ့ string အသစ်တစ်ခုလုံးကို allocate လုပ်ပြီး ရှေးက content နှင့် addition နှစ်ခုလုံးကို အထဲကို copy ကူးလိုက်တာပါ။ တစ်ကြိမ်ပဲဆိုရင် ဘေးမဲ့ပါတယ်၊ ဒါပေမယ့် loop ထဲမှာဆို ဆိုးဆိုးရွားရွား ပေါင်းစပ်သွားပါတယ် — iteration k မှာ accumulated string ဟာ length k လောက် ရှိပြီးဖြစ်တဲ့အတွက် `+=` တစ်ခုစီဟာ character k ခန့် copy ကူးရမှာဖြစ်ပြီး၊ iteration n ခုလုံး (1 + 2 + 3 + ... + n) ရဲ့ copy ကုန်ကျစရိတ်ကို ပေါင်းလိုက်ရင် character copy n²/2 ခန့် စုစုပေါင်း ဖြစ်သွားပါတယ် — innocent O(n) loop လိုမြင်ရပေမယ့် O(n²) ဖြစ်သွားပါတယ်။ ဖြေရှင်းနည်းကတော့ string ကို incremental အနေနှင့် ဘယ်တော့မှ မ accumulate ရပါဘူး။ အစား list တစ်ခုထဲမှာ piece တွေကို စုသိမ်းပြီး — list ထဲ append လုပ်တာက ယခင်ကလေ့လာခဲ့သလို amortized O(1) ပါ — အဆုံးမှာ "".join(pieces) ကို တစ်ကြိမ်ပဲ call လုပ်ပါ။ join က list ကို တစ်ကြိမ် scan လုပ်ပြီး total length ကို ကြိုသိထားတဲ့အတွက် correct size ရှိတဲ့ final string တစ်ခုတည်းကိုပဲ allocate လုပ်ပြီး piece တစ်ခုချင်းစီကို တစ်ကြိမ်တည်းပဲ copy ကူးပါတယ်၊ ဒါက true O(n) total cost ဖြစ်ပါတယ်။ mental rule ကတော့ — list နှင့်ဆောက်ပါ၊ တစ်ကြိမ်တည်း join လုပ်ပါ။

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

Tutorial Platform က lesson page တစ်ခုကို render လုပ်တဲ့အခါ title, code block တစ်ခုချင်းစီ, paragraph တစ်ခုချင်းစီ, exercise, pitfalls list — piece အများကြီးကနေ HTML string တစ်ခုကို ပေါင်းစပ်နေတာပါ။ ဒီ assembly ကို fragment ရာချီပါတဲ့ lesson တစ်ခုအတွက် string += ထပ်ခါထပ်ခါ လုပ်ရင် တိတ်တဆိတ် O(n²) ဖြစ်သွားပြီး lesson ရှည်လာလေ page generation နှေးလာလေ ဖြစ်သွားပါလိမ့်မယ်၊ fragment တစ်ခုချင်းစီကို list ထဲ အရင်စုသိမ်းပြီး "".join() ကို တစ်ကြိမ်တည်း call လုပ်ခြင်းက lesson မှာ fragment ဘယ်နှစ်ခုပဲရှိရှိ rendering ကို O(n) ဖြစ်နေအောင် ထိန်းသိမ်းပေးပါတယ်၊ ဒါက real template engine တွေက အောက်ခြေမှာ သုံးနေတဲ့ pattern အတိအကျပါပဲ။

• Python string များသည် immutable ဖြစ်သည် — += တိုင်းက string အသစ်တစ်ခု ဖန်တီးပြီး operand နှစ်ခုလုံးကို copy ကူးသည်
• Loop ထဲတွင် += ကို ထပ်ခါထပ်ခါ concatenate လုပ်ခြင်းသည် iteration တိုင်းက accumulated text ပိုများသော ပမာဏကို copy ကူးရသောကြောင့် စုစုပေါင်း O(n²) ဖြစ်သည်
• Piece များကို list ထဲစုသိမ်းပြီး "".join() ကို တစ်ကြိမ်တည်း call လုပ်ခြင်းသည် မှန်ကန်သော O(n) pattern ဖြစ်သည်

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

words = ['Data', 'Structures', 'and', 'Algorithms', 'are', 'fun']

# Slow pattern: repeated += creates a new string and copies everything each time -> O(n^2)
result_slow = ''
for word in words:
    result_slow += word + ' '

# Fast pattern: collect pieces, join once -> O(n) total
result_fast = ' '.join(words)

print('Slow result:', result_slow.strip())
print('Fast result:', result_fast)
print('Equal content:', result_slow.strip() == result_fast)

slow နည်းနှင့် fast နည်းနှစ်မျိုးဖြင့် ဆောက်ထားသော sentence ('Data Structures and Algorithms are fun') တူညီသည်ကို print ထုတ်ပြီး confirm ပြုသည်၊ word အရေအတွက်များလာလေ += version က အောက်ခြေမှာ copy ပိုများစွာ လုပ်နေသော်လည်းပါ။

Python Docs — Text Sequence Type str — Data Structures & Algorithms