Diziler

Programlama Temelleri kursunda listeler kullanıldı: elemanlar eklendi, gezildi, süzüldü. Bu işlemlerin bellekte neye karşılık geldiği ve neden bazılarının diğerlerinden pahalı olduğu açık bırakıldı.

Bu kurs o boşluğu doldurur. Sorusu şudur: veri bellekte nasıl düzenlenirse hangi işlem ucuz, hangisi pahalı olur? Yanıt her seferinde aynı iki kaynaktan gelir — Bilgisayarlar Nasıl Çalışır kursunda kurulan bellek modeli ve yapının kendi düzeni.

Bitişik Yerleşim

Dizi (array), aynı tipteki elemanları bellekte bitişik tutan yapıdır. İlk elemanın adresi biliniyorsa, diğerlerinin adresi hesaplanabilir:

$$\text{adres}(i) = \text{taban} + i \times \text{eleman boyutu}$$

Dört baytlık tam sayılardan oluşan bir dizi 1000 adresinden başlıyorsa, üçüncü elemanın adresi $1000 + 3 \times 4 = 1012$’dir. Hesap tek bir çarpma ve bir toplamadır; dizinin uzunluğundan bağımsızdır.

Bu, dizinin ayırt edici özelliğidir: herhangi bir elemana, sırasını bilerek doğrudan erişilir. Beşinci elemana ulaşmak için önceki dördünün üzerinden geçmek gerekmez.

Yerleşimin ikinci sonucu, dizinin tek tip eleman taşımasıdır. Adres aritmetiği, elemanların eşit boyutta olmasına dayanır; farklı boyutlarda elemanlar bitişik dizilseydi $i$’nci elemanın yeri hesaplanamaz, aranması gerekirdi.

Maliyet Dili

Bu kurs boyunca işlemlerin maliyeti karşılaştırılacaktır. Karşılaştırma için üç ifade yeterlidir; biçimsel tanımları Algoritmalar kursunda verilir.

• Sabit zaman, $O(1)$: İşin süresi veri büyüklüğünden bağımsızdır. Dizinin $i$’nci elemanına erişim böyledir.
• Doğrusal zaman, $O(n)$: Süre, eleman sayısıyla orantılı büyür. Bir diziyi baştan sona taramak böyledir.
• Logaritmik zaman, $O(\log n)$: Her adımda arama alanı sabit bir oranda küçülür. Sıralı bir dizide ikili arama böyledir.

Gösterim, sabit çarpanları ve düşük dereceli terimleri yok sayar; ölçtüğü şey, veri büyüdükçe maliyetin hangi hızla arttığıdır.

Dizinin İşlem Maliyetleri

İşlem	Maliyet	Gerekçe
$i$’nci elemana erişim	$O(1)$	Adres aritmetiği
Sıralı olmayan dizide arama	$O(n)$	En kötü durumda tüm elemanlar
Sıralı dizide arama	$O(\log n)$	Her adımda aralık yarılanır
Sona ekleme (yer varsa)	$O(1)$	Tek yazma
Başa veya ortaya ekleme	$O(n)$	Sonraki elemanların kaydırılması
Ortadan silme	$O(n)$	Boşluğun kapatılması

Ekleme ve silmenin pahalı olması, bitişik yerleşimin doğrudan bedelidir. Beş elemanlı bir dizinin başına eleman eklemek, var olan beş elemanın her birini bir sıra ileri taşımayı gerektirir; yerleşim bitişik kalmalıdır, çünkü adres aritmetiği buna dayanır.

def basa_ekle(dizi: list[int], deger: int) -> int:
    """Diziyi bir sıra kaydırarak başa ekler; kaydırılan eleman sayısını döndürür."""
    dizi.append(None)                      # sona yer aç
    kaydirma = 0
    for i in range(len(dizi) - 1, 0, -1):  # sondan başa doğru kaydır
        dizi[i] = dizi[i - 1]
        kaydirma += 1
    dizi[0] = deger
    return kaydirma


olcumler = [12, 18, 7, 25, 14]
print(basa_ekle(olcumler, 30))     # 5   — beş eleman kaydırıldı
print(olcumler)                    # [30, 12, 18, 7, 25, 14]

Kaydırma sayısı, dizinin uzunluğuna eşittir; bu, tablodaki $O(n)$ satırının sayımla gösterilmiş hâlidir.

Sabit Boyut Kısıtı

Klasik bir dizi, yaratıldığı anda boyutu belirlenen bir bellek bloğudur. Blok bitişik olduğundan, sonradan büyütmek genellikle mümkün değildir: dizinin hemen ardındaki bellek başka bir veri tarafından kullanılıyor olabilir.

Bu kısıtın iki sonucu vardır. Gereğinden büyük ayrılan dizi bellek israfıdır; küçük ayrılan dizi ise dolduğunda kullanılamaz hâle gelir. Programın kaç eleman tutacağı önceden bilinmiyorsa, sabit boyutlu dizi doğrudan çözüm değildir.

