Kısım I · Makine · Bölüm 11

Veri Yapıları ve Algoritmalar

Düşünme araçları (Data structures and algorithms)

1. Kat 10Bizim hukuk uygulamamızSorular, puan, seri ve sıralama: üstteki amaç.
2. Kat 9Tarayıcı ve webHTML, CSS, JavaScript: Bölüm 20, 23–26.
3. Kat 8Ağ ve internetMakineler arasında iletişim: Bölüm 19–20.
4. Kat 7İşletim sistemiKaynaklar, süreçler, bellek ve dosyalar: Bölüm 13–18.
5. Kat 6Gömülü yazılım ve açılışİlk koddan işletim sistemine geçiş: Bölüm 12.
6. Kat 5Diller, derleyici ve veri düzeniC ile tarif, adres ve algoritma: Bölüm 9–11.
7. Kat 4Makine dili ve assemblyBitlerden oluşan işlemci komutları: Bölüm 7.
8. Kat 3İşlemci ve bellekKomutları yürüten donanım ve RAM: Bölüm 6, 8.

Bu bölümün sonunda “hızlı algoritma” sözünün neyi ölçtüğünü, sıralılığın aramaya ne kazandırdığını, işaretçilerin nasıl veri yapısına dönüştüğünü ve bir agent’ın veri düzeni seçimini hangi sorularla sınayacağını anlatabileceksin.

11.1 Verimlilik ölçüsü: büyük O gösterimi

Bölüm 10'da aynı değerleri yan yana hücrelerde tutabildiğini ve işaretçilerle ayrı yerlere bağlayabildiğini gördün. Şimdi başka bir soru soralım: soru bankasında belirli bir soruyu bulmak için kaç hücreye bakman gerekiyor? İşlemci bütün bu yöntemlerde yine Bölüm 6'daki komutları yürütür. Ama seçtiğin yöntem, kaç komut gerektiğini değiştirir. Veri yapısı (data structure) verinin bellekte örgütlenişidir; algoritma ise bu örgütleniş üzerinde izlediğin adımlardır. İkisini birlikte düşünmek gerekir.¹²

Bir programı kronometreyle ölçmek yararlıdır, fakat iki farklı makinede farklı süre görürsün. CS50 önce makineyi değil, işin büyümesini karşılaştırır: girdi büyüdükçe yapılacak iş nasıl artıyor? Buna zaman karmaşıklığı (time complexity) diyebiliriz. Girdi büyüklüğünü n ile gösterelim. Bizim örneğimizde n, aranan soru bankasındaki soru sayısı olsun. Bir dizi hücresine erişmeyi ve iki küçük tam sayıyı karşılaştırmayı birer temel işlem saydığımız basitleştirilmiş bir model kuruyoruz.¹

O harfi neyi söylüyor?

Büyük O gösterimi (big-O notation), iş miktarının büyük girdilerdeki büyümesine bir üst sınır tarif eder. Sabit çarpanları ve baskın olmayan terimleri gizler: 3n + 7 temel işlem de n temel işlem de O(n) ile sınırlıdır. Bu, iki programın eşit sürede çalıştığı anlamına gelmez. Yalnızca ikisinin de girdi büyüklüğüyle doğrusal büyüdüğünü söyler. Kitapta arama için O(n) dediğimizde, ayrıca belirtilmedikçe en kötü durumdaki sıkı büyüme sınıfını kastedeceğiz; O işaretinin kendisi matematiksel olarak yalnızca üst sınırdır.¹

O(1)'deki 1, “tek makine komutu” veya “sıfır saniye” değildir. Dizi adresi hesaplamak, değeri getirmek, belki önbelleği kaçırmak gibi işler hâlâ vardır. Sabitlik, n'ye göredir. O(log n)'de logaritma (logarithm) burada “kaç defa ikiye bölebilirim?” sorusunun kısa adıdır. İkiye bölme modelinde 1.024 adayı 10 kez, 1.048.576 adayı 20 kez yarılarsın. Bunlar yarılama sayılarıdır; belirli bir ikili arama kodunun yaptığı karşılaştırmaların tam sayısı ayrıca hesaplanır.¹

Büyümeyi bir cetvelle görmek

Aşağıdaki tablo gerçek bilgisayarda ölçülen süre değil, dört farklı büyüme fonksiyonunun Python ile doğrulanmış değerleridir. Özellikle n² sütununa bak: girdi iki katına çıkınca iş dört katına çıkar. log₂ n sütununda aynı artış yalnızca bir birimdir.

