Dinamik Diziler

Önceki ders, dizinin sabit boyutlu bir bitişik blok olduğunu ve bu bloğun sonradan büyütülemediğini kurdu. Eleman sayısı önceden bilinmediğinde bu kısıt bağlayıcıdır.

Çözüm, kısıtı ortadan kaldırmak değil, onunla yaşamaktır: dizi dolduğunda daha büyük yeni bir dizi ayrılır, eski elemanlar oraya kopyalanır ve eski blok bırakılır. Bu yapıya dinamik dizi (dynamic array) denir.

Kapasite ve Uzunluk

Dinamik dizi iki sayı tutar:

• Uzunluk: İçindeki gerçek eleman sayısı.
• Kapasite: Ayrılmış bloğa sığabilecek en fazla eleman sayısı.

Kapasite her zaman uzunluğa eşit veya ondan büyüktür. Aradaki fark, henüz kullanılmayan ama ayrılmış olan yerdir; sona ekleme bu boşluğu kullandığı sürece ucuzdur.

Uzunluk kapasiteye ulaştığında yeniden ayırma gerekir: yeni ve daha büyük bir blok ayrılır, tüm elemanlar kopyalanır. Kopyalama, eleman sayısıyla orantılıdır — yani $O(n)$.

Büyütme Çarpanı

Kritik soru şudur: yeni kapasite ne kadar olmalıdır?

Sabit miktarda büyütme — her seferinde kapasiteye sabit bir sayı eklemek — kötü bir seçimdir. Kapasite birer birer artırılsaydı, $n$ eleman eklemek için yapılan toplam kopyalama şu olurdu:

$$1 + 2 + 3 + \dots + (n-1) = \frac{n(n-1)}{2}$$

Bu, $O(n^2)$ demektir: bin eleman eklemek yaklaşık yarım milyon kopyalama yapar.

Katlayarak büyütme — kapasiteyi her defasında bir çarpanla (yaygın olarak iki ile) çarpmak — toplam maliyeti kökten değiştirir. Kapasite $1$’den başlayıp ikiye katlanıyorsa, $n$ elemana ulaşana kadar yapılan kopyalamaların toplamı:

$$1 + 2 + 4 + \dots + \frac{n}{2} < n$$

Geometrik toplamın kendisi, son terimin iki katından küçüktür. Yani $n$ ekleme için toplam kopyalama sayısı $n$’den azdır; ekleme başına düşen ortalama maliyet sabittir.

Amortize Maliyet

Bu gözlem bir kavramı gerektirir. Tek tek bakıldığında sona ekleme işlemlerinin çoğu $O(1)$, bazıları $O(n)$’dir; en kötü durum maliyeti doğrusaldır.

Ancak pahalı işlemler seyrektir ve her pahalı işlemden sonra kapasite iki katına çıktığı için bir sonraki pahalı işleme kadar iki kat daha fazla ucuz işlem yapılır. Bir işlem dizisinin toplam maliyetini işlem sayısına bölerek elde edilen değere amortize maliyet denir.

Dinamik dizide sona eklemenin amortize maliyeti $O(1)$’dir. Bu, “her ekleme sabit sürer” demek değildir; “$n$ ekleme toplamda $O(n)$ sürer” demektir. Ayrım, gecikmeye duyarlı sistemlerde önem kazanır: tek bir eklemenin uzun sürebileceği bilinmelidir.

class DinamikDizi:
    """Kapasitesini ikiye katlayarak büyüyen dizi."""

    def __init__(self) -> None:
        self._blok: list = [None]      # kapasite 1 ile başlar
        self._uzunluk = 0
        self.kopyalama = 0             # ölçüm için sayaç

    def __len__(self) -> int:
        return self._uzunluk

    def kapasite(self) -> int:
        return len(self._blok)

    def ekle(self, deger: int) -> None:
        if self._uzunluk == self.kapasite():
            self._buyut()
        self._blok[self._uzunluk] = deger
        self._uzunluk += 1

    def _buyut(self) -> None:
        yeni = [None] * (self.kapasite() * 2)
        for i in range(self._uzunluk):        # her eleman yeni bloğa taşınır
            yeni[i] = self._blok[i]
            self.kopyalama += 1
        self._blok = yeni

    def __getitem__(self, i: int) -> int:
        if not 0 <= i < self._uzunluk:
            raise IndexError("dizin aralık dışında")
        return self._blok[i]


dizi = DinamikDizi()
for deger in range(16):
    dizi.ekle(deger)

print(len(dizi), dizi.kapasite())     # 16 16
print(dizi.kopyalama)                 # 15  — toplam kopyalama, eleman sayısından az
print(dizi[3])                        # 3

On altı ekleme için yapılan kopyalama sayısı $1 + 2 + 4 + 8 = 15$’tir. Ekleme başına ortalama bir kopyalamadan az; geometrik toplamın verdiği sınır sayımla doğrulanmıştır.

