3 Veri Yapıları ve Dinamik Diziler

Arayüz vs veri yapısı, statik dizi / bağlı liste / dinamik dizi, geometrik seri ve amortize analiz

Bölüm bilgisi

Demaine’in videosu: YouTube — Lecture 2: Data Structures and Dynamic Arrays (≈50 dk)
OCW sayfası: MIT 6.006 Lecture 2: Data Structures and Dynamic Arrays
Seri: MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 2
Hocalar: Erik Demaine (Jason Ku, Justin Solomon)
Okuma süresi: ≈24 dk

3.1 Bu Derste Ne Var?

Ders 1 problem ile algoritma arasındaki farkı kurdu. Bu ders, aynı ayrımı veri tarafında yapar: arayüz (interface) ile veri yapısı (data structure) arasındaki fark. Erik Demaine, dersin ilk veri yapıları bölümüne enerjik bir girişle başlar.

Üç temel kavram bu derste yan yana gelir:

Arayüz vs veri yapısı — arayüz ne yapılacağını (desteklenen işlemler), veri yapısı nasıl yapılacağını (gerçekleştirim) söyler.
Dizi (sequence) arayüzü — $n$ öğeyi sıralı tutma; statik dizi, bağlı liste ve dinamik dizi ile çözülür.
Amortize analiz — dinamik dizinin (Python list) neden sona eklemede amortize $O(1)$ olduğunun ispatı.

“an interface says what you want to do. A data structure says how you do it.” — Demaine, 1:18

flowchart TD
    A["Ders 2: Veri Yapıları ve Dinamik Diziler"] --> B["Arayüz (ne)"]
    A --> C["Veri Yapısı (nasıl)"]
    C --> D["Dizi (sequence) arayüzü"]
    D --> E["Statik Dizi<br/>rastgele erişim O(1)<br/>insert/delete Θ(n)"]
    D --> F["Bağlı Liste<br/>uç işlemi O(1)<br/>erişim O(i)"]
    D --> G["Dinamik Dizi<br/>ikisinin en iyisi<br/>insert_last amortize O(1)"]
    G --> H["İkiye-katlama + geometrik seri"]
    H --> I["Amortize analiz<br/>nadiren pahalı, çoğu ucuz"]

    classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
    classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
    classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
    class A root
    class B,C,D branch
    class E,F,G,H,I leaf

Şekil 3.1: Ders 2’nin kavram haritası: arayüz (ne) ile veri yapısı (nasıl) ayrımından, dizi arayüzünü çözen üç gerçekleştirime — statik dizi (rastgele erişim O(1)), bağlı liste (uç işlemi O(1)), dinamik dizi (ikisinin en iyisi).

Builder Notu — Arayüz/Implementasyon Ayrımı ve PyTorch

Demaine’in arayüz/veri yapısı ayrımı, modern ML kütüphanelerinin temel tasarım desenidir — aynı sözleşme (interface), değişebilir gerçekleştirim (implementation):

İleriye → PyTorch nn.Module: Bir katmanın forward() arayüzü ne hesaplanacağını söyler; arkadaki tensör depolaması, bellek düzeni ve çekirdek (kernel) seçimi nasıl yapılacağını. Aynı nn.Linear API’si CPU, CUDA veya MPS backend’iyle çalışır — arayüz sabit, veri yapısı değişir.
Geriye → Python (Phase 1): Demaine açıkça söyler, bu giriş dersleri “Python’ın nasıl gerçekleştirildiğini” anlatır. Python list = dinamik dizi; bu ders onun iç mekanizmasını açar.
Geriye → word RAM (Ders 1): statik dizinin $O(1)$ erişimi doğrudan Ders 1’in word RAM modeline dayanır (ardışık bellek + rastgele erişim).

Tek cümle: Aynı arayüzü farklı veri yapıları çözer; doğru seçim, hangi işlemin ne sıklıkta çağrıldığına bağlıdır.

3.2 Arayüz mü, Veri Yapısı mı?

Demaine, bir programcının API, eski kuşak bir algoritmacının ADT (abstract data type) dediği şeyi arayüz olarak adlandırır. Ayrım nettir:

Arayüz = ne: hangi veriyi saklayabilirsin, hangi işlemleri destekler, bu işlemler ne anlama gelir. Bu bir spesifikasyondur (problem ifadesinin veri karşılığı).
Veri yapısı = nasıl: verinin somut gösterimi ve işlemleri destekleyen algoritmalar. Algoritmalar tam da burada devreye girer.

“The same problem can be solved by many different data structures.” — Demaine, 3:23

Veriyi sadece saklamak sıkıcıdır (bir dosyaya atarsın). İşi ilginç kılan, o veri üzerindeki işlemlerdir — ve farklı veri yapıları bazı işlemleri diğerlerinden hızlı destekler. Doğru veri yapısı, ne için kullanacağına bağlıdır.

3.3 İki Temel Arayüz: Küme ve Dizi

6.006 iki ana arayüze odaklanır:

Küme (set): öğeleri değerlerine (anahtar/key) göre tutar — sıralı tutma, bir değeri arama. “Set” bir matematikçi için başka, bir Python programcısı için başka şey ifade eder.
Dizi (sequence): öğeleri belirli bir sırada tutar — örneğin 5, 2, 9, 7 sayılarını bu sırayla. Python’da bunu bir list ile saklarsın; sırayı korur.

Bu ders dizi arayüzüne odaklanır (küme arayüzüne sonda değinilir, Ders 3-4’te derinleşir). İki temel araç vardır: diziler (arrays) ve işaretçiler (pointers / bağlı yapılar). Bugün ikisini de göreceğiz.

3.4 Statik Dizi Arayüzü

En basit dizi arayüzü statik dizidir: öğe sayısı $n$ değişmez (ama öğelerin kendisi değişebilir). Öğeler $x_0, x_1, \ldots, x_{n-1}$ olarak etiketlenir (Python’daki gibi 0’dan başlar). Desteklenen işlemler:

build(x): verilen öğelerden $n$ boyutlu yeni bir dizi kur.
length(): sabit $n$ değerini döndür.
iter(): öğeleri $x_0$’dan $x_{n-1}$’e sırayla üret (en az lineer zaman).
get_at(i): $i$’inci öğeyi ($x_i$) döndür.
set_at(i, x): $i$’inci öğeyi yeni bir değerle değiştir.

build ve iter doğası gereği tüm öğelere dokunur → $\Theta(n)$. Asıl ilginç olan, dizinin ortasına dinamik erişim: get_at ve set_at.

3.5 Statik Dizi (Static Array)

Bu arayüzün doğal çözümü statik dizidir (Python’da list denir; Demaine “array” demeyi tercih eder). Python’da aslında statik dizi yoktur — yalnızca dinamik diziler vardır — ama kavramı anlamak gerekir.

Statik dizi, belleğin ardışık (consecutive) bir parçasıdır. Ders 1’in word RAM modeline dayanır: bellek, $w$-bitlik word’lerden oluşan bir dizidir ve herhangi bir word’e sabit zamanda rastgele erişilebilir. Bir diziye $i$ indeksinden erişmek, basit bir ofset aritmetiğidir (Şekil 3.2): dizinin başlangıç adresi (Python’da id(array)) artı $i$.

“as long as I store my array consecutively in memory, I can access the array in constant time.” — Demaine, 11:26

Bu yüzden statik dizi, get_at ve set_at işlemlerini $O(1)$ zamanda çözer. length de $O(1)$’dir ($n$’i adresle birlikte saklarız). build ve iter $\Theta(n)$’dir. Bu çalışma süreleri optimaldir — basit ama bu modele giderek daha çok ihtiyaç duyacağız.

Şekil 3.2: Statik dizi: öğeler $x_0 \ldots x_4$ **ardışık bellekte** yan yana durur. i’inci öğenin adresi basit bir **ofset aritmetiğiyle** bulunur: `base + i`. Bu yüzden `get_at(i)` herhangi bir indekse tek hamlede ulaşır — **$O(1)$ rastgele erişim** (amber vurgulu $x_2$). Bu, Ders 1’in word-RAM modeline dayanır: bir adres tek word’e sığar ve bellek hücresine sabit zamanda erişilir. Bedeli, dizinin boyutunun sabit olmasıdır.

3.6 Bellek Ayırma Modeli ve Word Boyutu

build’in nasıl çalıştığını tanımlamak için bellek ayırma modeli gerekir. En temiz varsayım: $n$ boyutlu bir diziyi $\Theta(n)$ zamanda ayırabiliriz.

“the cleanest one is just to assume that you can allocate an array of size n in theta n time.” — Demaine, 13:09

Neden sabit değil de lineer? Çünkü ayrılan bellek başlangıçta belirsizdir; onu 0’larla başlatmak lineer maliyet ister. Bu modelin güzel bir yan etkisi: kullandığın yer (space), kullandığın zamandan (time) fazla olamaz. Sonsuz boyutlu bir dizi ayırıp birkaç öğe kullanmak gerçekçi değildir — bellek ayırmanın bir bedeli olmalıdır.

Word boyutu ($w \geq \log n$): Dizi erişiminin sabit zaman olması için, word boyutu $w$ en az $\log n$ kadar olmalıdır. Sebep: $n$ öğeyle çalışıyorsak, en azından onları adresleyebilmeliyiz — “$i$’inciyi ver” diyebilmek için $i$ sayısını bir word’e sığdırmalıyız. Bu yüzden $w \geq \log n$.

“the word size has to grow with n… at least as fast as log n.” — Demaine, 15:13

Bu, gerçek makineler (sabit boyut) ile teori (ölçeklenebilirlik) arasında köprü kurar: gerçekte daha büyük girdi için daha çok RAM alırsın; teoride de $w$, $n$ ile birlikte asimptotik olarak büyür.

3.7 Dinamik Dizi Arayüzü