11.2 Arama: doğrusal arama ve ikili arama

Doğrusal arama (linear search), öğelere sırayla bakıp hedefle karşılaştırmaktır. Liste sırasız olabilir. Bir eşleşme bulununca durur; sona kadar eşleşme yoksa “bulunamadı” dersin. Neden var? Çünkü veri hakkında sıralılık gibi ek bir sözün yokken genel ve basit bir yöntem gerekir. Bunun karşılığında en kötü durumda bütün öğeleri okursun: O(n).¹

int bul(const int sayilar[], int n, int hedef)
{
    for (int i = 0; i < n; i++)
        if (sayilar[i] == hedef) return i;
    return -1;
}

Bu, Bölüm 9'un yapı taşlarıyla yazılmış bir fonksiyondur. İlk satır bir tam sayı dizisi, uzunluk ve hedef alır; const burada elemanları bu yol üzerinden değiştirmeyeceğimiz sözü verir. for geçerli indeksleri dolaşır. if eşleşirse indeks döndürür. Hiç eşleşme yoksa -1 döner; geçerli bir indeks olmadığı için onu “yok” işareti olarak seçtik. Kod, n'nin negatif olmadığını ve dizinin en az n eleman taşıdığını varsayar; bu bir tam sayı kimliği arama örneğidir, soru metni arama motoru değil.¹

Örneğin [42, 7, 91, 18, 63, 25, 80, 12] dizisinde 63 ararken 42, 7, 91, 18 ve 63 okunur: beş eşitlik kontrolü. 99 yoksa sekiz kontrol gerekir. Birinci eleman olan 42 içinse bir kontrol yeter. Fonksiyonun aynı kalıp veriye göre farklı miktarda iş yapması artık somutlaşmış oldu.

Sıralılık bize ne kazandırır?

İkili arama (binary search), sıralı verinin ortasına bakar. Ortadaki sayı hedeften küçükse sol yarının tamamını eler; büyükse sağ yarıyı eler. Eşitse durur. Elenen yarıya tek tek bakmak gerekmez, çünkü sıralılık onların da hedef olamayacağını garanti eder. Bölüm 1.2'deki telefon rehberi şimdi sayısal bir diziye dönüştü.¹

Sıralı dizi: [7, 12, 18, 25, 42, 63, 80, 91]
Hedef: 63

Aday indeksler 0..7 → orta indeks 3, değer 25 → sağa git
Aday indeksler 4..7 → orta indeks 5, değer 63 → bulundu

Bu iz, ortayı aşağı yuvarlayan ve iki ucu dahil tutan bir algoritmanın izidir; Python ile denetlendi. Bir “adım”da orta değerle karşılaştırıp hangi yöne gideceğine karar veriyoruz; C'de bunun birden çok karşılaştırma veya komuta açılabileceğini unutma. Böyle bir dizide n büyürken orta öğeye bakış sayısı O(log n) olur. Yöntem doğru çalışmak için kullanılan karşılaştırma kuralına göre sıralılık ve ortadaki elemana ucuz erişim ister.¹

11.3 Sıralama: seçmeli, kabarcık, birleştirmeli

Sıralama (sorting), aynı öğeleri belirli bir karşılaştırma kuralıyla yeniden dizmektir. Burada küçükten büyüğe tam sayılar kullanacağız. Leaderboard'da kural ters olabilir: büyük puan önce gelir. İşlemci açısından sihirli “sırala” anlayışı yoktur; karşılaştırma, yer değiştirme ve tekrar vardır. CS50 üç yöntemi bu adımlar üzerinden karşılaştırır.¹

Seçmeli sıralama: her turda sıradakini seç

Seçmeli sıralama (selection sort) kalan bölümdeki en küçük değeri bulur, kalan bölümün başına taşır ve o yeri tamamlanmış sayar. [40, 10, 30, 20] için önce 10 seçilir ve 40 ile yer değiştirir: [10, 40, 30, 20]. Sonra kalanların en küçüğü 20 başa alınır: [10, 20, 30, 40]. Sonraki turlar sonuç zaten düzgün olsa bile bunu karşılaştırarak belirler.¹