Bu sayım, amortize çözümlemenin en sade biçimidir: her ekleme kendi maliyetinin yanında ileride yapılacak kopyalama için bir pay biriktirir; yeniden ayırma geldiğinde bu birikmiş paylar maliyeti karşılar.

Çarpanın iki olması zorunlu değildir. Daha küçük bir çarpan (örneğin $1{,}5$) daha az boş yer bırakır ama daha sık kopyalar; daha büyük çarpan tersini yapar. Her iki durumda da amortize maliyet sabit kalır — değişen, sabit çarpanın büyüklüğüdür.

Önceden Ayırma

Eleman sayısı önceden biliniyorsa, büyüme hiç yaşanmayabilir. Çoğu dinamik dizi gerçekleştirimi, kapasiteyi baştan belirlemeye izin veren bir işlem sunar.

Kazanç iki yönlüdür. Yeniden ayırma ve kopyalama tümüyle ortadan kalkar; ve ayrılan blok tek parça olduğu için bellek parçalanması azalır. Bin elemanlık bir sonucun üretileceği biliniyorsa, kapasitenin baştan bin verilmesi on yeniden ayırmayı önler.

sonuc = []
# Kapasite baştan bilinen durumda, dilin sunduğu ön ayırma kullanılır.
# Ön ayırma yoksa, sonucu doğrudan hedef boyutta üretmek aynı işi görür:
hazir = [0] * 1000                      # tek ayırma, kopyalama yok
for i in range(1000):
    hazir[i] = i * 3
print(len(hazir), hazir[999])           # 1000 2997

Bu, erken eniyileme değildir: son boyutun bilindiği durumlarda ön ayırma, kodun okunabilirliğini de artırır — niyet açıkça yazılmış olur.

Küçülme ve Salınım

Elemanlar silindiğinde kapasitenin de düşürülmesi beklenir; aksi hâlde bir kez büyüyen dizi belleği bırakmaz.

Küçültme eşiği dikkatle seçilmelidir. Kapasite, uzunluk kapasitenin yarısına indiğinde yarıya düşürülürse salınım oluşur: dizi tam sınırdayken art arda yapılan bir ekleme ve bir silme, her seferinde yeniden ayırma tetikler. Her işlem $O(n)$ olur ve amortize kazanç yok olur.

Standart çözüm, eşikleri ayırmaktır: kapasite dolduğunda ikiye katlanır, ancak yalnızca uzunluk kapasitenin dörtte birine indiğinde yarıya düşürülür. Aradaki boşluk, sınırda gidip gelen işlemlerin yeniden ayırma tetiklemesini engeller.

Gerçek Dillerdeki Karşılığı

Çoğu dilin standart “liste” veya “vektör” yapısı, bir dinamik dizidir. Sona ekleme amortize sabit, başa ekleme doğrusaldır; bu asimetri, kod yazarken hangi ucun kullanılacağını belirler.

Bir ayrıntı, elemanların ne saklandığıdır. Sabit genişlikli tipler doğrudan blokta tutulabilir; nesne referansları saklandığında ise blok işaretçiler taşır ve gerçek değerler öbekte dağınık durur. İkinci düzen esneklik verir, önbellek uyumunu düşürür. Bilgisayarlar Nasıl Çalışır kursundaki bitişik yerleşim tartışması bu ayrımı içeriyordu.

Maliyet Tablosu

Yapı	Erişim	Arama	Başa ekleme	Sona ekleme	Ortadan silme
Dizi (sabit boyut)	$O(1)$	$O(n)$	$O(n)$	$O(1)$*	$O(n)$
Dinamik dizi	$O(1)$	$O(n)$	$O(n)$	$O(1)$ amortize	$O(n)$

* Yer kaldığı sürece.

Özet

• Dinamik dizi, dolduğunda daha büyük bir blok ayırıp elemanları kopyalayarak sabit boyut kısıtını aşar.
• Kapasite ayrılmış yeri, uzunluk gerçek eleman sayısını gösterir.
• Sabit miktarda büyütme toplam maliyeti $O(n^2)$ yapar; katlayarak büyütmede toplam kopyalama $n$’den azdır.
• Amortize maliyet, bir işlem dizisinin toplam maliyetinin işlem sayısına bölünmesidir; sona eklemenin amortize maliyeti sabittir, tek bir eklemeninki değildir.
• Küçültme eşiği büyütme eşiğinden ayrı seçilir; aksi hâlde sınırdaki işlemler salınım üretir.

Sonraki Adım

Dinamik dizi, sona eklemeyi ucuzlattı ama başa ve ortaya ekleme hâlâ doğrusal. Kaydırma maliyetinin kaynağı bitişik yerleşimdi. Sonraki ders, bitişikliği tümüyle terk eden bir yapıyı — bağlı listeyi — ve bu değiş tokuşun neyi kazanıp neyi kaybettirdiğini ele alacak.