Statik arayüze iki dinamik işlem ekleriz: dizinin ortasına insert_at ve ortasından delete_at. insert_at, set_at’ten farklıdır: hiçbir bilgiyi silmez; eklenen konumdan sonraki tüm öğeler indekslerini bir kaydırır ($n' = n+1$).

İndeksleme inceliği önemlidir: insert_at(2, x)’ten sonra get_at(2) yeni öğeyi, get_at(3) eski $x_2$’yi döndürür. Bu izlemesi zordur ama uçlarda (baş/son) ekleme/silme yaparken çok kullanışlıdır. Bu yüzden özel durumları tanımlarız: insert/delete first ve last, get/set first ve last.

“insert_last doesn’t change the indices of any of the old items.” — Demaine, 19:59

Kritik gözlem: insert_last eski öğelerin indekslerini değiştirmez (güzel özellik); insert_first hepsini $+1$ kaydırır. Tüm dinamik dizi arayüzünü sabit zamanda çözmek imkânsızdır (ispatlanabilir), ama özel durumları — yalnızca uçlardan ekleme/silme — verimli çözebiliriz. İşte bu yüzden özel durumlar ilginçtir.

3.8 Bağlı Liste (Linked List)

Dinamik diziyi çözen ilk veri yapısı bağlı listedir. Öğeleri düğümlerde (node) saklarız; her düğümde bir item alanı ve bir next (sonraki) işaretçisi vardır — iki sınıf değişkenli bir nesne gibi. Düğümler next işaretçileriyle birbirine bağlanır; sıra, bu işaretçilerle örtük olarak temsil edilir (Şekil 3.3). Veri yapısı bir head (baş) işaretçisiyle temsil edilir.

Bu, işaretçi tabanlı bir veri yapısıdır (statik dizi ise dizi tabanlıydı). İşaretçiler tek bir word’e sığar, bu yüzden word RAM modelinde sabit zamanda dereference edilebilir (işaret edilen düğüme bakılabilir). Düğümler bellekte rastgele sırada durur — işaretçiler aslında dev bellek dizisindeki indekslerdir.

“linked list, insert- and delete_first are constant time.” — Demaine, 30:41

Bağlı listenin uçlarda dinamik olması güçlüdür: yeni bir baş öğe eklemek (insert_first) sabit zamandır — yeni düğüm ayır, next’ini eski başa bağla, head’i güncelle. Ancak rastgele erişim zayıftır: $i$’inci öğeye ulaşmak için $i$ kez next takip etmek gerekir → get_at/set_at $O(i)$, en kötü durumda $\Theta(n)$. Statik dizinin tam tersi: dizi rastgele erişimde iyi, bağlı liste uçlarda dinamiklikte iyidir.

Şekil 3.3: Bağlı liste: her düğüm bir **(item | next)** kutusudur; sıra yalnız `next` işaretçileriyle örtük tutulur (bellekte düğümler dağınık olabilir). `head` ilk, `tail` son düğüme işaret eder ($\S 8$ augmentation) → **insert_first** ve **insert_last** $O(1)$. Rastgele erişim zayıftır: `get_at(2)` head’den `next` zincirini $i$ kez takip eder — burada $3$ düğüm ziyareti (amber zincir) → $O(i)$. Son düğümün `next`’i $\varnothing$ (None).

3.9 Veri Yapısı Zenginleştirme (Augmentation)

Küçük bir bulmaca: bağlı listede get_last’ı sabit zamanda nasıl çözeriz? Cevap: son öğeye bir işaretçi sakla (genelde tail denir). Bu, veri yapısı zenginleştirmedir (augmentation): yapıya ekstra bilgi ekleyip onu her zaman güncel tutmak.

“data structure augmentation, where we add some extra information to the data structure” — Demaine, 33:09

tail işaretçisiyle get_last ve insert_last $O(1)$ olur. delete_last ise daha zordur — onun için çift bağlı liste (doubly linked list, her düğümde bir de prev işaretçisi) gerekir. Zenginleştirmenin bedeli: yapıyı değiştiren her işlemde ekstra bilgiyi (örneğin tail) güncel tutmak zorundasın.

Builder Notu — Augmentation ve Veritabanı İndeksleri

Augmentation — “yapıya ekstra bilgi ekle, onu güncel tut, bir sorguyu hızlandır” — sistem mühendisliğinin en yaygın takasıdır:

İleriye → veritabanı indeksleri: Bir tabloya B-ağacı veya hash indeksi eklemek tam olarak augmentation’dır: aramayı $O(n)$ tam-taramadan $O(\log n)$’e (veya $O(1)$’e) indirir. Bedeli, tail’i güncel tutmak gibi — her INSERT/UPDATE/DELETE indeksi de güncellemek zorundadır (yazma daha pahalı, okuma çok daha ucuz).
Sezgi → skip-list / B-tree: tail ve prev işaretçileri, daha zengin augmentation’ların (skip-list’in atlama katmanları, B-ağacının iç düğüm anahtarları) ilk basamağıdır; hepsi “ekstra yapısal bilgi sakla, navigasyonu hızlandır” fikrinin türevidir.
İleriye → ML feature store: Önceden hesaplanmış (materialized) öznitelik tabloları, çıkarım anında yeniden hesaplamayı önlemek için tutulan augmentation’lardır — güncel tutma maliyeti (cache invalidation), tail güncellemesiyle aynı disiplini ister.

3.10 Statik Dizi mi, Bağlı Liste mi?

İki veri yapısı birbirini tamamlar:

Statik dizi: get_at/set_at sabit zaman $O(1)$ (rastgele erişimde mükemmel), ama insert/delete her yerde $\Theta(n)$ (kaydırma veya yeniden ayırma + kopyalama gerekir). Sona ekleme bile zordur, çünkü ayrılan dizi büyütülemez — yeni bir dizi ayırıp her şeyi kopyalamak $\Theta(n)$’dir.
Bağlı liste: insert/delete_first sabit zaman $O(1)$ (uçlarda dinamiklikte iyi), ama get_at/set_at $O(i)$, en kötü $\Theta(n)$ (rastgele erişimde kötü).

Demaine’in deyişiyle: diziler statik rastgele erişim için, bağlı listeler dinamik uç işlemleri için iyidir. Hiçbiri her ikisini birden iyi yapmaz. Hedefimiz, ikisinin de güçlü yanlarını birleştiren bir yapı. Bu tercihin gerçek donanımdaki bir başka boyutu da bellek yerelliğidir (Şekil 3.4): aynı asimptotik tarama, ardışık dizide bağlı listeden çok daha hızlı koşar.

Şekil 3.4: Dizilerin taramada bağlı listeyi yenmesinin donanım sebebi: **bellek yerelliği**. Üstte statik dizi tek **ardışık blok** — öğeler bitişik adreslerde, bir önbellek satırı ($O(1)$ erişim, amber); sıralı tarama tek atlamayla ilerler, yüksek yerellik. Altta bağlı liste düğümleri bellekte **dağınık**; her `next` işaretçisi uzak bir adrese sıçrar (amber oklar), her erişim önbellek-ıskası (cache-miss) riski taşır. Aynı asimptotik $\Theta(n)$ tarama, gerçek donanımda dizide çok daha hızlıdır — düşük yerellik bağlı listeyi cezalandırır.

3.11 Dinamik Dizi (Dynamic Array)

Çözüm dinamik dizidir — ve bu tam olarak Python’ın list dediği şeydir.

“another way to describe what these introductory lectures are about is telling you about how Python is implemented.” — Demaine, 34:19

Fikir, statik dizinin katı kuralını gevşetmektir: ayrılan dizinin boyutu tam $n$ olmak zorunda değil; kabaca $n$ olsun. Algoritma dilinde “kabaca” = sabit çarpanları at. Diziyi boyutu $\Theta(n)$ ve $n$’den büyük-eşit tutarız (örneğin $2n$).

“the size of the array is theta n– probably also greater than or equal to n.” — Demaine, 36:11

Yapı, bir dizi artı bir length (gerçek öğe sayısı) tutar. length, dizinin gerçek boyutu size’dan küçük-eşittir; ilk length konum veriyi, kalanı boş yeri temsil eder. insert_last basittir: a[length] = x, sonra length’i artır → $O(1)$. Ama bir sorun var: length = size olduğunda boş yer kalmaz. İşte o zaman diziyi büyütmek gerekir — sonraki bölümün konusu.

3.12 Dizi Büyütme ve Geometrik Seri

length = size olduğunda diziyi büyütmek gerekir. Ne kadar? İki doğal seçenek:

Sabit ekleme (size + 5): Kötü. Her 5 adımda bir lineer yeniden ayırma → işlem başına hâlâ lineer zaman. Statik dizinin “her seferinde yeniden ayır” sorununu sadece sabit çarpanla iyileştirir.
Sabit çarpan (2 × size): İyi. Diziyi her dolduğunda iki katına çıkar.

Çalışılan Örnek — Doubling’in Toplam Maliyeti

Boş bir diziden başlayıp $n$ kez insert_last yapalım (size = 1 başlasın). Yeniden boyutlandırmalar $n = 1, 2, 4, 8, 16, \ldots$ değerlerinde, yani 2’nin kuvvetlerinde olur (çünkü ikiye katlıyoruz; Şekil 3.5). Her resize, ayırma + kopyalama nedeniyle lineerdir. Toplam resize maliyeti:

\[1 + 2 + 4 + 8 + \cdots + (\approx n) = \sum_i 2^i \quad (i = 0 \text{'dan} \approx \log_2 n \text{'e})\]

Bu bir geometrik seridir. Kimliği: $1 + 2 + 4 + \cdots + 2^k = 2^{k+1} - 1$. Geometrik seriler son terim tarafından domine edilir:

“Geometric series are dominated by the last term” — Demaine, 45:46

Son terim $2^{\log_2 n} = n$ olduğundan, toplam $\Theta(n)$’dir. Yani $n$ işlem için toplam yeniden boyutlandırma maliyeti yalnızca $\Theta(n)$ — işlem başına “kabaca sabit”.

Şekil 3.5: Dinamik dizi büyütme (doubling): dizi dolarken ayrılan boyut **1 → 2 → 4 → 8** olarak ikiye katlanır. Her satır o anki diziyi gösterir — dolu amber hücreler **length** (gerçek öğe sayısı), boş slate hücreler **size − length** (ayrılan ama henüz kullanılmayan yer). Soldaki amber oklar her resize’da **ayır + kopyala** adımını gösterir: `length == size` olunca yeni (iki kat) dizi ayrılır ve eski öğeler taşınır ($\Theta(\text{length})$). Toplam ayrılan + kopyalanan iş bir geometrik seridir: $1 + 2 + 4 + 8 = 15 = 2^{4} - 1$ — son terim toplamı domine eder, bu yüzden $n$ append toplam $\Theta(n)$’dir ve `insert_last` amortize $O(1)$ olur.

Builder Notu — İkiye-Katlama Her Yerde

Demaine’in “dolunca iki katına çık” stratejisi, tek bir veri yapısının özelliği değil — ölçeklenen sistemlerin tekrar eden bir motifidir:

İleriye → PyTorch DataLoader ve torch.cat: Boyutu önceden bilinmeyen bir tampona (buffer) tensör biriktirirken, kapasitenin geometrik büyütülmesi (her torch.cat realloc’unda sabit çarpan) toplam kopya işini $\Theta(n)$’de tutar; sabit ekleme olsa $\Theta(n^2)$’ye patlardı.
İleriye → exponential backoff: Başarısız bir isteği yeniden denerken bekleme süresini ikiye katlamak (1s, 2s, 4s, 8s), aynı geometrik seri sezgisidir — toplam bekleme son terimle domine olur, sistem yükü sınırlı kalır.
İleriye → batch-size / LR taraması: Hiperparametre ararken batch boyutunu veya öğrenme oranını ikiye katlayarak (32, 64, 128, …) geometrik bir ızgara taramak, lineer ızgaraya göre çok daha geniş bir aralığı logaritmik sayıda denemeyle kapsar — “son terim toplamı domine eder” disiplini.

3.13 Amortize Analiz (Amortized Analysis)

Bu “kabaca sabit” kavramı amortizasyondur. Tanım: bir işlem $T(n)$ amortize zaman alır, eğer herhangi $k$ işlem en fazla $k \cdot T(n)$ toplam zaman alıyorsa.

“Amortized means a particular kind of averaging– averaging over the sequence of operations.” — Demaine, 47:42

Doubling’de $n$ işlem toplam $\Theta(n)$ zaman aldığından, insert_last sabit amortize (constant amortized) zamandır. Sezgi: tek tek işlemler bazen pahalıdır (resize anında lineer), ama çoğu ucuzdur (sabit). Pahalı işlemin maliyetini, onu mümkün kılan tüm ucuz işlemlere “dağıtırız” — bu, işlem dizisi üzerinde ortalamadır (Şekil 3.6). delete_last için resize gerekmez (length’i azalt, biter), o da sabit amortizedir.

Şekil 3.6: Amortize analiz (İMZA): bir dinamik diziye boş başlangıçtan $n=31$ kez `append`. **Sol:** her işlemin maliyeti — çoğu yalnız 1 (tek slot yazımı, slate çubuklar); `length == size` olduğunda ikiye-katlama tetiklenir ve o işlemin maliyeti o anki boyut kadar sıçrar (amber çubuklar, append #1, 2, 3, 5, 9, 17’de değerler $1, 2, 3, 5, 9, 17$ — yani o anki boyutu kopyalama + 1 slot yazımı; resize boyutları $1, 2, 4, 8, 16$ ($2^k$) olduğundan ilk hariç maliyet $2^k+1$’e sıçrar). **Sağ:** kümülatif ortalama (toplam maliyet / işlem sayısı, slate çizgi) her resize’da yukarı sıçrayıp ardından düşer ve sabit bir değere — tam olarak $62/31 = 2{,}00$ (amber kesik çizgi) — düzleşir. Nadiren pahalı resize’ların maliyeti tüm adımlara yayıldığı için `insert_last` **amortize $O(1)$**’dir; geometrik seri toplamı $\sum_{i} 2^i = 2^{k+1}-1 \approx 2n$ bu sabiti garanti eder.

Builder Notu — Amortize Düşünme ve Mini-batch/Checkpoint

“Nadiren pahalı, çoğu zaman ucuz; maliyeti diziye yay” analizi, eğitim ve altyapı kodunun her yerinde aynı biçimde karşına çıkar:

İleriye → checkpoint kaydetme: Bir modeli her $N$ adımda bir diske yazmak pahalıdır (tüm ağırlıkları serialize et), ama bu maliyet aradaki $N$ ucuz eğitim adımına yayıldığında adım başına amortize maliyet ihmal edilebilir kalır — tam olarak resize’ın append’lere yayılması gibi.
İleriye → gradient accumulation: Birkaç mini-batch’in gradyanını biriktirip seyrek aralıklarla bir optimizer adımı atmak, pahalı step() çağrısının maliyetini birikim adımlarına amortize eder.
İleriye → rehash ve GC: Hash tablosu yük faktörü eşiği aşınca yeniden hash’leme ($\Theta(n)$) ve çöp toplama (garbage collection) duraklamaları, doubling resize’la birebir aynı amortize argümanına dayanır: nadir, pahalı, ama dizi boyunca sabit ortalama.

3.14 Üç Veri Yapısı — Karşılaştırma

Demaine dersi bu özet tabloyla kapatır ($\Theta$’lar atılmış, çalışma süreleri; Şekil 3.7):

İşlem	Statik Dizi	Bağlı Liste	Dinamik Dizi
get_at / set_at	$O(1)$	$O(n)$	$O(1)$
insert / delete_first	$O(n)$	$O(1)$	$O(n)$
insert / delete_last	$O(n)$	$O(n)$	$O(1)$ amortize
insert / delete_at	$O(n)$	$O(n)$	$O(n)$

Dinamik dizi, rastgele erişimde statik dizinin hızını ($O(1)$ get_at) ve sona eklemede neredeyse bağlı listenin esnekliğini ($O(1)$ amortize insert_last) birleştirir — ikisinin en iyisi.

Şekil 3.7: Demaine’in kapanış maliyet matrisi: 4 işlem ailesi × 3 veri yapısı. Yeşilimsi hücreler $O(1)$ (en iyi, sabit zaman), amber hücreler $O(n)$ (yavaş, lineer), amber-çerçeveli açık hücre ise $O(1)$ amortize (neredeyse en iyi). Hiçbir sütun her satırda kazanmaz: **statik dizi** rastgele erişimde ($O(1)$ get_at/set_at) üstündür ama her ekleme/silme $O(n)$ kaydırma ister; **bağlı liste** uç işlemlerini ($O(1)$ insert/delete_first ve tail augmentation’la last) hızlandırır ama rastgele erişim $O(n)$’e düşer; **dinamik dizi** rastgele erişim $O(1)$’i sona ekleme $O(1)$ amortize ile birleştirip ikisinin en iyisini sunar — bu yüzden Python `list`’in temelidir. Veri yapısı seçimi, hangi işlemlerin sıcak yolda olduğuna bağlı bir takastır.

Builder Notu — Veri Yapısı Seçimi = Tensor Layout

Maliyet matrisinin verdiği ders — “her yapı bir takas; sıcak yoldaki işleme göre seç” — derin öğrenmede tensör bellek düzeni seçiminde birebir tekrar eder:

İleriye → contiguous tensor vs Python list: Bir batch’i Python list’inde tutmak (dağınık nesneler, bağlı liste sezgisi) ile tek bir contiguous tensörde tutmak (ardışık dizi sezgisi) arasındaki fark, tam olarak bu matristeki rastgele erişim/tarama takasıdır — vektörize işlemler ardışık belleği ister.
İleriye → .contiguous() çağrısı: transpose/permute sonrası bir tensör mantıksal olarak doğru ama bellekte dağınıktır; .contiguous() onu yeniden ardışık düzene kopyalar ($\Theta(n)$, tıpkı resize kopyası gibi) — çünkü birçok CUDA çekirdeği ardışık düzen olmadan çalışmaz veya yavaşlar.
İleriye → GPU bellek yerelliği: Şekil 3.4’nin cache argümanı GPU’da daha da keskindir; coalesced (bitişik) erişim tam bant genişliği kullanır, dağınık erişim çekirdeği bellek-bağlı yapar. “Hangi işlem sıcak yolda?” sorusu, layout kararıyla doğrudan performansa çevrilir.

3.15 Bu Dersin Özeti

Arayüz ne yapılacağını (işlemler), veri yapısı nasıl yapılacağını (gerçekleştirim) söyler.
İki temel arayüz: küme (değere/anahtara göre) ve dizi (sıraya göre).
Statik dizi: ardışık bellek; get_at/set_at $O(1)$, build/iter $\Theta(n)$.
Bağlı liste: düğüm + next işaretçisi; insert/delete_first $O(1)$, erişim $O(i)$.
Dinamik dizi (Python list): boyut $\Theta(n)$; ikiye-katlama ile insert_last amortize $O(1)$.
Geometrik seri son terimle domine olur: $1 + 2 + \cdots + 2^k = \Theta(2^k) = \Theta(n)$.
Amortize analiz: $k$ işlem en fazla $k \cdot T(n)$ zaman alır; nadiren pahalı, ortalama ucuz.

Tek Bir Cümle

Python list’in her “ucuz” append’i, arada bir yapılan pahalı ikiye-katlamanın işlem dizisine amortize edilmiş hâlidir — sihir değil, geometrik seri.

3.16 Kontrol Soruları

Soru 1: Arayüz (interface) ile veri yapısı (data structure) arasındaki fark nedir?

Cevap: Arayüz, ne yapılacağını söyler: hangi veriyi saklayabilirsin, hangi işlemler desteklenir ve bu işlemler ne anlama gelir (bir spesifikasyon). Veri yapısı, nasıl yapılacağını söyler: verinin somut gösterimi ve işlemleri destekleyen algoritmalar. Aynı arayüz (örneğin “dizi”) birden çok veri yapısıyla (statik dizi, bağlı liste, dinamik dizi) çözülebilir; her birinin farklı çalışma süreleri vardır.

Soru 2: Çok sık get_at ama nadiren ekleme gereken bir uygulamada hangi veri yapısı uygundur? Tersine, sürekli baştan ekleme gerekiyorsa?

Cevap: Sık rastgele erişim için statik dizi veya dinamik dizi uygundur (get_at $O(1)$). Sürekli baştan ekleme için bağlı liste uygundur (insert_first $O(1)$; dizilerde $O(n)$ çünkü kaydırma gerekir). Eğer hem sık get_at hem sık insert_first gerekiyorsa, tek bir basit yapı ikisini birden $O(1)$ yapamaz — bu ileri veri yapılarının (örneğin dengeli ağaçlar, Ders 6-7) motivasyonudur.

Soru 3: Dinamik dizi dolduğunda neden boyutu size + 1 değil de 2 × size yapılır?

Cevap: size + 1 (ya da sabit ekleme, örn. +5), her birkaç eklemede bir lineer yeniden-ayırma gerektirir → işlem başına hâlâ lineer zaman. 2 × size ise yeniden boyutlandırmaları 2’nin kuvvetlerinde seyrekleştirir; $n$ eklemenin toplam resize maliyeti geometrik seri olduğu için $\Theta(n)$’dir → işlem başına sabit amortize. Sabit çarpanla büyütme, amortize sabit zamanın anahtarıdır.

Soru 4: Python’da list.append() amortize O(1) ne demektir? Tek bir append neden bazen yavaş olabilir?

Cevap: “Amortize $O(1)$”, herhangi $k$ append’in toplamda en fazla $k \cdot O(1) = O(k)$ zaman aldığı anlamına gelir — işlem başına ortalama sabit. Ama tek bir append, dizi tam dolduğu anda denk gelirse, yeni (iki kat) dizi ayırıp tüm öğeleri kopyalar → o tek işlem $O(n)$. Bu nadir pahalı işlemin maliyeti, onu izleyen birçok ucuz append’e dağıtılır; dolayısıyla ortalama sabit kalır.

3.17 Egzersizler

Egzersiz 1. Statik dizi arayüzünün beş işlemini (build, length, iter, get_at, set_at) listele ve her birinin statik dizi gerçekleştiriminde çalışma süresini yaz. Hangileri $\Theta(n)$, hangileri $O(1)$?

Egzersiz 2. Bağlı listede insert_last’ı $O(1)$ yapmak için hangi zenginleştirme (augmentation) gerekir? Aynı zenginleştirmeyle delete_last neden hâlâ zordur ve bunu çözmek için ne gerekir?

Egzersiz 3. Dinamik dizide $n$ öğe ekleyip sonra hepsini delete_last ile silersen, dizi boyutu hâlâ $\Theta(n)$ kalır (oysa $n = 0$). Bu bellek israfını önlemek için “küçültme” (shrinking) kuralını tasarla. (İpucu: dizi ¼ dolduğunda yarıya indir — neden ⅓ veya ½ değil?)

Egzersiz 4. Python’da bir listeye $n$ kez append yaparken iç kapasitenin ne zaman büyüdüğünü gözlemle:

import sys

lst = []
prev = -1
for i in range(64):
    cap = sys.getsizeof(lst)
    if cap != prev:
        print("uzunluk", len(lst), "-> kapasite baytlari", cap)
        prev = cap
    lst.append(i)

Kapasite hangi uzunluklarda zıplıyor? Bu, ikiye-katlama (doubling) sezgisini doğruluyor mu?

Egzersiz 5. Küme (set) arayüzü, dizi (sequence) arayüzünden nasıl ayrılır? Öğeleri değerine/anahtarına göre aramak (sıraya göre değil), neden farklı bir veri yapısı gerektirir? Ders 3-4’e (sıralama ve hashing) bir köprü kur.

3.18 Sonraki Ders İçin Hazırlık

Ders 3 (L3): Kümeler ve Sıralama

Justin Solomon ile küme (set) arayüzüne ve onu çözmenin ilk adımı olan sıralamaya (insertion, selection, merge sort) geçiyoruz. Bu derste değindiğimiz “değere göre arama” sorusu orada merkeze oturur. (Not: ders akışında araya Problem Oturumu 1 girer — bu dersin kavramlarını pekiştiren problemler.)

Ders 3 Öncesi Yapılacak

Bu dersin egzersizlerini, özellikle Egzersiz 4’ü (Python kapasite gözlemi) çöz.
Üç veri yapısı tablosunu (Şekil 3.7) ezberden çizebilecek hâle gel.
Ana cümleyi tekrar oku: “Aynı işi farklı veri yapıları farklı maliyetlerle yapar.”

3.19 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Sayfada
Arayüz vs veri yapısı	Ne (spesifikasyon) vs nasıl (gerçekleştirim)	Böl. 1
Dizi (sequence)	Öğeleri belirli bir sırada tutan arayüz	Böl. 2-3
Statik dizi	Ardışık bellek; get_at/set_at $O(1)$	Böl. 4
Bellek ayırma modeli	$n$ boyutlu dizi $\Theta(n)$ zamanda ayrılır	Böl. 5
Word boyutu	$w \geq \log n$ ($n$ öğeyi adresleyebilmek için)	Böl. 5
Bağlı liste	Düğüm + next; insert/delete_first $O(1)$	Böl. 7
Augmentation	Ekstra bilgi (tail) ile $O(1)$ get_last	Böl. 8
Dinamik dizi	Python list; boyut $\Theta(n)$, ikiye-katlama	Böl. 10
Geometrik seri	$1+2+\cdots+2^k = \Theta(2^k) = \Theta(n)$	Böl. 11
Amortize analiz	$k$ işlem en fazla $k \cdot T(n)$ zaman	Böl. 12

3.20 Builder ve OMSCS Bağlantıları

6 köprü

Bu ders, ileri algoritma ve sistem mühendisliğinin temel dilini kurar — köprülerin özeti:

Amortize analiz → altyapı: log-structured storage, hash tablosu rehashing, garbage collection — “nadiren pahalı, çoğu zaman ucuz” her yerde aynı analiz.
Dinamik dizi → Python list, C++ vector, Java ArrayList’in iç mekanizması; kapasite büyütme stratejisi.
Arayüz / veri yapısı ayrımı → API tasarımı: aynı sözleşme (interface), değişebilir backend (implementation).
word RAM + işaretçiler → bellek modeli ve cache yerelliği; dizi (ardışık) ile bağlı liste (dağınık) arasındaki gerçek performans farkı.
Augmentation → veritabanı indeksleri: ekstra bir yapı (B-ağacı, hash) ekleyip sorguyu hızlandırma — aynı augmentation fikri.
Geometrik seri sezgisi → ikiye-katlama/yarıya-indirme stratejileri: connection pool, buffer büyütme, exponential backoff.

Tek bir şey alıp gideceksen

Aynı işi farklı veri yapıları farklı maliyetlerle yapar; mühendislik, “hangi işlem ne sıklıkta çağrılıyor?” sorusuna göre doğru yapıyı seçmektir. Python list’in zarafeti, bu seçimi amortize analizle senin için çoktan çözmüş olmasıdır.

--- title: "Veri Yapıları ve Dinamik Diziler" subtitle: "Arayüz vs veri yapısı, statik dizi / bağlı liste / dinamik dizi, geometrik seri ve amortize analiz" --- ::: {.callout-note title="Bölüm bilgisi"} - **Demaine'in videosu:** [YouTube — Lecture 2: Data Structures and Dynamic Arrays](https://www.youtube.com/watch?v=CHhwJjR0mZA) (≈50 dk) - **OCW sayfası:** [MIT 6.006 Lecture 2: Data Structures and Dynamic Arrays](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-2-data-structures-and-dynamic-arrays/) - **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 2 - **Hocalar:** Erik Demaine (Jason Ku, Justin Solomon) - **Okuma süresi:** ≈24 dk ::: ## Bu Derste Ne Var? {#sec-bu-derste-d02} Ders 1 problem ile algoritma arasındaki farkı kurdu. Bu ders, aynı ayrımı veri tarafında yapar: **arayüz (interface)** ile **veri yapısı (data structure)** arasındaki fark. Erik Demaine, dersin ilk veri yapıları bölümüne enerjik bir girişle başlar. Üç temel kavram bu derste yan yana gelir: 1. **Arayüz vs veri yapısı** — arayüz *ne* yapılacağını (desteklenen işlemler), veri yapısı *nasıl* yapılacağını (gerçekleştirim) söyler. 2. **Dizi (sequence) arayüzü** — $n$ öğeyi sıralı tutma; statik dizi, bağlı liste ve dinamik dizi ile çözülür. 3. **Amortize analiz** — dinamik dizinin (Python `list`) neden sona eklemede amortize $O(1)$ olduğunun ispatı. > *"an interface says what you want to do. A data structure says how you do it."* — Demaine, 1:18 ```{mermaid} %%| label: fig-concept-map %%| echo: false %%| fig-cap: "Ders 2'nin kavram haritası: arayüz (ne) ile veri yapısı (nasıl) ayrımından, dizi arayüzünü çözen üç gerçekleştirime — statik dizi (rastgele erişim O(1)), bağlı liste (uç işlemi O(1)), dinamik dizi (ikisinin en iyisi)." flowchart TD A["Ders 2: Veri Yapıları ve Dinamik Diziler"] --> B["Arayüz (ne)"] A --> C["Veri Yapısı (nasıl)"] C --> D["Dizi (sequence) arayüzü"] D --> E["Statik Dizi rastgele erişim O(1) insert/delete Θ(n)"] D --> F["Bağlı Liste uç işlemi O(1) erişim O(i)"] D --> G["Dinamik Dizi ikisinin en iyisi insert_last amortize O(1)"] G --> H["İkiye-katlama + geometrik seri"] H --> I["Amortize analiz nadiren pahalı, çoğu ucuz"] classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937 classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937 classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937 class A root class B,C,D branch class E,F,G,H,I leaf ``` ::: {.callout-tip title="Builder Notu — Arayüz/Implementasyon Ayrımı ve PyTorch"} Demaine'in arayüz/veri yapısı ayrımı, modern ML kütüphanelerinin temel tasarım desenidir — aynı sözleşme (interface), değişebilir gerçekleştirim (implementation): - **İleriye → PyTorch `nn.Module`:** Bir katmanın `forward()` arayüzü *ne* hesaplanacağını söyler; arkadaki tensör depolaması, bellek düzeni ve çekirdek (kernel) seçimi *nasıl* yapılacağını. Aynı `nn.Linear` API'si CPU, CUDA veya MPS backend'iyle çalışır — arayüz sabit, veri yapısı değişir. - **Geriye → Python (Phase 1):** Demaine açıkça söyler, bu giriş dersleri "Python'ın nasıl gerçekleştirildiğini" anlatır. Python `list` = dinamik dizi; bu ders onun iç mekanizmasını açar. - **Geriye → word RAM (Ders 1):** statik dizinin $O(1)$ erişimi doğrudan Ders 1'in word RAM modeline dayanır (ardışık bellek + rastgele erişim). Tek cümle: *Aynı arayüzü farklı veri yapıları çözer; doğru seçim, hangi işlemin ne sıklıkta çağrıldığına bağlıdır.* ::: ```{python} #| echo: false # ============================================================================ # SETUP — 6.006 Ders 2 motoru (_engine.py D2) + Slate+Amber viz (_viz.py D2) # Bu hücre gizlidir (#| echo: false). Aşağıdaki TÜM figür hücreleri bu hücrede # tanımlanan StaticArray / LinkedList / DynamicArray / amortize_trace / # geometric_series / cost_matrix + draw_* + COL_* + apply_style'ı IMPORT # ETMEDEN kullanır. Notion'daki öğretim içeriği (görünür prose + display python) # bu motorun tarif seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar. # # NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama # backend'ini ezer (plt.show() 0 figür üretir; brief §2/§11). Standalone testte # savefig kullanılır; Quarto render'da jupyter inline backend'i ayarlar. # ============================================================================ import math import matplotlib.pyplot as plt from matplotlib.patches import FancyBboxPatch, FancyArrowPatch import networkx as nx # --------------------------------------------------------------------------- # _engine.py (D2) — veri yapıları motoru (DETERMİNİSTİK + TEST EDİLEBİLİR) # --------------------------------------------------------------------------- class StaticArray: """Statik dizi (L2 §3-4): ardışık bellekte sabit-boyutlu dizi soyutlaması. Öğe sayısı n DEĞİŞMEZ; öğeler set_at ile değişir. Word RAM modeline dayanır: ardışık bellek → ofset aritmetiğiyle (base + i) rastgele erişim O(1). """ def __init__(self, n=0): self.data = [None] * n self.n = n @staticmethod def build(x): items = list(x) arr = StaticArray(len(items)) for i, v in enumerate(items): arr.data[i] = v return arr def length(self): return self.n def get_at(self, i): if not 0 <= i < self.n: raise IndexError(f"get_at: index {i} aralık dışı (n={self.n})") return self.data[i] def set_at(self, i, x): if not 0 <= i < self.n: raise IndexError(f"set_at: index {i} aralık dışı (n={self.n})") self.data[i] = x def iter(self): for i in range(self.n): yield self.data[i] def to_list(self): return list(self.data) class Node: """Bağlı liste düğümü (L2 §7): bir `item` alanı + bir `next` işaretçisi.""" def __init__(self, item, next=None): self.item = item self.next = next class LinkedList: """Tek yönlü bağlı liste (L2 §7-8): head + tail augmentation ile. §8 augmentation: son düğüme `tail` işaretçisi → insert_last/get_last O(1). get_at(i) → i kez next takip; ADIM SAYISINI döndürür (figür/verify). """ def __init__(self): self.head = None self.tail = None self.n = 0 def length(self): return self.n def insert_first(self, x): node = Node(x, self.head) self.head = node if self.tail is None: self.tail = node self.n += 1 def insert_last(self, x): node = Node(x, None) if self.tail is None: self.head = node self.tail = node else: self.tail.next = node self.tail = node self.n += 1 def get_at(self, i): if not 0 <= i < self.n: raise IndexError(f"get_at: index {i} aralık dışı (n={self.n})") node = self.head steps = 0 for _ in range(i): node = node.next steps += 1 steps += 1 return node.item, steps def to_list(self): out = [] node = self.head while node is not None: out.append(node.item) node = node.next return out class DynamicArray: """Dinamik dizi = Python `list`'in iç mekanizması (L2 §10-12). length == size olunca ikiye-katlama (1→2→4→8→...) ile resize. Geometrik seri sayesinde n append toplam Θ(n) → insert_last amortize O(1). """ def __init__(self): self.data = [] self.size = 0 self.n = 0 self.resize_events = [] def length(self): return self.n def get_at(self, i): if not 0 <= i < self.n: raise IndexError(f"get_at: index {i} aralık dışı (length={self.n})") return self.data[i] def set_at(self, i, x): if not 0 <= i < self.n: raise IndexError(f"set_at: index {i} aralık dışı (length={self.n})") self.data[i] = x def _resize(self, new_size): copy_cost = self.n new_data = [None] * new_size for i in range(self.n): new_data[i] = self.data[i] self.resize_events.append((self.n, self.size, new_size, copy_cost)) self.data = new_data self.size = new_size def append(self, x): if self.n == self.size: new_size = 1 if self.size == 0 else self.size * 2 self._resize(new_size) self.data[self.n] = x self.n += 1 insert_last = append def to_list(self): return [self.data[i] for i in range(self.n)] def amortize_trace(n): """n kez insert_last için işlem-başı maliyet izi — DETERMİNİSTİK (L2 §11-12).""" arr = DynamicArray() per_op = [] resize_at = [] for k in range(n): cost = 1 if arr.n == arr.size: cost += arr.n resize_at.append(k) arr.append(x=k) per_op.append(cost) total = sum(per_op) cumulative = [] running = 0 for k, c in enumerate(per_op): running += c cumulative.append(running / (k + 1)) return { "per_op": per_op, "cumulative": cumulative, "resize_at": resize_at, "total": total, "average": (total / n) if n > 0 else 0.0, } def geometric_series(k): """Geometrik seri 1 + 2 + ... + 2ᵏ — terimler, toplam, kimlik 2ᵏ⁺¹−1 (L2 §11).""" if k < 0: raise ValueError("geometric_series: k ≥ 0 olmalı") terms = [2 ** i for i in range(k + 1)] total = sum(terms) identity = 2 ** (k + 1) - 1 return { "terms": terms, "sum": total, "identity": identity, "last_term": 2 ** k, "matches": total == identity, } def cost_matrix(): """Demaine kapanış tablosu (L2 §13): 4 işlem × 3 veri yapısı çalışma süreleri.""" ops = [ "get_at / set_at", "insert / delete_first", "insert / delete_last", "insert / delete_at", ] structures = ["Statik Dizi", "Bağlı Liste", "Dinamik Dizi"] table = { "get_at / set_at": ("O(1)", "O(n)", "O(1)"), "insert / delete_first": ("O(n)", "O(1)", "O(n)"), "insert / delete_last": ("O(n)", "O(n)", "O(1) amortize"), "insert / delete_at": ("O(n)", "O(n)", "O(n)"), } cells = {} for op in ops: for s_idx, struct in enumerate(structures): cells[(op, struct)] = table[op][s_idx] return {"ops": ops, "structures": structures, "cells": cells} # --------------------------------------------------------------------------- # _viz.py (D2) — Slate + Amber stil sabitleri (HEX birebir brief §1/§8) # --------------------------------------------------------------------------- COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve COL_ACCENT = "#f59e0b" # amber-500 — vurgu (hızlı/kötü; aktif eşleşme) COL_TEXT = "#1f2937" # slate-800 — metin COL_BG = "#f3f4f6" # slate-100 — arka plan / callout / kutu dolgusu COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast COL_AMBER_600 = "#d97706" # koyu amber COL_AMBER_300 = "#fcd34d" # açık amber COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu) COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara COL_WHITE = "#ffffff" def apply_style(ax): """Bir eksene tutarlı Slate+Amber görünümü uygular (curve figürleri için).""" ax.set_facecolor(COL_WHITE) ax.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8) for spine in ax.spines.values(): spine.set_color(COL_SLATE_400) ax.tick_params(colors=COL_TEXT) ax.title.set_color(COL_TEXT) ax.xaxis.label.set_color(COL_TEXT) ax.yaxis.label.set_color(COL_TEXT) return ax def draw_static_array(ax, cells=("x₀", "x₁", "x₂", "x₃", "x₄"), access_i=2, base_label="base"): """Statik dizi (L2 §4): ardışık hücreler + ofset aritmetiği + O(1) erişim.""" cells = list(cells) n = len(cells) cell_w, cell_h, y0 = 1.0, 1.0, 0.0 centers = [] for k, content in enumerate(cells): x = k * cell_w hot = (k == access_i) box = FancyBboxPatch( (x, y0), cell_w * 0.96, cell_h * 0.96, boxstyle="square,pad=0.0", fc=COL_AMBER_100 if hot else COL_BG, ec=COL_ACCENT if hot else COL_PRIMARY, linewidth=2.6 if hot else 1.7, zorder=2, ) ax.add_patch(box) cx, cy = x + cell_w * 0.48, y0 + cell_h * 0.48 centers.append((cx, cy)) ax.text(cx, cy, content, ha="center", va="center", fontsize=12, color=COL_TEXT, weight="bold", zorder=4) ax.text(cx, y0 - 0.28, f"{base_label}+{k}", ha="center", va="center", fontsize=8, color=COL_SLATE_500, zorder=4) cx, cy = centers[access_i] ax.add_patch(FancyArrowPatch( (cx, cy + cell_h * 0.95), (cx, cy + cell_h * 0.55), arrowstyle="-|>", mutation_scale=16, color=COL_ACCENT, linewidth=2.2, zorder=5, )) ax.text(cx, cy + cell_h * 1.18, f"get_at({access_i}) = {base_label}+{access_i} → O(1)", ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=5) ax.text((n - 1) * cell_w * 0.5, y0 - 0.62, "ardışık bellek — rastgele erişim ofset aritmetiğiyle sabit zaman", ha="center", va="center", fontsize=9, color=COL_SLATE_500, style="italic") ax.set_xlim(-0.4, n * cell_w + 0.4) ax.set_ylim(y0 - 0.95, y0 + cell_h * 1.5) ax.set_aspect("equal") ax.axis("off") return centers def draw_linked_list(ax, items=("a", "b", "c", "d"), access_i=2): """Bağlı liste (L2 §7-8): (item|next) + head/tail + next okları + i-adım zinciri.""" items = list(items) n = len(items) node_w, node_h, gap, y0 = 1.5, 0.9, 0.8, 0.0 item_frac = 0.62 centers = [] for k, it in enumerate(items): x = k * (node_w + gap) on_chain = (k <= access_i) ax.add_patch(FancyBboxPatch( (x, y0), node_w * item_frac, node_h, boxstyle="square,pad=0.0", fc=COL_AMBER_100 if on_chain else COL_BG, ec=COL_ACCENT if on_chain else COL_PRIMARY, linewidth=2.4 if on_chain else 1.6, zorder=2, )) ax.add_patch(FancyBboxPatch( (x + node_w * item_frac, y0), node_w * (1 - item_frac), node_h, boxstyle="square,pad=0.0", fc=COL_BG, ec=COL_ACCENT if on_chain else COL_PRIMARY, linewidth=2.4 if on_chain else 1.6, zorder=2, )) ax.text(x + node_w * item_frac * 0.5, y0 + node_h * 0.5, str(it), ha="center", va="center", fontsize=12, color=COL_TEXT, weight="bold", zorder=4) ax.text(x + node_w * (item_frac + (1 - item_frac) * 0.5), y0 + node_h * 0.5, "next", ha="center", va="center", fontsize=7.5, color=COL_SLATE_500, zorder=4) centers.append((x + node_w * 0.5, y0 + node_h * 0.5)) nx0 = x + node_w ny = y0 + node_h * 0.5 if k < n - 1: hot = (k < access_i) ax.add_patch(FancyArrowPatch( (nx0, ny), (nx0 + gap, ny), arrowstyle="-|>", mutation_scale=14, color=COL_ACCENT if hot else COL_SLATE_400, linewidth=2.4 if hot else 1.4, zorder=3, )) else: ax.text(nx0 + gap * 0.5, ny, "∅", ha="center", va="center", fontsize=12, color=COL_SLATE_500, zorder=4) hx, hy = centers[0] ax.text(hx, y0 + node_h + 0.45, "head", ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold") ax.add_patch(FancyArrowPatch( (hx, y0 + node_h + 0.30), (hx, y0 + node_h + 0.02), arrowstyle="-|>", mutation_scale=13, color=COL_AMBER_700, linewidth=2.0)) tx, ty = centers[-1] ax.text(tx, y0 + node_h + 0.45, "tail", ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold") ax.add_patch(FancyArrowPatch( (tx, y0 + node_h + 0.30), (tx, y0 + node_h + 0.02), arrowstyle="-|>", mutation_scale=13, color=COL_AMBER_700, linewidth=2.0)) ax.text((n * (node_w + gap)) * 0.5 - gap * 0.5, y0 - 0.45, f"get_at({access_i}): head'den {access_i+1} düğüm ziyaret → O(i)", ha="center", va="center", fontsize=10, color=COL_AMBER_700, weight="bold") ax.text((n * (node_w + gap)) * 0.5 - gap * 0.5, y0 - 0.82, "bellekte dağınık — sıra yalnızca next işaretçileriyle", ha="center", va="center", fontsize=9, color=COL_SLATE_500, style="italic") ax.set_xlim(-0.5, n * (node_w + gap) - gap + 0.6) ax.set_ylim(y0 - 1.15, y0 + node_h + 0.85) ax.set_aspect("equal") ax.axis("off") return centers def draw_dynamic_resize(ax, stages=(1, 2, 4, 8)): """Dinamik dizi büyütme (L2 §10-11): ikiye-katlama 1→2→4→8 + kopya + length/size.""" stages = list(stages) cell_w, cell_h = 0.5, 0.5 row_gap = 1.45 prev_size = 0 y = 0.0 row_y = [] for s_idx, size in enumerate(stages): length = prev_size if prev_size > 0 else size y = -s_idx * row_gap row_y.append(y) for c in range(size): x = c * cell_w full = c < length ax.add_patch(FancyBboxPatch( (x, y), cell_w * 0.9, cell_h * 0.9, boxstyle="square,pad=0.0", fc=COL_AMBER_100 if full else COL_WHITE, ec=COL_ACCENT if full else COL_SLATE_400, linewidth=1.8 if full else 1.2, zorder=2, )) ax.text(size * cell_w + 0.35, y + cell_h * 0.45, f"size={size}, length={length}", ha="left", va="center", fontsize=9.5, color=COL_TEXT) prev_size = size for s_idx in range(len(stages) - 1): y_top = row_y[s_idx] y_bot = row_y[s_idx + 1] ax.add_patch(FancyArrowPatch( (-0.25, y_top + cell_h * 0.45), (-0.25, y_bot + cell_h * 0.45), arrowstyle="-|>", mutation_scale=13, color=COL_AMBER_700, linewidth=1.8, zorder=3, connectionstyle="arc3,rad=-0.35")) ax.text(-1.15, (row_y[0] + row_y[-1]) * 0.5 + cell_h * 0.45, "ikiye-katla\n+ kopyala", ha="center", va="center", fontsize=9, color=COL_AMBER_700, weight="bold", rotation=90) max_size = max(stages) ax.set_xlim(-1.6, max_size * cell_w + 3.0) ax.set_ylim(row_y[-1] - 0.5, row_y[0] + cell_h + 0.3) ax.set_aspect("equal") ax.axis("off") return row_y def draw_amortize(ax_cost, ax_avg, trace): """Amortize analiz iki-panel (L2 §12, İMZA): per-op maliyet + kümülatif ortalama.""" per_op = trace["per_op"] cumulative = trace["cumulative"] resize_set = set(trace["resize_at"]) ks = list(range(1, len(per_op) + 1)) apply_style(ax_cost) colors = [COL_ACCENT if (k - 1) in resize_set else COL_PRIMARY for k in ks] ax_cost.bar(ks, per_op, color=colors, width=0.85, zorder=3) ax_cost.set_xlabel("append işlemi #") ax_cost.set_ylabel("o işlemin maliyeti") ax_cost.set_title("İşlem-başı maliyet — resize'da 2ᵏ spike (amber)", color=COL_TEXT, fontsize=11) ax_cost.bar([], [], color=COL_PRIMARY, label="ucuz (maliyet 1)") ax_cost.bar([], [], color=COL_ACCENT, label="pahalı (resize / kopya)") ax_cost.legend(loc="upper left", fontsize=8.5, framealpha=0.9) apply_style(ax_avg) ax_avg.plot(ks, cumulative, color=COL_PRIMARY, linewidth=2.2, marker="o", markersize=2.5, zorder=3, label="kümülatif ortalama (toplam/işlem)") final_avg = trace["average"] ax_avg.axhline(final_avg, color=COL_ACCENT, linewidth=1.8, linestyle="--", zorder=2, label=f"amortize sınırı ≈ {final_avg:.2f}") ax_avg.set_xlabel("append işlemi #") ax_avg.set_ylabel("ortalama maliyet / işlem") ax_avg.set_ylim(0, max(cumulative) * 1.25 + 0.5) ax_avg.set_title("Kümülatif ortalama → sabit (amortize O(1))", color=COL_TEXT, fontsize=11) ax_avg.legend(loc="upper right", fontsize=8.5, framealpha=0.9) return ax_cost, ax_avg def draw_cost_matrix(ax, matrix): """Maliyet matrisi (L2 §13, İMZA): 4 işlem × 3 veri yapısı renkli tablo.""" ops = matrix["ops"] structures = matrix["structures"] cells = matrix["cells"] n_rows = len(ops) n_cols = len(structures) cell_w, cell_h = 2.7, 1.0 label_w = 3.6 COL_GOOD = "#cfe8da" COL_GOOD_EC = "#3f7d5e" def cell_style(text): if text == "O(1)": return COL_GOOD, COL_GOOD_EC, 1.8 if "amortize" in text: return COL_AMBER_100, COL_ACCENT, 2.4 return COL_AMBER_300, COL_AMBER_700, 1.6 for c, struct in enumerate(structures): x = label_w + c * cell_w + cell_w * 0.5 ax.text(x, cell_h * 0.5, struct, ha="center", va="center", fontsize=11, color=COL_TEXT, weight="bold") for r, op in enumerate(ops): y = -(r + 1) * cell_h ax.text(label_w - 0.15, y + cell_h * 0.5, op, ha="right", va="center", fontsize=10, color=COL_TEXT, weight="bold") for c, struct in enumerate(structures): x = label_w + c * cell_w text = cells[(op, struct)] fc, ec, lw = cell_style(text) ax.add_patch(FancyBboxPatch( (x, y), cell_w * 0.96, cell_h * 0.9, boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=2)) ax.text(x + cell_w * 0.48, y + cell_h * 0.45, text, ha="center", va="center", fontsize=10.5, color=COL_TEXT, weight="bold", zorder=4) ax.set_xlim(-0.2, label_w + n_cols * cell_w + 0.2) ax.set_ylim(-(n_rows + 1) * cell_h - 0.2, cell_h + 0.2) ax.set_aspect("equal") ax.axis("off") return ax def draw_memory_locality(ax): """Bellek yerelliği (L2 §7/§9): ardışık dizi (cache-dostu) vs dağınık liste (cache-miss).""" n = 6 cell_w, cell_h = 0.85, 0.7 y_top = 2.2 for k in range(n): x = k * cell_w ax.add_patch(FancyBboxPatch( (x, y_top), cell_w * 0.97, cell_h, boxstyle="square,pad=0.0", fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=2)) ax.text(x + cell_w * 0.48, y_top + cell_h * 0.5, f"x{k}", ha="center", va="center", fontsize=9, color=COL_TEXT, weight="bold", zorder=4) ax.text(n * cell_w * 0.5, y_top + cell_h + 0.32, "Statik dizi — ardışık bellek (cache-dostu)", ha="center", va="center", fontsize=10.5, color=COL_PRIMARY, weight="bold") ax.text(n * cell_w * 0.5, y_top - 0.30, "tek atlamayla sıralı erişim · yüksek yerellik", ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, style="italic") y_base = -1.0 scatter = [(0.2, 0.0), (3.6, 0.55), (1.4, -0.7), (4.7, -0.35), (2.6, 0.3), (5.4, 0.7)] node_w, node_h = 0.7, 0.55 centers = [] for k, (sx, sy) in enumerate(scatter): x = sx y = y_base + sy ax.add_patch(FancyBboxPatch( (x, y), node_w, node_h, boxstyle="round,pad=0.02,rounding_size=0.06", fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=3)) ax.text(x + node_w * 0.5, y + node_h * 0.5, f"n{k}", ha="center", va="center", fontsize=8.5, color=COL_TEXT, weight="bold", zorder=4) centers.append((x + node_w * 0.5, y + node_h * 0.5)) for k in range(len(centers) - 1): x0, y0 = centers[k] x1, y1 = centers[k + 1] ax.add_patch(FancyArrowPatch( (x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=12, color=COL_AMBER_700, linewidth=1.5, zorder=2, shrinkA=10, shrinkB=10, connectionstyle="arc3,rad=0.18")) ax.text(2.9, y_base + 1.35, "Bağlı liste — dağınık düğümler (cache-miss)", ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold") ax.text(2.9, y_base - 1.05, "her next uzun bir bellek sıçraması · düşük yerellik", ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, style="italic") ax.set_xlim(-0.6, max(n * cell_w, 6.3) + 0.4) ax.set_ylim(y_base - 1.5, y_top + cell_h + 0.7) ax.set_aspect("equal") ax.axis("off") return ax ``` ## Arayüz mü, Veri Yapısı mı? {#sec-arayuz-veri-yapisi} Demaine, bir programcının **API**, eski kuşak bir algoritmacının **ADT** (abstract data type) dediği şeyi **arayüz** olarak adlandırır. Ayrım nettir: - **Arayüz** = *ne*: hangi veriyi saklayabilirsin, hangi işlemleri destekler, bu işlemler ne anlama gelir. Bu bir **spesifikasyondur** (problem ifadesinin veri karşılığı). - **Veri yapısı** = *nasıl*: verinin somut gösterimi ve işlemleri destekleyen **algoritmalar**. Algoritmalar tam da burada devreye girer. > *"The same problem can be solved by many different data structures."* — Demaine, 3:23 Veriyi sadece saklamak sıkıcıdır (bir dosyaya atarsın). İşi *ilginç* kılan, o veri üzerindeki **işlemlerdir** — ve farklı veri yapıları bazı işlemleri diğerlerinden hızlı destekler. Doğru veri yapısı, ne için kullanacağına bağlıdır. ## İki Temel Arayüz: Küme ve Dizi {#sec-kume-dizi} 6.006 iki ana arayüze odaklanır: - **Küme (set):** öğeleri *değerlerine* (anahtar/key) göre tutar — sıralı tutma, bir değeri arama. "Set" bir matematikçi için başka, bir Python programcısı için başka şey ifade eder. - **Dizi (sequence):** öğeleri *belirli bir sırada* tutar — örneğin 5, 2, 9, 7 sayılarını bu sırayla. Python'da bunu bir `list` ile saklarsın; sırayı korur. Bu ders **dizi** arayüzüne odaklanır (küme arayüzüne sonda değinilir, Ders 3-4'te derinleşir). İki temel araç vardır: **diziler (arrays)** ve **işaretçiler (pointers / bağlı yapılar)**. Bugün ikisini de göreceğiz. ## Statik Dizi Arayüzü {#sec-statik-dizi-arayuzu} En basit dizi arayüzü **statik dizidir**: öğe sayısı $n$ değişmez (ama öğelerin kendisi değişebilir). Öğeler $x_0, x_1, \ldots, x_{n-1}$ olarak etiketlenir (Python'daki gibi 0'dan başlar). Desteklenen işlemler: - **build(x):** verilen öğelerden $n$ boyutlu yeni bir dizi kur. - **length():** sabit $n$ değerini döndür. - **iter():** öğeleri $x_0$'dan $x_{n-1}$'e sırayla üret (en az lineer zaman). - **get_at(i):** $i$'inci öğeyi ($x_i$) döndür. - **set_at(i, x):** $i$'inci öğeyi yeni bir değerle değiştir. `build` ve `iter` doğası gereği tüm öğelere dokunur → $\Theta(n)$. Asıl ilginç olan, dizinin *ortasına* dinamik erişim: get_at ve set_at. ## Statik Dizi (Static Array) {#sec-statik-dizi} Bu arayüzün doğal çözümü **statik dizidir** (Python'da `list` denir; Demaine "array" demeyi tercih eder). Python'da aslında statik dizi yoktur — yalnızca dinamik diziler vardır — ama kavramı anlamak gerekir. Statik dizi, belleğin **ardışık (consecutive)** bir parçasıdır. Ders 1'in word RAM modeline dayanır: bellek, $w$-bitlik word'lerden oluşan bir dizidir ve herhangi bir word'e sabit zamanda rastgele erişilebilir. Bir diziye $i$ indeksinden erişmek, basit bir **ofset aritmetiğidir** (@fig-static-array): dizinin başlangıç adresi (Python'da `id(array)`) artı $i$. > *"as long as I store my array consecutively in memory, I can access the array in constant time."* — Demaine, 11:26 Bu yüzden statik dizi, get_at ve set_at işlemlerini **$O(1)$** zamanda çözer. length de $O(1)$'dir ($n$'i adresle birlikte saklarız). build ve iter $\Theta(n)$'dir. Bu çalışma süreleri **optimaldir** — basit ama bu modele giderek daha çok ihtiyaç duyacağız. ```{python} #| label: fig-static-array #| fig-cap: "Statik dizi: öğeler $x_0 \\ldots x_4$ **ardışık bellekte** yan yana durur. i'inci öğenin adresi basit bir **ofset aritmetiğiyle** bulunur: `base + i`. Bu yüzden `get_at(i)` herhangi bir indekse tek hamlede ulaşır — **$O(1)$ rastgele erişim** (amber vurgulu $x_2$). Bu, Ders 1'in word-RAM modeline dayanır: bir adres tek word'e sığar ve bellek hücresine sabit zamanda erişilir. Bedeli, dizinin boyutunun sabit olmasıdır." #| fig-width: 8.5 #| fig-height: 3.6 # --- Statik dizi: ardışık bellek + ofset aritmetiği + O(1) get_at (deterministik) --- # 5 hücre x₀..x₄ ardışık bellekte. access_i=2 → O(1) erişim örneği (amber vurgu + ok). cells = ("x₀", "x₁", "x₂", "x₃", "x₄") access_i = 2 fig, ax = plt.subplots(figsize=(8.5, 3.6)) draw_static_array(ax, cells=cells, access_i=access_i, base_label="base") ax.set_title( "Statik dizi: ardışık bellek + ofset aritmetiği (base + i)", color=COL_TEXT, fontsize=12.5, pad=20, ) plt.tight_layout() plt.show() ``` ## Bellek Ayırma Modeli ve Word Boyutu {#sec-bellek-word-d02} build'in nasıl çalıştığını tanımlamak için **bellek ayırma modeli** gerekir. En temiz varsayım: $n$ boyutlu bir diziyi **$\Theta(n)$** zamanda ayırabiliriz. > *"the cleanest one is just to assume that you can allocate an array of size n in theta n time."* — Demaine, 13:09 Neden sabit değil de lineer? Çünkü ayrılan bellek başlangıçta belirsizdir; onu 0'larla başlatmak lineer maliyet ister. Bu modelin güzel bir yan etkisi: kullandığın yer (space), kullandığın zamandan (time) fazla olamaz. Sonsuz boyutlu bir dizi ayırıp birkaç öğe kullanmak gerçekçi değildir — bellek ayırmanın bir bedeli olmalıdır. **Word boyutu ($w \geq \log n$):** Dizi erişiminin sabit zaman olması için, word boyutu $w$ en az $\log n$ kadar olmalıdır. Sebep: $n$ öğeyle çalışıyorsak, en azından onları **adresleyebilmeliyiz** — "$i$'inciyi ver" diyebilmek için $i$ sayısını bir word'e sığdırmalıyız. Bu yüzden $w \geq \log n$. > *"the word size has to grow with n... at least as fast as log n."* — Demaine, 15:13 Bu, gerçek makineler (sabit boyut) ile teori (ölçeklenebilirlik) arasında köprü kurar: gerçekte daha büyük girdi için daha çok RAM alırsın; teoride de $w$, $n$ ile birlikte asimptotik olarak büyür. ## Dinamik Dizi Arayüzü {#sec-dinamik-dizi-arayuzu} Statik arayüze iki **dinamik işlem** ekleriz: dizinin ortasına **insert_at** ve ortasından **delete_at**. insert_at, set_at'ten farklıdır: hiçbir bilgiyi silmez; eklenen konumdan sonraki tüm öğeler indekslerini bir kaydırır ($n' = n+1$). İndeksleme inceliği önemlidir: insert_at(2, x)'ten sonra get_at(2) yeni öğeyi, get_at(3) eski $x_2$'yi döndürür. Bu izlemesi zordur ama uçlarda (baş/son) ekleme/silme yaparken çok kullanışlıdır. Bu yüzden özel durumları tanımlarız: insert/delete **first** ve **last**, get/set **first** ve **last**. > *"insert_last doesn't change the indices of any of the old items."* — Demaine, 19:59 Kritik gözlem: insert_last eski öğelerin indekslerini değiştirmez (güzel özellik); insert_first hepsini $+1$ kaydırır. Tüm dinamik dizi arayüzünü sabit zamanda çözmek **imkânsızdır** (ispatlanabilir), ama özel durumları — yalnızca uçlardan ekleme/silme — verimli çözebiliriz. İşte bu yüzden özel durumlar ilginçtir. ## Bağlı Liste (Linked List) {#sec-bagli-liste} Dinamik diziyi çözen ilk veri yapısı **bağlı listedir**. Öğeleri **düğümlerde (node)** saklarız; her düğümde bir **item** alanı ve bir **next** (sonraki) işaretçisi vardır — iki sınıf değişkenli bir nesne gibi. Düğümler next işaretçileriyle birbirine bağlanır; sıra, bu işaretçilerle örtük olarak temsil edilir (@fig-linked-list). Veri yapısı bir **head** (baş) işaretçisiyle temsil edilir. Bu, **işaretçi tabanlı** bir veri yapısıdır (statik dizi ise dizi tabanlıydı). İşaretçiler tek bir word'e sığar, bu yüzden word RAM modelinde sabit zamanda dereference edilebilir (işaret edilen düğüme bakılabilir). Düğümler bellekte rastgele sırada durur — işaretçiler aslında dev bellek dizisindeki indekslerdir. > *"linked list, insert- and delete_first are constant time."* — Demaine, 30:41 Bağlı listenin **uçlarda** dinamik olması güçlüdür: yeni bir baş öğe eklemek (insert_first) sabit zamandır — yeni düğüm ayır, next'ini eski başa bağla, head'i güncelle. Ancak **rastgele erişim** zayıftır: $i$'inci öğeye ulaşmak için $i$ kez next takip etmek gerekir → get_at/set_at $O(i)$, en kötü durumda $\Theta(n)$. Statik dizinin tam tersi: dizi rastgele erişimde iyi, bağlı liste uçlarda dinamiklikte iyidir. ```{python} #| label: fig-linked-list #| fig-cap: "Bağlı liste: her düğüm bir **(item | next)** kutusudur; sıra yalnız `next` işaretçileriyle örtük tutulur (bellekte düğümler dağınık olabilir). `head` ilk, `tail` son düğüme işaret eder ($\\S 8$ augmentation) → **insert_first** ve **insert_last** $O(1)$. Rastgele erişim zayıftır: `get_at(2)` head'den `next` zincirini $i$ kez takip eder — burada $3$ düğüm ziyareti (amber zincir) → $O(i)$. Son düğümün `next`'i $\\varnothing$ (None)." #| fig-width: 9 #| fig-height: 3.4 # Deterministik bağlı liste: a,b,c,d (insert_last ile sıra korunur, head/tail augment) ll = LinkedList() for item in ("a", "b", "c", "d"): ll.insert_last(item) items = ll.to_list() # ['a', 'b', 'c', 'd'] ACCESS_I = 2 # get_at(2): head'den 3 düğüm ziyaret → O(i) value, steps = ll.get_at(ACCESS_I) # ('c', 3) — steps == i + 1 fig, ax = plt.subplots(figsize=(9, 3.4)) # (item | next) düğümleri + head/tail + next okları + get_at(i) i-adım zinciri (amber) draw_linked_list(ax, items=items, access_i=ACCESS_I) # insert_first O(1): yeni baş düğüm, head güncelle → sabit zaman (zincir gezme yok) ax.text( -0.45, 1.55, "insert_first(x): yeni baş düğüm, head güncelle → O(1)", ha="left", va="center", fontsize=9.5, color=COL_PRIMARY, weight="bold", ) fig.suptitle( "Bağlı liste: (item | next) düğümleri + head/tail · get_at(i) i-adım zinciri", color=COL_TEXT, fontsize=12, y=1.02, ) plt.tight_layout() plt.show() ``` ## Veri Yapısı Zenginleştirme (Augmentation) {#sec-augmentation-d02} Küçük bir bulmaca: bağlı listede get_last'ı sabit zamanda nasıl çözeriz? Cevap: son öğeye bir **işaretçi** sakla (genelde **tail** denir). Bu, **veri yapısı zenginleştirmedir** (augmentation): yapıya ekstra bilgi ekleyip onu her zaman güncel tutmak. > *"data structure augmentation, where we add some extra information to the data structure"* — Demaine, 33:09 tail işaretçisiyle get_last ve insert_last $O(1)$ olur. delete_last ise daha zordur — onun için **çift bağlı liste** (doubly linked list, her düğümde bir de prev işaretçisi) gerekir. Zenginleştirmenin bedeli: yapıyı değiştiren her işlemde ekstra bilgiyi (örneğin tail) güncel tutmak zorundasın. ::: {.callout-tip title="Builder Notu — Augmentation ve Veritabanı İndeksleri"} Augmentation — "yapıya ekstra bilgi ekle, onu güncel tut, bir sorguyu hızlandır" — sistem mühendisliğinin en yaygın takasıdır: - **İleriye → veritabanı indeksleri:** Bir tabloya B-ağacı veya hash indeksi eklemek tam olarak augmentation'dır: aramayı $O(n)$ tam-taramadan $O(\log n)$'e (veya $O(1)$'e) indirir. Bedeli, tail'i güncel tutmak gibi — her `INSERT`/`UPDATE`/`DELETE` indeksi de güncellemek zorundadır (yazma daha pahalı, okuma çok daha ucuz). - **Sezgi → skip-list / B-tree:** tail ve prev işaretçileri, daha zengin augmentation'ların (skip-list'in atlama katmanları, B-ağacının iç düğüm anahtarları) ilk basamağıdır; hepsi "ekstra yapısal bilgi sakla, navigasyonu hızlandır" fikrinin türevidir. - **İleriye → ML feature store:** Önceden hesaplanmış (materialized) öznitelik tabloları, çıkarım anında yeniden hesaplamayı önlemek için tutulan augmentation'lardır — güncel tutma maliyeti (cache invalidation), tail güncellemesiyle aynı disiplini ister. ::: ## Statik Dizi mi, Bağlı Liste mi? {#sec-statik-mi-bagli-mi} İki veri yapısı **birbirini tamamlar**: - **Statik dizi:** get_at/set_at sabit zaman $O(1)$ (rastgele erişimde mükemmel), ama insert/delete her yerde $\Theta(n)$ (kaydırma veya yeniden ayırma + kopyalama gerekir). Sona ekleme bile zordur, çünkü ayrılan dizi büyütülemez — yeni bir dizi ayırıp her şeyi kopyalamak $\Theta(n)$'dir. - **Bağlı liste:** insert/delete_first sabit zaman $O(1)$ (uçlarda dinamiklikte iyi), ama get_at/set_at $O(i)$, en kötü $\Theta(n)$ (rastgele erişimde kötü). Demaine'in deyişiyle: diziler statik rastgele erişim için, bağlı listeler dinamik uç işlemleri için iyidir. Hiçbiri *her ikisini* birden iyi yapmaz. Hedefimiz, ikisinin de güçlü yanlarını birleştiren bir yapı. Bu tercihin gerçek donanımdaki bir başka boyutu da **bellek yerelliğidir** (@fig-memory-locality): aynı asimptotik tarama, ardışık dizide bağlı listeden çok daha hızlı koşar. ```{python} #| label: fig-memory-locality #| fig-cap: "Dizilerin taramada bağlı listeyi yenmesinin donanım sebebi: **bellek yerelliği**. Üstte statik dizi tek **ardışık blok** — öğeler bitişik adreslerde, bir önbellek satırı ($O(1)$ erişim, amber); sıralı tarama tek atlamayla ilerler, yüksek yerellik. Altta bağlı liste düğümleri bellekte **dağınık**; her `next` işaretçisi uzak bir adrese sıçrar (amber oklar), her erişim önbellek-ıskası (cache-miss) riski taşır. Aynı asimptotik $\\Theta(n)$ tarama, gerçek donanımda dizide çok daha hızlıdır — düşük yerellik bağlı listeyi cezalandırır." #| fig-width: 9 #| fig-height: 5.4 # fig-memory-locality: ardışık dizi (cache-dostu) vs dağınık liste (cache-miss). # draw_memory_locality deterministik sabit koordinatlar kullanır (sayılar birebir). fig, ax = plt.subplots(figsize=(9, 5.4)) draw_memory_locality(ax) ax.set_title( "Bellek yerelliği: ardışık dizi (cache-dostu) vs dağınık liste (cache-miss)", color=COL_TEXT, fontsize=12.5, pad=12, ) # Donanım gerekçesi dipnotu — dizinin tarama avantajı ax.text( 0.5, -0.02, "Aynı sayıda öğe: dizi tek ardışık blok (önbellek satırı), liste her next'te uzak bir adrese sıçrar", transform=ax.transAxes, ha="center", va="top", fontsize=9.5, color=COL_AMBER_700, ) plt.tight_layout() plt.show() ``` ## Dinamik Dizi (Dynamic Array) {#sec-dinamik-dizi} Çözüm **dinamik dizidir** — ve bu tam olarak Python'ın `list` dediği şeydir. > *"another way to describe what these introductory lectures are about is telling you about how Python is implemented."* — Demaine, 34:19 Fikir, statik dizinin katı kuralını **gevşetmektir**: ayrılan dizinin boyutu tam $n$ olmak zorunda değil; *kabaca* $n$ olsun. Algoritma dilinde "kabaca" = sabit çarpanları at. Diziyi boyutu **$\Theta(n)$** ve $n$'den büyük-eşit tutarız (örneğin $2n$). > *"the size of the array is theta n-- probably also greater than or equal to n."* — Demaine, 36:11 Yapı, bir dizi artı bir **length** (gerçek öğe sayısı) tutar. length, dizinin gerçek boyutu **size**'dan küçük-eşittir; ilk length konum veriyi, kalanı boş yeri temsil eder. insert_last basittir: `a[length] = x`, sonra length'i artır → $O(1)$. Ama bir sorun var: length = size olduğunda boş yer kalmaz. İşte o zaman diziyi büyütmek gerekir — sonraki bölümün konusu. ## Dizi Büyütme ve Geometrik Seri {#sec-dizi-buyutme} length = size olduğunda diziyi büyütmek gerekir. Ne kadar? İki doğal seçenek: - **Sabit ekleme (size + 5):** Kötü. Her 5 adımda bir lineer yeniden ayırma → işlem başına hâlâ lineer zaman. Statik dizinin "her seferinde yeniden ayır" sorununu sadece sabit çarpanla iyileştirir. - **Sabit çarpan (2 × size):** İyi. Diziyi her dolduğunda **iki katına** çıkar. **Çalışılan Örnek — Doubling'in Toplam Maliyeti** Boş bir diziden başlayıp $n$ kez insert_last yapalım (size = 1 başlasın). Yeniden boyutlandırmalar $n = 1, 2, 4, 8, 16, \ldots$ değerlerinde, yani **2'nin kuvvetlerinde** olur (çünkü ikiye katlıyoruz; @fig-dynamic-resize). Her resize, ayırma + kopyalama nedeniyle lineerdir. Toplam resize maliyeti: $$1 + 2 + 4 + 8 + \cdots + (\approx n) = \sum_i 2^i \quad (i = 0 \text{'dan} \approx \log_2 n \text{'e})$$ Bu bir **geometrik seridir**. Kimliği: $1 + 2 + 4 + \cdots + 2^k = 2^{k+1} - 1$. Geometrik seriler **son terim tarafından domine edilir**: > *"Geometric series are dominated by the last term"* — Demaine, 45:46 Son terim $2^{\log_2 n} = n$ olduğundan, toplam $\Theta(n)$'dir. Yani $n$ işlem için toplam yeniden boyutlandırma maliyeti yalnızca $\Theta(n)$ — işlem başına "kabaca sabit". ```{python} #| label: fig-dynamic-resize #| fig-cap: "Dinamik dizi büyütme (doubling): dizi dolarken ayrılan boyut **1 → 2 → 4 → 8** olarak ikiye katlanır. Her satır o anki diziyi gösterir — dolu amber hücreler **length** (gerçek öğe sayısı), boş slate hücreler **size − length** (ayrılan ama henüz kullanılmayan yer). Soldaki amber oklar her resize'da **ayır + kopyala** adımını gösterir: `length == size` olunca yeni (iki kat) dizi ayrılır ve eski öğeler taşınır ($\\Theta(\\text{length})$). Toplam ayrılan + kopyalanan iş bir geometrik seridir: $1 + 2 + 4 + 8 = 15 = 2^{4} - 1$ — son terim toplamı domine eder, bu yüzden $n$ append toplam $\\Theta(n)$'dir ve `insert_last` amortize $O(1)$ olur." #| fig-width: 9 #| fig-height: 6.4 # DETERMİNİSTİK: sabit stages (1,2,4,8) + geometric_series(3); seed yok. draw_dynamic_resize # / geometric_series / COL_* / plt gizli setup hücresinden (inline _engine+_viz) gelir. fig, ax = plt.subplots(figsize=(9, 6.4)) fig.patch.set_facecolor(COL_WHITE) # Doubling satırları: size 1→2→4→8 (length=önceki size; ilk satır dolu) + kopya okları. draw_dynamic_resize(ax, stages=(1, 2, 4, 8)) # Geometrik seri annotasyonu (DETERMİNİSTİK): 1+2+4+8 = 15 = 2⁴−1 ≈ 2n (n=8). gs = geometric_series(3) # k=3 → [1, 2, 4, 8] terms = gs["terms"] total = gs["sum"] # 15 series_str = " + ".join(str(t) for t in terms) # "1 + 2 + 4 + 8" # Başlık + alt başlık: eksenin ÜSTÜNE (fig koordinatı) — veri satırlarıyla çakışmaz. fig.suptitle( "Dinamik dizi büyütme — ikiye-katlama (doubling)", color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985, ) fig.text( 0.5, 0.935, "length = dolu (amber) · size = ayrılan (boş hücre) · her resize: ayır + kopyala", ha="center", va="top", fontsize=9.5, color=COL_SLATE_500, style="italic", ) # Geometrik seri kapanışı: eksenin ALTINA, satırların altında (amber vurgu). fig.text( 0.5, 0.045, f"Toplam ayrılan + kopyalanan iş: {series_str} = {total} = $2^{{4}}-1 = \\Theta(n)$", ha="center", va="bottom", fontsize=11.5, color=COL_AMBER_700, weight="bold", ) plt.tight_layout(rect=(0, 0.06, 1, 0.92)) plt.show() ``` ::: {.callout-tip title="Builder Notu — İkiye-Katlama Her Yerde"} Demaine'in "dolunca iki katına çık" stratejisi, tek bir veri yapısının özelliği değil — ölçeklenen sistemlerin tekrar eden bir motifidir: - **İleriye → PyTorch `DataLoader` ve `torch.cat`:** Boyutu önceden bilinmeyen bir tampona (buffer) tensör biriktirirken, kapasitenin geometrik büyütülmesi (her `torch.cat` realloc'unda sabit çarpan) toplam kopya işini $\Theta(n)$'de tutar; sabit ekleme olsa $\Theta(n^2)$'ye patlardı. - **İleriye → exponential backoff:** Başarısız bir isteği yeniden denerken bekleme süresini ikiye katlamak (1s, 2s, 4s, 8s), aynı geometrik seri sezgisidir — toplam bekleme son terimle domine olur, sistem yükü sınırlı kalır. - **İleriye → batch-size / LR taraması:** Hiperparametre ararken batch boyutunu veya öğrenme oranını ikiye katlayarak (32, 64, 128, ...) geometrik bir ızgara taramak, lineer ızgaraya göre çok daha geniş bir aralığı logaritmik sayıda denemeyle kapsar — "son terim toplamı domine eder" disiplini. ::: ## Amortize Analiz (Amortized Analysis) {#sec-amortize} Bu "kabaca sabit" kavramı **amortizasyondur**. Tanım: bir işlem **$T(n)$ amortize zaman** alır, eğer *herhangi* $k$ işlem en fazla $k \cdot T(n)$ toplam zaman alıyorsa. > *"Amortized means a particular kind of averaging-- averaging over the sequence of operations."* — Demaine, 47:42 Doubling'de $n$ işlem toplam $\Theta(n)$ zaman aldığından, insert_last **sabit amortize** (constant amortized) zamandır. Sezgi: tek tek işlemler bazen pahalıdır (resize anında lineer), ama çoğu ucuzdur (sabit). Pahalı işlemin maliyetini, onu mümkün kılan tüm ucuz işlemlere "dağıtırız" — bu, işlem dizisi üzerinde ortalamadır (@fig-amortize). delete_last için resize gerekmez (length'i azalt, biter), o da sabit amortizedir. ```{python} #| label: fig-amortize #| fig-cap: "Amortize analiz (İMZA): bir dinamik diziye boş başlangıçtan $n=31$ kez `append`. **Sol:** her işlemin maliyeti — çoğu yalnız 1 (tek slot yazımı, slate çubuklar); `length == size` olduğunda ikiye-katlama tetiklenir ve o işlemin maliyeti o anki boyut kadar sıçrar (amber çubuklar, append #1, 2, 3, 5, 9, 17'de değerler $1, 2, 3, 5, 9, 17$ — yani o anki boyutu kopyalama + 1 slot yazımı; resize boyutları $1, 2, 4, 8, 16$ ($2^k$) olduğundan ilk hariç maliyet $2^k+1$'e sıçrar). **Sağ:** kümülatif ortalama (toplam maliyet / işlem sayısı, slate çizgi) her resize'da yukarı sıçrayıp ardından düşer ve sabit bir değere — tam olarak $62/31 = 2{,}00$ (amber kesik çizgi) — düzleşir. Nadiren pahalı resize'ların maliyeti tüm adımlara yayıldığı için `insert_last` **amortize $O(1)$**'dir; geometrik seri toplamı $\\sum_{i} 2^i = 2^{k+1}-1 \\approx 2n$ bu sabiti garanti eder." #| fig-width: 11 #| fig-height: 4.6 N = 31 trace = amortize_trace(N) fig, (ax_cost, ax_avg) = plt.subplots(1, 2, figsize=(11, 4.6)) draw_amortize(ax_cost, ax_avg, trace) fig.suptitle( "Amortize analiz: nadir pahalı resize'lar adımlara yayılır → ortalama sabit", color=COL_TEXT, fontsize=12.5, y=0.99, ) ax_cost.text( 0.97, 0.95, f"toplam maliyet = {trace['total']} ({N} append)", transform=ax_cost.transAxes, ha="right", va="top", fontsize=9, color=COL_PRIMARY, weight="bold", ) ax_avg.text( 0.97, 0.62, f"ortalama → {trace['average']:.2f} ≈ O(1)", transform=ax_avg.transAxes, ha="right", va="top", fontsize=9.5, color=COL_ACCENT, weight="bold", ) plt.tight_layout(rect=(0, 0, 1, 0.96)) plt.show() ``` ::: {.callout-tip title="Builder Notu — Amortize Düşünme ve Mini-batch/Checkpoint"} "Nadiren pahalı, çoğu zaman ucuz; maliyeti diziye yay" analizi, eğitim ve altyapı kodunun her yerinde aynı biçimde karşına çıkar: - **İleriye → checkpoint kaydetme:** Bir modeli her $N$ adımda bir diske yazmak pahalıdır (tüm ağırlıkları serialize et), ama bu maliyet aradaki $N$ ucuz eğitim adımına yayıldığında *adım başına* amortize maliyet ihmal edilebilir kalır — tam olarak resize'ın append'lere yayılması gibi. - **İleriye → gradient accumulation:** Birkaç mini-batch'in gradyanını biriktirip seyrek aralıklarla bir optimizer adımı atmak, pahalı `step()` çağrısının maliyetini birikim adımlarına amortize eder. - **İleriye → rehash ve GC:** Hash tablosu yük faktörü eşiği aşınca yeniden hash'leme ($\Theta(n)$) ve çöp toplama (garbage collection) duraklamaları, doubling resize'la birebir aynı amortize argümanına dayanır: nadir, pahalı, ama dizi boyunca sabit ortalama. ::: ## Üç Veri Yapısı — Karşılaştırma {#sec-karsilastirma-d02} Demaine dersi bu özet tabloyla kapatır ($\Theta$'lar atılmış, çalışma süreleri; @fig-cost-matrix): | İşlem | Statik Dizi | Bağlı Liste | Dinamik Dizi | |---|---|---|---| | get_at / set_at | $O(1)$ | $O(n)$ | $O(1)$ | | insert / delete_first | $O(n)$ | $O(1)$ | $O(n)$ | | insert / delete_last | $O(n)$ | $O(n)$ | $O(1)$ amortize | | insert / delete_at | $O(n)$ | $O(n)$ | $O(n)$ | Dinamik dizi, rastgele erişimde statik dizinin hızını ($O(1)$ get_at) ve sona eklemede neredeyse bağlı listenin esnekliğini ($O(1)$ amortize insert_last) birleştirir — ikisinin en iyisi. ```{python} #| label: fig-cost-matrix #| fig-cap: "Demaine'in kapanış maliyet matrisi: 4 işlem ailesi × 3 veri yapısı. Yeşilimsi hücreler $O(1)$ (en iyi, sabit zaman), amber hücreler $O(n)$ (yavaş, lineer), amber-çerçeveli açık hücre ise $O(1)$ amortize (neredeyse en iyi). Hiçbir sütun her satırda kazanmaz: **statik dizi** rastgele erişimde ($O(1)$ get_at/set_at) üstündür ama her ekleme/silme $O(n)$ kaydırma ister; **bağlı liste** uç işlemlerini ($O(1)$ insert/delete_first ve tail augmentation'la last) hızlandırır ama rastgele erişim $O(n)$'e düşer; **dinamik dizi** rastgele erişim $O(1)$'i sona ekleme $O(1)$ amortize ile birleştirip ikisinin en iyisini sunar — bu yüzden Python `list`'in temelidir. Veri yapısı seçimi, hangi işlemlerin sıcak yolda olduğuna bağlı bir takastır." #| fig-width: 11 #| fig-height: 5.2 # --- Deterministik maliyet matrisi (Demaine §13 kapanış tablosu) --- # cost_matrix() değerleri _engine'de DETERMİNİSTİK; tablo Notion §13 ile birebir. matrix = cost_matrix() fig, ax = plt.subplots(figsize=(11, 5.2)) draw_cost_matrix(ax, matrix) ax.set_title( "Veri yapısı seçimi = işlem profili: her sütun bir takas (Demaine §13)", color=COL_TEXT, fontsize=12.5, pad=16, ) # Renk lejantı (O(1) iyi / O(1) amortize / O(n)) — okuyucuya renk anahtarı COL_GOOD = "#cfe8da" legend_items = [ (COL_GOOD, "#3f7d5e", "O(1) — en iyi (sabit zaman)"), ("#fef3c7", COL_ACCENT, "O(1) amortize — neredeyse en iyi"), ("#fcd34d", "#b45309", "O(n) — yavaş (lineer)"), ] x_leg = 0.06 for i, (fc, ec, label) in enumerate(legend_items): y_leg = -0.13 - i * 0.06 ax.add_patch(plt.Rectangle( (x_leg, y_leg), 0.035, 0.04, transform=ax.transAxes, facecolor=fc, edgecolor=ec, linewidth=1.8, clip_on=False)) ax.text(x_leg + 0.05, y_leg + 0.02, label, transform=ax.transAxes, ha="left", va="center", fontsize=9.5, color=COL_TEXT) plt.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — Veri Yapısı Seçimi = Tensor Layout"} Maliyet matrisinin verdiği ders — "her yapı bir takas; sıcak yoldaki işleme göre seç" — derin öğrenmede **tensör bellek düzeni** seçiminde birebir tekrar eder: - **İleriye → contiguous tensor vs Python list:** Bir batch'i Python `list`'inde tutmak (dağınık nesneler, bağlı liste sezgisi) ile tek bir contiguous tensörde tutmak (ardışık dizi sezgisi) arasındaki fark, tam olarak bu matristeki rastgele erişim/tarama takasıdır — vektörize işlemler ardışık belleği ister. - **İleriye → `.contiguous()` çağrısı:** `transpose`/`permute` sonrası bir tensör mantıksal olarak doğru ama bellekte dağınıktır; `.contiguous()` onu yeniden ardışık düzene kopyalar ($\Theta(n)$, tıpkı resize kopyası gibi) — çünkü birçok CUDA çekirdeği ardışık düzen olmadan çalışmaz veya yavaşlar. - **İleriye → GPU bellek yerelliği:** @fig-memory-locality'nin cache argümanı GPU'da daha da keskindir; coalesced (bitişik) erişim tam bant genişliği kullanır, dağınık erişim çekirdeği bellek-bağlı yapar. "Hangi işlem sıcak yolda?" sorusu, layout kararıyla doğrudan performansa çevrilir. ::: ## Bu Dersin Özeti {#sec-ozet-d02} 1. **Arayüz** *ne* yapılacağını (işlemler), **veri yapısı** *nasıl* yapılacağını (gerçekleştirim) söyler. 2. İki temel arayüz: **küme** (değere/anahtara göre) ve **dizi** (sıraya göre). 3. **Statik dizi**: ardışık bellek; get_at/set_at $O(1)$, build/iter $\Theta(n)$. 4. **Bağlı liste**: düğüm + next işaretçisi; insert/delete_first $O(1)$, erişim $O(i)$. 5. **Dinamik dizi** (Python `list`): boyut $\Theta(n)$; ikiye-katlama ile insert_last amortize $O(1)$. 6. **Geometrik seri** son terimle domine olur: $1 + 2 + \cdots + 2^k = \Theta(2^k) = \Theta(n)$. 7. **Amortize analiz**: $k$ işlem en fazla $k \cdot T(n)$ zaman alır; nadiren pahalı, ortalama ucuz. ::: {.callout-important title="Tek Bir Cümle"} Python `list`'in her "ucuz" append'i, arada bir yapılan pahalı ikiye-katlamanın işlem dizisine **amortize** edilmiş hâlidir — sihir değil, geometrik seri. ::: ## Kontrol Soruları {#sec-sorular-d02} ::: {.callout-note collapse="true" title="Soru 1: Arayüz (interface) ile veri yapısı (data structure) arasındaki fark nedir?"} **Cevap:** **Arayüz**, *ne* yapılacağını söyler: hangi veriyi saklayabilirsin, hangi işlemler desteklenir ve bu işlemler ne anlama gelir (bir spesifikasyon). **Veri yapısı**, *nasıl* yapılacağını söyler: verinin somut gösterimi ve işlemleri destekleyen algoritmalar. Aynı arayüz (örneğin "dizi") birden çok veri yapısıyla (statik dizi, bağlı liste, dinamik dizi) çözülebilir; her birinin farklı çalışma süreleri vardır. ::: ::: {.callout-note collapse="true" title="Soru 2: Çok sık get_at ama nadiren ekleme gereken bir uygulamada hangi veri yapısı uygundur? Tersine, sürekli baştan ekleme gerekiyorsa?"} **Cevap:** Sık rastgele erişim için **statik dizi** veya **dinamik dizi** uygundur (get_at $O(1)$). Sürekli baştan ekleme için **bağlı liste** uygundur (insert_first $O(1)$; dizilerde $O(n)$ çünkü kaydırma gerekir). Eğer hem sık get_at hem sık insert_first gerekiyorsa, tek bir basit yapı ikisini birden $O(1)$ yapamaz — bu ileri veri yapılarının (örneğin dengeli ağaçlar, Ders 6-7) motivasyonudur. ::: ::: {.callout-note collapse="true" title="Soru 3: Dinamik dizi dolduğunda neden boyutu size + 1 değil de 2 × size yapılır?"} **Cevap:** size + 1 (ya da sabit ekleme, örn. +5), her birkaç eklemede bir lineer yeniden-ayırma gerektirir → işlem başına hâlâ **lineer** zaman. 2 × size ise yeniden boyutlandırmaları 2'nin kuvvetlerinde seyrekleştirir; $n$ eklemenin toplam resize maliyeti geometrik seri olduğu için $\Theta(n)$'dir → işlem başına **sabit amortize**. Sabit çarpanla büyütme, amortize sabit zamanın anahtarıdır. ::: ::: {.callout-note collapse="true" title="Soru 4: Python'da list.append() amortize O(1) ne demektir? Tek bir append neden bazen yavaş olabilir?"} **Cevap:** "Amortize $O(1)$", *herhangi* $k$ append'in toplamda en fazla $k \cdot O(1) = O(k)$ zaman aldığı anlamına gelir — işlem başına ortalama sabit. Ama tek bir append, dizi tam dolduğu anda denk gelirse, yeni (iki kat) dizi ayırıp tüm öğeleri kopyalar → o tek işlem $O(n)$. Bu nadir pahalı işlemin maliyeti, onu izleyen birçok ucuz append'e dağıtılır; dolayısıyla *ortalama* sabit kalır. ::: ## Egzersizler {#sec-egzersizler-d02} **Egzersiz 1.** Statik dizi arayüzünün beş işlemini (build, length, iter, get_at, set_at) listele ve her birinin statik dizi gerçekleştiriminde çalışma süresini yaz. Hangileri $\Theta(n)$, hangileri $O(1)$? **Egzersiz 2.** Bağlı listede insert_last'ı $O(1)$ yapmak için hangi zenginleştirme (augmentation) gerekir? Aynı zenginleştirmeyle delete_last neden hâlâ zordur ve bunu çözmek için ne gerekir? **Egzersiz 3.** Dinamik dizide $n$ öğe ekleyip sonra hepsini delete_last ile silersen, dizi boyutu hâlâ $\Theta(n)$ kalır (oysa $n = 0$). Bu bellek israfını önlemek için "küçültme" (shrinking) kuralını tasarla. (İpucu: dizi ¼ dolduğunda yarıya indir — neden ⅓ veya ½ değil?) **Egzersiz 4.** Python'da bir listeye $n$ kez append yaparken iç kapasitenin ne zaman büyüdüğünü gözlemle: ```python import sys lst = [] prev = -1 for i in range(64): cap = sys.getsizeof(lst) if cap != prev: print("uzunluk", len(lst), "-> kapasite baytlari", cap) prev = cap lst.append(i) ``` Kapasite hangi uzunluklarda zıplıyor? Bu, ikiye-katlama (doubling) sezgisini doğruluyor mu? **Egzersiz 5.** Küme (set) arayüzü, dizi (sequence) arayüzünden nasıl ayrılır? Öğeleri *değerine/anahtarına* göre aramak (sıraya göre değil), neden farklı bir veri yapısı gerektirir? Ders 3-4'e (sıralama ve hashing) bir köprü kur. ## Sonraki Ders İçin Hazırlık {#sec-sonraki-d02} **Ders 3 (L3): Kümeler ve Sıralama** Justin Solomon ile **küme (set)** arayüzüne ve onu çözmenin ilk adımı olan **sıralamaya** (insertion, selection, merge sort) geçiyoruz. Bu derste değindiğimiz "değere göre arama" sorusu orada merkeze oturur. (Not: ders akışında araya **Problem Oturumu 1** girer — bu dersin kavramlarını pekiştiren problemler.) ::: {.callout-warning title="Ders 3 Öncesi Yapılacak"} - Bu dersin egzersizlerini, özellikle Egzersiz 4'ü (Python kapasite gözlemi) çöz. - Üç veri yapısı tablosunu (@fig-cost-matrix) ezberden çizebilecek hâle gel. - Ana cümleyi tekrar oku: *"Aynı işi farklı veri yapıları farklı maliyetlerle yapar."* ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d02} | Kavram | Tanım | Sayfada | |---|---|---| | Arayüz vs veri yapısı | Ne (spesifikasyon) vs nasıl (gerçekleştirim) | Böl. 1 | | Dizi (sequence) | Öğeleri belirli bir sırada tutan arayüz | Böl. 2-3 | | Statik dizi | Ardışık bellek; get_at/set_at $O(1)$ | Böl. 4 | | Bellek ayırma modeli | $n$ boyutlu dizi $\Theta(n)$ zamanda ayrılır | Böl. 5 | | Word boyutu | $w \geq \log n$ ($n$ öğeyi adresleyebilmek için) | Böl. 5 | | Bağlı liste | Düğüm + next; insert/delete_first $O(1)$ | Böl. 7 | | Augmentation | Ekstra bilgi (tail) ile $O(1)$ get_last | Böl. 8 | | Dinamik dizi | Python list; boyut $\Theta(n)$, ikiye-katlama | Böl. 10 | | Geometrik seri | $1+2+\cdots+2^k = \Theta(2^k) = \Theta(n)$ | Böl. 11 | | Amortize analiz | $k$ işlem en fazla $k \cdot T(n)$ zaman | Böl. 12 | ## Builder ve OMSCS Bağlantıları {#sec-ml-baglantilar-d02} ::: {.callout-tip title="6 köprü"} Bu ders, ileri algoritma ve sistem mühendisliğinin temel dilini kurar — köprülerin özeti: 1. **Amortize analiz** → altyapı: log-structured storage, hash tablosu rehashing, garbage collection — "nadiren pahalı, çoğu zaman ucuz" her yerde aynı analiz. 2. **Dinamik dizi** → Python `list`, C++ `vector`, Java `ArrayList`'in iç mekanizması; kapasite büyütme stratejisi. 3. **Arayüz / veri yapısı ayrımı** → API tasarımı: aynı sözleşme (interface), değişebilir backend (implementation). 4. **word RAM + işaretçiler** → bellek modeli ve cache yerelliği; dizi (ardışık) ile bağlı liste (dağınık) arasındaki gerçek performans farkı. 5. **Augmentation** → veritabanı indeksleri: ekstra bir yapı (B-ağacı, hash) ekleyip sorguyu hızlandırma — aynı augmentation fikri. 6. **Geometrik seri sezgisi** → ikiye-katlama/yarıya-indirme stratejileri: connection pool, buffer büyütme, exponential backoff. ::: --- ::: {.callout-important title="Tek bir şey alıp gideceksen"} Aynı işi farklı veri yapıları farklı maliyetlerle yapar; mühendislik, "hangi işlem ne sıklıkta çağrılıyor?" sorusuna göre doğru yapıyı seçmektir. Python `list`'in zarafeti, bu seçimi amortize analizle senin için çoktan çözmüş olmasıdır. :::

İşlem	Statik Dizi	Bağlı Liste	Dinamik Dizi
get_at / set_at	\(O(1)\)	\(O(n)\)	\(O(1)\)
insert / delete_first	\(O(n)\)	\(O(1)\)	\(O(n)\)
insert / delete_last	\(O(n)\)	\(O(n)\)	\(O(1)\) amortize
insert / delete_at	\(O(n)\)	\(O(n)\)	\(O(n)\)