İlk turda n−1, sonra n−2, en son bir karşılaştırma gerekir. Toplam n(n−1)/2 karşılaştırmadır. Dört öğede 6, 1.000 öğede 499.500 karşılaştırma eder; bu değerler Python ile hesaplandı. Baskın büyüme O(n²)'dir. Bu basit gerçekleme girdinin zaten sıralı olduğunu bir bakışta anlayamaz: her turda kalanların en küçüğünü yeniden arar.¹

Kabarcık sıralama: yalnızca komşuları düzelt

Kabarcık sıralama (bubble sort), yan yana iki değer yanlış sıradaysa onları değiştirir. Soldan sağa bir tam geçişte en büyük değer sağ uca taşınır. Aynı dört öğede ilk geçiş şöyledir: [40,10,30,20] → [10,40,30,20] → [10,30,40,20] → [10,30,20,40]. En sağdaki 40 artık yerindedir; kalan kısmı aynı biçimde düzeltirsin.¹

En kötü durumda yine O(n²) iş yapar. Fakat bir geçişte hiç yer değiştirme olmadığını takip eden sürüm, “dizi zaten sıralı” diyerek durabilir. Bu sürümde sıralı girdide tek geçiş, yani doğrusal miktarda iş yeter. Buradaki kazanç yöntemin adından değil, erken durma denetiminden gelir. Seçmeli sıralamayla kabarcık sıralamayı yalnızca “ikisi de O(n²)” diyerek eşitlemek bu önemli farkı kaybettirir.¹

Birleştirmeli sıralama: küçük sıraları birleştir

Birleştirmeli sıralama (merge sort), veriyi iki parçaya böler, her parçayı sıralar ve iki sıralı parçayı birleştirir. “Her parçayı sıralar” işini aynı yöntemle tekrarlar; tek öğeye varınca sıralanacak bir şey kalmaz. Bu kendine dönme fikrini hemen sonraki alt bölümde özyineleme adıyla açacağız.¹

[40, 10, 30, 20]
       böl
[40, 10]        [30, 20]
[40] [10]       [30] [20]
       birleştir
[10, 40]        [20, 30]
[10, 20, 30, 40]

İki sıralı parçayı birleştirirken her parçanın ilk kalan öğesine bakarsın. Küçük olanı çıktıya alır, yalnızca o parçanın konumunu ilerletirsin. Diğer öğelerle yeniden baştan kıyaslamak gerekmez; her parçanın kendi içinde sıralı olduğunu biliyorsun. [10,40] ile [20,30] birleşirken önce 10, sonra 20, sonra 30 alınır; solda kalan 40 sona eklenir.¹

Bölme düzeylerinin sayısı yaklaşık log₂ n; her düzeyde toplam n öğe üzerinde birleştirme işi vardır. Böylece yeni bir büyüme sınıfına ulaştık: O(n log n). Bu, O(log n) aramayla aynı şey değildir: burada bütün öğeleri sıralamak zorundasın. n=1.024 için n log₂ n = 10.240; bu bir büyüme cetveli değeridir, tam karşılaştırma sayısı değildir. Standart dizi üzerinde birleştirme gerçeklemelerinde ayrıca geçici çıktı alanı gerekir; zaman kazancının yanında bellek maliyeti de düşünülür.¹⁵

11.4 Özyineleme: aynı işi daha küçük girdide istemek

Özyineleme (recursion), bir fonksiyonun işi kendi daha küçük örneklerine ayırıp kendisini çağırmasıdır. Kendi adını kullanmak tek başına yeterli değildir. Duracağı bir taban durumu (base case) ve her çağrıyı o duruma yaklaştıran bir küçülme gerekir. Aksi halde fonksiyon çağrıları birikir ve Bölüm 10.4'teki sınırlı yığın sorununa varabilirsin.¹²

int toplam(int n)
{
    if (n <= 0) return 0;
    return n + toplam(n - 1);
}

Bu örneğin girdisini küçük, negatif olmayan tam sayılarla sınırlıyoruz; C'nin tam sayı sınırları ve yığın sınırları ortadan kalkmış değildir. İlk satır fonksiyonu tanımlar. n <= 0 taban durumudur ve yeni çağrı yapmadan döner. Son satır bir küçük girdinin cevabını ister, onun üzerine n'yi ekler. toplam(4) için bekleyen işler 4 + toplam(3), 3 + toplam(2), 2 + toplam(1), 1 + toplam(0) biçiminde açılır; dönüşte 0, 1, 3, 6, 10 sonuçları oluşur. Bu iz Python ile, fonksiyonun sonucu da C ile denetlendi.