Sonraki dersin konusu, tam olarak bu kısıtın nasıl aşıldığıdır.

Dizin Denetimi

Adres aritmetiği, verilen dizinin geçerli olduğunu varsayar. Dizin aralık dışındaysa hesaplanan adres, dizinin dışındaki bir bellek konumunu gösterir.

Diller bu duruma iki farklı yanıt verir. Denetim yapanlar, her erişimde dizini sınır ile karşılaştırır ve aşımda hata üretir; bedeli, erişim başına birkaç komuttur. Denetim yapmayanlar hesabı doğrudan uygular; erişim en hızlı hâlindedir, ancak aralık dışı bir dizin, komşu verinin okunmasına veya üzerine yazılmasına yol açar.

İkinci davranış, Bilgisayarlar Nasıl Çalışır kursunda tanımsız davranış başlığı altında geçmişti. Sonucu yalnızca yanlış değer değildir: dizinin dışına yazmak, çağrı çerçevesindeki dönüş adresini bozabilir. Bu, bellek güvenliği açıklarının en bilinen sınıfıdır ve siber güvenlik müfredatında ayrıca ele alınır.

Çok Boyutlu Diziler

İki boyutlu bir dizi de bellekte tek boyutlu olarak durur; satırlar art arda yerleştirilir. Buna satır öncelikli yerleşim denir ve dizin hesabı şöyle olur:

$$\text{konum}(i, j) = i \times \text{sütun sayısı} + j$$

SUTUN = 4
duz = [0] * (3 * SUTUN)          # 3 satır, 4 sütunluk tablo tek dizide

def yaz(i: int, j: int, deger: int) -> None:
    duz[i * SUTUN + j] = deger

def oku(i: int, j: int) -> int:
    return duz[i * SUTUN + j]

yaz(1, 2, 99)
print(oku(1, 2), duz)            # 99 [0, 0, 0, 0, 0, 0, 99, 0, 0, 0, 0, 0]

99 değerinin düz dizide altıncı konumda ($1 \times 4 + 2$) durması, iki boyutun tek boyuta nasıl indirildiğini gösterir.

Bu yerleşimin başarım sonucu, Bilgisayarlar Nasıl Çalışır kursunun önbellek dersinde hesaplanmıştı: satır boyunca gezinme ardışık adresleri okur, sütun boyunca gezinme her adımda bir satır uzunluğu atlar. Aynı sayıda toplama için taşınan veri miktarı, önbellek satırına sığan eleman sayısı kadar farklıdır.

Diziler Neden Yaygın

Dizinin ekleme ve silme maliyetleri yüksek olmasına karşın, pratikte en sık kullanılan yapı olmasının üç nedeni vardır.

Erişim maliyeti en düşüktür. Sabit zamanlı ve tek bir adres hesabı kadar ucuzdur.

Önbellek davranışı en iyisidir. Bitişik yerleşim, uzamsal yerellikten en çok yararlanan düzendir; bir eleman getirildiğinde komşuları da önbelleğe girer.

Ek yer tutmaz. Bağlantılı yapıların aksine, eleman başına işaretçi saklanmaz.

Bu üç nedenle, “hangi yapı” sorusunun varsayılan yanıtı dizidir; başka bir yapı, ancak dizinin zayıf olduğu bir işlem baskınsa seçilir. Bu kursun geri kalanı, o durumların neler olduğunu ve hangi yapının hangi maliyeti düşürdüğünü gösterir.

Maliyet Tablosu

Kurs boyunca aşağıdaki tablo satır satır büyüyecektir. İlk satır bu dersin sonucudur:

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

* Yer kaldığı sürece; dizi dolduğunda ekleme yapılamaz.

Özet

• Dizi, aynı tipteki elemanları bitişik tutar; $i$’nci elemanın adresi taban adres ve eleman boyutundan hesaplanır.
• Bu hesap dizinin uzunluğundan bağımsız olduğu için erişim sabit zamanlıdır.
• Ekleme ve silme, bitişikliği korumak için eleman kaydırmayı gerektirir ve doğrusal zamanlıdır.
• Sabit boyut kısıtı, bitişik bloğun sonradan büyütülememesinden doğar.
• Çok boyutlu diziler bellekte tek boyutlu durur; satır öncelikli yerleşim, gezinme yönünün önbellek davranışını belirlemesine yol açar.
• Erişim maliyeti, önbellek uyumu ve ek yer tutmaması nedeniyle dizi, varsayılan seçimdir.

Sonraki Adım

Sabit boyut kısıtı, eleman sayısı önceden bilinmeyen problemlerde diziyi kullanılamaz kılıyor. Sonraki ders, diziyi taşımaya dayalı bir çözümle bu kısıtı kaldıracak ve bu çözümün maliyetinin neden göründüğü kadar yüksek olmadığını — amortize maliyet kavramıyla — gösterecek.