Java Nuggets(Data Structures in Action) မြန်မာဘာသာ

Java ရဲ့ ArrayList ဟာ add method နဲ့ ကြိုက်သလောက်ထည့်လို့ရပေမယ့် နောက်ကွယ်မှာတော့ သူ့ကို backed လုပ်ပေးထားတဲ့ elementData ဆိုတဲ့ plain java array တစ်ခုရှိလို့နေပါတယ်။

Dynamic resizing

Dynamic resizing ဆိုတဲ့ feature ကတော့ array capacity full ဖြစ်သွားတဲ့အချိန်မှာ နဂိုcapcity ရဲ့ တဝက်တိတိ ထပ်တိုးပေးတာပါ။ ဥပမာ နဂို capacity က 10 ဆိုရင် 10/2 = 5 ဖြစ်တာကြောင့် elementData ရဲ့ size က 15 ဖြစ်သွားပါတယ်။ ဒါကို 1.5x တိုးတယ်လို့လည်း ခေါ်ပါတယ်။ တခြား data type တွေလို 50% တိုးတာ မဟုတ်ပါဘူး။

Add operation:
Add operation လုပ်ရင် elementData array ရဲ့ နောက်ဆုံးအခန်းလွတ်မှာ သွားထည့်ပါတယ်။ အခန်းလွတ်မကျန်တော့ရင် ရှိတဲ့ Data တွေကို ခုဏကလို array အသစ်ရဲ့ capicity ကို တွက်ပြီး အဟောင်းထဲကနေ အသစ်ထဲ ကူးထည့်ပါတယ်။

Add operation က amortize O(1) ဖြစ်ပါတယ်။
O(1), amortize O(1) နဲ့ O(n) ကို နောင်များမှ ထပ်ရှင်းပါ့မယ်။ အခုတော့ Add Operation က O(1) မဟုတ်ပဲ amortize O(1) ဆိုတာကိုမှတ်ထားပေးပါ။

အမှန်ကတော့ Add Operation ဟာ သူ့ထဲကို data add လုပ်တိုင်း resize မလုပ်ပါဘူး။ ပုံမှန် Add operation က internal array နောက်မှာပဲထည့်တာပါ။ resize လုပ်ပြီဆိုရင်တော့ grow ကိုခေါ်ပါတယ်။

grow က ကျွန်တော် စောစောက ပြောခဲ့သလိုပဲ လုပ်တာပါ။ တချက်ပဲ။ oldCapacity >> 1 ဆိုတဲ့ bitwise operation က oldCapacity/2 လို့အဓိပ္ပါယ်ရပါတယ်။ ပုံမှန် စားတာထက် ပိုမြန်ပါတယ်။

private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }


    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

Get/Set operation:
Get/Set operation တွေဟာ ArrayList ထဲက elementData raw array ကို တိုက်ရိုက်ထောက်ပြီး ယူတာ၊ ပြင်တာ လုပ်တာဖြစ်လို့ သူတို့တွေဟာ Data ပမာဏပေါ်မူတည်ပြီး ပြောင်းလဲခြင်းမရှိပါဘူး။ ဒါကြောင့်မို့ O(1) လို့သတ်မှတ်ကြပါတယ်။

Add operation revisit:
ဘာကြောင့် Add operation က amortize O(1) လည်းဆိုတော့

return elementData = Arrays.copyOf(elementData, newCapacity);

ဟုတ်ပါတယ်။ Array element များရင် များသလောက် copyOf က ကြာပါတယ်။ ဒါကြောင့် copyOf operation က O(n) ပါ။ ဒါပေမယ့် Add Operation လုပ်တိုင်း grow ကို မခေါ်ပါဘူး။ ဒါကြောင့်မို့ O(n) ထက်မြန်တဲ့ O(1) ဒါပေမယ့် Add Operation ဟာ amortize O(1) လို့ သတ်မှတ်ခံရပါတယ်။

Remove operation:
Remove ကြတော့ index ထောက်ထားတဲ့နေရာက element ကို ဖျက်ပြီး သူ့နောက်က data တွေကို ဘယ်ဘက်ကနေ ညာဘက်ကို တွန်းပို့ရတဲ့အတွက် data များရင် များသလို အချိန်ကလိုက်ကြာပါတယ်။ ဒါကြောင့်မို့ သူက add လိုမျိုး amortize O(1) မဟုတ်တော့ပဲ worst case မှာ O(n) ဖြစ်ပါတယ်။