Çağıran fonksiyon bu sırada yok olmaz: alt çağrının sonucunu bekler. Bölüm 10'daki fonksiyon çerçevesini şimdi bunun için kullanıyoruz. toplam(4) çerçevesi “gelen cevaba 4 ekle” işini saklar; daha derindeki çerçeve kendi n değeriyle başka bir iş saklar. Aynı kaynak satırı, farklı çağrılarda farklı yerel değerlerle çalışır. İşte özyineleme “bilgisayar aynı satıra bakıp karışmıyor mu?” sorusunun cevabıdır.²

Özyineleme kendi başına hızlandırıcı değildir. Bu toplamı bir döngüyle de O(n) işte yapabilirsin; özyinelemeli sürüm ayrıca bekleyen çağrılar taşır. Buna karşılık ikiye ayrılan bir sıralama veya dalları olan bir ağaç, özyinelemeyle doğal biçimde tarif edilebilir. Seçim, problem yapısını daha açık anlatmak içindir; her özyinelemeyi zorla döngüye, her döngüyü zorla özyinelemeye çevirmek hedef değil.¹²

11.5 Veri yapıları: bağlı liste, ağaç, karma tablo, kuyruk ve yığın

Bağlı liste: komşuluk yerine bağlantı

Bölüm 10.4 bağlı listenin ilk örneğini öbek üzerinden gösterdi. Şimdi işaretçiyi yeniden öğretmek yerine, bu düzenin erişim ve ekleme maliyetine bakacağız.

Bağlı liste (linked list), her parçasında bir değer ve sonraki parçanın adresi bulunan düzendir. Her parçaya düğüm (node) denir. Düğümler bellekte yan yana durmak zorunda değildir; Bölüm 10'daki işaretçiler onları bağlar. Son düğümün sonraki işaretçisi NULL'dır. Listenin başının adresini tutarsan bütün zincire erişebilirsin.²

baş → [42 | sonraki] → [7 | sonraki] → [91 | NULL]

Neden var? Sabit boyutlu C dizisinin yanında yer yoksa büyütmek için yeni, daha büyük bir blok ayırıp değerleri taşımak gerekebilir. Bağlı listede ayrı bir düğüm ayırıp bağlantıları değiştirirsin. Fakat bu bedelsiz esneklik değildir: her düğüm bir işaretçi de taşır ve beşinci öğeye gitmek için ilk düğümden başlayıp bağlantıları izlersin. Dizi hücresine indeksle gitme kolaylığını kaybedersin. Sıralı bir bağlı listede bile orta öğeye sabit zamanda atlayamadığın için, dizideki ikili aramanın O(log n) erişim avantajını doğrudan elde etmezsin.²

“Listeye eklemek O(1)” cümlesinin eksik kısmını tamamlayalım: başa eklemek için gereken bağlantı değişiklikleri sabittir. Sıralı yerini bulmak için önce n düğüme bakman gerekebilir. Sona eklemek, yalnızca başı tutup sonu arıyorsan O(n), son düğümün işaretçisini de tutuyorsan bağlantı açısından O(1) olabilir. Konumu bulma işi ile bağlantıyı değiştirme işi ayrı hesaplardır. Bu bölümde bellek ayırmanın sistem düzeyindeki bedelini bu basit modele dahil etmiyoruz.²

Büyüyen dizi hâlâ dizidir

Bağlı liste, büyümenin tek yolu değildir. CS50 yeni bir dizi bloğu ayırıp eskisini kopyalamayı ve realloc ile yeniden yer ayırmayı da gösterir. Demek ki “boyutu büyüyen veri” otomatik olarak bağlı liste demek değildir. Önceki bölümde JavaScript dizisinin kolayca büyüdüğünü gördün; bunu görünce “demek içerisi bağlı liste” sonucuna varma. Bir dilin sunduğu büyütme arayüzü, içeride hangi veri düzeninin seçildiğini tek başına söylemez. Burada incelediğimiz yan yana hücre modeli özellikle C dizisidir.²

Ağaç: bir sonrakinden birden çok dala

Ağaç (tree), bir kökten başlayıp alt düğümlere dallanan hiyerarşik yapıdır. Kitaptaki kısım → bölüm → konu sırası gibi. Her ağaç arama ağacı değildir. İkili arama ağacı (binary search tree) ise ek bir düzen taşır: bu örnekte küçük değerler soldaki, büyük değerler sağdaki alt ağaçtadır. Bir düğümde 42 varsa 63 ararken sol dalın tamamını elemek mümkün olur.²

           42
          /  \
        18    80
       /  \   / \
      7   25 63  91

Burada kök 42'dir; 63 için 42 → 80 → 63 yolu izlenir. Dallar dengeliyse yol uzunluğu öğe sayısından çok daha yavaş, O(log n) büyür. Ama 7, 18, 25, 42 değerlerini saf bir arama ağacına sırayla ekleyip hepsini sağa bağlarsan yapı bir zincire dönüşebilir. O zaman en kötü arama O(n)'dir. “Ağaç hızlıdır” yerine “hangi ağaç, hangi denge koşuluyla?” demelisin. Kitabın ilerideki veritabanı dizinleri köprüsünün temeli bu sorudur.²

Karma tablo: anahtardan bölmeye gitmek

Karma tablo (hash table), bir anahtarı hesapla bir bölmeye yönlendirerek aramayı kısaltır. Karma fonksiyonu (hash function) anahtardan sayısal bir sonuç üretir; bu sonuç bölme seçmekte kullanılır. Kimliği bilinen kullanıcının kaydını bulmak buna örnektir. Anahtar kimliktir, değer ise puan ve seri gibi alanları olan kullanıcı kaydıdır. Bu bir veri düzeni fikridir; ilerideki parola güvenliğinin özet fonksiyonunu burada öğrenmiş sayılmıyorsun.²

Öğretici ama bilerek zayıf bir fonksiyon seçelim: sayısal kimliği 4'e bölünce kalana bak. Kimlik 10 için 2, kimlik 18 için de 2 çıkar. İki farklı anahtarın aynı bölmeye yönelmesine çakışma (collision) denir. Bu bir hata veya iki kullanıcının aynı kişi olması değildir. CS50'nin gösterdiği çözümde her bölme bir bağlı listenin başını tutar; önce bölmeyi bulur, sonra o bölmedeki gerçek anahtarları karşılaştırırsın.²

Yeterince bölme varsa ve anahtarlar iyi dağılıyorsa beklenen arama işi sabit düzeyde tutulabilir. Bu bir dağılım ve kapasite varsayımıdır; her anahtar aynı bölmeye giderse n kaydı yine dolaşmak gerekebilir. Üstelik uzun bir anahtardan karma sonucunu hesaplamak da kendi uzunluğuna bağlı iş ister. Bu yüzden karma tablo için duyduğun “ortalama O(1)” sözünü, “her girdide kesin tek adım” diye çevirmemelisin. CS50 özellikle çakışmaların en kötü O(n) davranışa yol açabildiğini gösterir.²⁶

Kuyruk ve yığın: nerede değil, hangi sırayla?

Kuyruk (queue) ilk giren ilk çıkar kuralıdır: FIFO (first in, first out). A, B, C sırayla eklendiyse sıradaki çıkarma A'yı verir. Ekleme enqueue, çıkarma dequeue diye geçer. Yığın (stack) ise son giren ilk çıkar: LIFO (last in, first out). Aynı eklemelerden sonra ilk çıkarılan C'dir. Üste koyma push, üstten alma pop adını alır.²

Burada iki ayrı soruyu ayırıyoruz: “Öğeleri hangi sırayla alacağım?” bir davranış sözüdür; “Bunları diziyle mi, bağlı düğümlerle mi tutacağım?” gerçekleme kararıdır. CS50 kuyrukla yığının başlangıçta aynı tür alanlarla tanımlanabildiğini gösterir; fark, hangi işlemlere izin verildiğindedir. Bölüm 1.4'teki arayüz ile gerçekleme ayrımı, şimdi veri yapılarında karşına çıktı.²

11.6 Uygulamamızda: leaderboard, soru arama ve veritabanı dizini

Sıralama tablosu (leaderboard) örneğinde kuralları önce yazalım: puan azalan, eşit puanda kullanıcı kimliği artan olsun. İkinci kural olmadan eşit puanlı iki kişinin hangi sırada görüneceğini tarif etmiş olmazsın. Örneğin (kimlik, puan) kayıtları (18,70), (7,90), (10,90) ise örnek sıramız (7,90), (10,90), (18,70) olur. Python ile doğrulanan bu sonuç bizim seçtiğimiz ürün kuralıdır; prototipin gerçek davranışı olduğu iddia edilmiyor.

Soru bankasında “kimliği 63 olan soruyu bul” sayısal eşitlik aramasıdır. “İçinde kusur kelimesi geçen bütün soruları bul” ise metin üzerinde başka bir aramadır. Bugünkü ikili arama, herhangi bir metnin içinde geçen sözcükleri otomatik olarak bulmaz. Neyi aradığını, verinin neye göre sıralandığını ve hangi karşılaştırmayı yaptığını belirtmek gerekir. Veri yapısını seçmeden önce erişim sorusunu seçersin.¹

B-tree'ye yalnızca bir köprü

Veritabanı, verileri saklayıp sorgulayan sistemdir; ayrıntısı Bölüm 38'de. Bir dizin (index), kayıtlara ulaşmayı kolaylaştıran ek veri yapısıdır. Buradaki index, C dizisinin kaçıncı hücresi anlamındaki “indeks” değildir. PostgreSQL belgeleri, varsayılan dizin türünün B-tree olduğunu ve bunun eşitlik, aralık karşılaştırmaları ve uygun durumda sıralı sonuç üretmek için kullanılabildiğini belirtir. Demek ki arama ağacı fikri, yalnızca ders kâğıdında kalmaz.³

B-tree (B-tree), veritabanlarının kullandığı dengeli arama ağacı ailesidir; CS50'nin çizdiğimiz iki dallı ağacıyla birebir aynı yapı değildir.⁴ Şimdilik ortak fikri al: verinin sırasını bir yardımcı yapıda tutarak her soruda bütün kayıtları dolaşmamak. Yapısını, dizinin yazma maliyetini ve gerçekten kullanılıp kullanılmadığını Bölüm 39'da göreceğiz. “Dizin varsa her sorgu hızlıdır” sonucu bu belgelerden çıkmaz; PostgreSQL bile sıralı dizin okumasının her zaman tarayıp sıralamaktan hızlı olmadığını söyler.⁷

Bu bölümde neler kuruldu

Büyük O, temel işlemlerin girdi büyürken nasıl arttığını sınırlar; saniye veya tek komut garantisi değildir. Doğrusal arama sırayla bakar, ikili arama sıralılıkla yarıları eler. Seçmeli ve kabarcık sıralama ile birleştirmeli sıralama farklı iş düzenleridir. Özyineleme taban durumuna yaklaşır. Bağlı liste bağlantıyla, ağaç dallarla, karma tablo hesaplanan bölmelerle erişim kurar. Kuyruk ve yığın hangi öğenin önce çıkacağını belirler. Uygulamamızda kimlik arama ile puan sırası farklı sorulardır; dizin ve B-tree bu fikirleri veritabanına taşıyacak.

Terimler sözlükte, Bölüm 11 başlığı altında.

Kaynaklar

1. Harvard CS50x, Lecture 3 ders notları: Running Time; Linear Search; Binary Search; Sorting and Selection Sort; Bubble Sort; Recursion; Merge Sort. İşlem sayısı, sıralılık, taban durumu ve sıralama maliyetleri.
2. Harvard CS50x, Lecture 5 ders notları: Data Structures; Queues; Stacks; Arrays; Linked Lists; Trees; Hashing and Hash Tables. Bağlantılar, düğümler, dengeli arama ve çakışma maliyetleri.
3. PostgreSQL belgeleri, 11.2 Index Types — B-Tree: Varsayılan dizin türü, eşitlik/aralık araması ve uygun durumda sıralı erişim; dizinin her sorguyu hızlandırdığı iddia edilmiyor.
4. Pat Morin, Open Data Structures — 14.2 B-Trees: İki dallı arama ağacının çok dallı genellemesi; bütün yaprakların aynı derinlikte olması ve bloklara göre düzenlenmesi.
5. Pat Morin, Open Data Structures — 11.1.1 Merge-Sort: Dizi parçalarının kopyalanması ve sıralı parçalardan çıktı oluşturulması; zaman ve bellek maliyeti ayrımı.
6. Pat Morin, Open Data Structures — 5.1 ChainedHashTable: İyi dağılım, kapasite ve beklenen liste uzunluğu varsayımları; beklenen sabit arama maliyeti ve kötü dağılımın sınırı.
7. PostgreSQL — Indexes and ORDER BY: Dizinden sıralı okuma ile tabloyu tarayıp sıralama arasında sorguya bağlı maliyet seçimi.