Karşılaştırmalı Ölçüm ve Profilleme

Önceki ders bir gövdenin doğru çalıştığını koşarak gösterdi, ama bu gösterimin sınırlı sayıda girdiyle ve sınamayı yazan tarafın kararlarıyla sınırlı kaldığını ölçtü. Bu ders aynı “koşarak kurulan güvence” fikrini bambaşka bir soruya uyguluyor: iki yazımdan hangisi daha az iş yapıyor? Derleyici bu soruyu da hiç sormaz — iki yazım da tip denetiminden geçer, ikisi de derlenir ve derleyici ikisinin de kaç adımda bir sonuca ulaştığı konusunda hiçbir görüş bildirmez.

Bu ölçümün Rust’a özgü sert bir kısıtı var: derleyicinin kendi dağıtımında bir karşılaştırmalı ölçüm niteliği bulunur, ama bu nitelik kararlı sürümde açık değildir — yalnız derleyicinin kararsız (nightly) dalında kullanılabilir. Bu ders kararlı derleyiciyle çalıştığı için bu niteliği hiç kullanmıyor; süre zaten bu müfredatın hiçbir dersinde basılmaz — bir sürenin bu makinede aldığı değer başka bir makinede geçerli değildir; aynı program aynı makinede bile arka planda koşan başka bir işten, önbelleğin o an ne tuttuğundan ya da işletim sisteminin zamanlayıcı kararından etkilenir. Bu yüzden “hangi yazımın süresi kısa” sorusu bu derste hiç sorulmuyor; onun yerine sorulan, “hangi yazım kaç işlem yapıyor”. M09/K05 kursu Go’da başarım iddialarını süre yerine iş başına ayırma sayısıyla ölçmüştü; bu ders aynı ilkeyi karşılaştırma ve kopyalama sayısına uyguluyor — ikisi de aynı gerekçeden geliyor: ortama bağlı olmayan bir sayı, ortama bağlı bir süreden daha güvenilir bir ölçme birimi.

İşlem Sayısıyla Karşılaştırma

Aynı işi yapan iki sıralama yazımı — seçmeli sıralama ve eklemeli sıralama — aynı dizide koşturuluyor. İkisi de sonucu doğru sıralar, ama farklı sayıda karşılaştırma ve farklı sayıda kopyalama yaparak sıralar. Bu farkı görünür kılmak için iki yazım da paylaşılan bir sayaca her karşılaştırmada ve her kopyalamada bir artış yazıyor.

Seçmeli sıralama, dizinin sıralanmamış kalan kısmında en küçük elemanı arar, onu bulunca sıralı kısmın hemen ardına taşır ve bu adımı dizinin sonuna kadar tekrarlar — her adımda kalan bütün elemanlara bakılır, ama yer değiştirme yalnızca bir kez olur. Eklemeli sıralama ise dizinin başından başlar, her yeni elemanı zaten sıralı duran önceki kısmın doğru yerine kadar geri kaydırarak yerleştirir — bir eleman yerine oturana kadar birden çok kaydırma gerekebilir, ama her kaydırma yalnızca komşu elemanlarla karşılaştırma yapar. İki yazım da aynı sonuca varır; ölçülen, oraya varmak için attıkları adım sayısı.

// islem_sayaci.rs — kars ve kopya sayaci, iki siralama yazimi arasinda paylasilir
#[derive(Default)]
pub struct IslemSayaci {
    pub karsilastirma: u64,
    pub kopyalama: u64,
}

pub fn secmeli_sirala(dizi: &mut [i32], sayac: &mut IslemSayaci) {
    let n = dizi.len();
    for i in 0..n {
        let mut en_kucuk = i;
        for j in (i + 1)..n {
            sayac.karsilastirma += 1;
            if dizi[j] < dizi[en_kucuk] {
                en_kucuk = j;
            }
        }
        if en_kucuk != i {
            dizi.swap(i, en_kucuk);
            sayac.kopyalama += 1;
        }
    }
}

pub fn eklemeli_sirala(dizi: &mut [i32], sayac: &mut IslemSayaci) {
    let n = dizi.len();
    for i in 1..n {
        let deger = dizi[i];
        let mut j = i;
        while j > 0 {
            sayac.karsilastirma += 1;
            if dizi[j - 1] <= deger {
                break;
            }
            dizi[j] = dizi[j - 1];
            sayac.kopyalama += 1;
            j -= 1;
        }
        dizi[j] = deger;
        sayac.kopyalama += 1;
    }
}

PY9. secmeli_sirala her adımda kalan en küçük elemanı arıyor ve onu bulunca tek bir takasla (swap) yerine koyuyor — bu yüzden karşılaştırma sayısı çok, ama kopyalama sayısı az. eklemeli_sirala ise her elemanı zaten sıralı kısmın doğru yerine kaydırarak yerleştiriyor — karşılaştırma sayısı girdinin düzenine bağlı, kopyalama sayısı kaydırılan eleman sayısına bağlı. İki yazım da aynı sonucu üretiyor, ama farklı bir yoldan.

// olcum.rs — ayni dizi uzerinde iki siralama yaziminin islem sayisi
mod islem_sayaci;
use islem_sayaci::{eklemeli_sirala, secmeli_sirala, IslemSayaci};

fn main() {
    let girdi: [i32; 12] = [9, 3, 7, 1, 8, 2, 6, 4, 10, 5, 12, 11];

    let mut dizi_a = girdi;
    let mut sayac_a = IslemSayaci::default();
    secmeli_sirala(&mut dizi_a, &mut sayac_a);

    let mut dizi_b = girdi;
    let mut sayac_b = IslemSayaci::default();
    eklemeli_sirala(&mut dizi_b, &mut sayac_b);

    println!("secmeli sonuc:  {:?}", dizi_a);
    println!("eklemeli sonuc: {:?}", dizi_b);
    println!("ikisi de ayni sonucu verdi: {}", dizi_a == dizi_b);
    println!();
    println!("{:<12}{:<14}{}", "yazim", "karsilastirma", "kopyalama");
    println!("{:<12}{:<14}{}", "secmeli", sayac_a.karsilastirma, sayac_a.kopyalama);
    println!("{:<12}{:<14}{}", "eklemeli", sayac_b.karsilastirma, sayac_b.kopyalama);
}

secmeli sonuc:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
eklemeli sonuc: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
ikisi de ayni sonucu verdi: true

yazim       karsilastirma kopyalama
secmeli     66            9
eklemeli    32            34

On iki elemanlı bu dizide seçmeli sıralama altmış altı karşılaştırma ve dokuz kopyalama yaptı; eklemeli sıralama otuz iki karşılaştırma ve otuz dört kopyalama yaptı. PY10. Hiçbir yazım her iki sütunda da “daha az” değil: seçmeli sıralama karşılaştırmada kaybediyor ama kopyalamada kazanıyor, eklemeli sıralama tam tersi. Tek bir sayı (“toplam işlem”) üretmek bu farkı gizlerdi; iki ayrı sayaç tutmak, hangi yazımın hangi kaynağı daha çok kullandığını ayrı ayrı görünür kılıyor.

Karşılaştırma ve kopyalamayı tek bir toplamda birleştirmenin nasıl yanıltıcı olabileceği bu sayılarda görülebilir: yetmiş beş (66 + 9) ile altmış altı (32 + 34) toplandığında eklemeli sıralama daha “az işlem yapmış” gibi görünür. Ama bu toplam, bir karşılaştırmayla bir kopyalamayı aynı birimden sayıyor — oysa ikisi farklı işlemler ve farklı maliyetler taşıyabilir. Sayaç bu iki işlemi bilerek ayrı tuttu; birleştirilmiş bir toplam, seçmeli sıralamanın kopyalamada ne kadar tutumlu olduğunu (yalnızca dokuz) gizler.

Bu iki sayaç aynı zamanda bir profilleme biçimi. Karşılaştırmalı ölçüm iki yazımı birbiriyle kıyaslarken, profilleme tek bir yazımın nereye iş harcadığını sorar — hangi adım, hangi işlem türü toplam işin ne kadarını oluşturuyor. IslemSayacinin iki ayrı alanı tam olarak bunu yapıyor: seçmeli sıralamanın işinin neredeyse tamamı karşılaştırmada (altmış altı karşılaştırmaya karşı dokuz kopyalama), eklemeli sıralamanın işi ise iki tür arasında daha dengeli dağılıyor (otuz iki karşılaştırmaya karşı otuz dört kopyalama). Bir profilleme aracı gerçek bir programda genellikle hangi işlevin toplam sürenin ne kadarını tükettiğini gösterir; bu ders süre yerine işlem türünü kullanıyor, ama soru aynı: iş nereye gidiyor?

Ayrım cümlesi: M09/K05 kursunun Karşılaştırmalı Ölçüm dersi bir gövdenin iş başına kaç ayırma yaptığını ölçtü — orada sayılan, öbek üzerinde yeni bellek ayrılıp ayrılmadığıydı ve bir işlev çağrısı içinde kaç kez tekrarlandığıydı. Bu derste hiç bellek ayırma yok; her iki sıralama da girdi dizisini yerinde (&mut [i32]) sıralıyor, yeni bir dizi ya da yapı kurmuyor. Sayılan, karşılaştırma ve kopyalama gibi doğrudan algoritmanın adımları. İkisi de süre yerine bir sayı kullanıyor, ama sayının neyi temsil ettiği farklı: biri kaynak tüketimini (kaç kez öbekten yer istendiğini), bu ders algoritmanın kendi iş adımlarını (kaç kez iki değer karşılaştırıldığını, kaç kez bir değer taşındığını) sayıyor.

Bu sayının verdiği güvence koşarak geliyor, derleyiciden değil — ve kimse bu sayıyı sürekli izlemiyor. Derleyici iki yazımın da tipini denetledi, ikisinin de aynı imzayı taşıdığını doğruladı, ama hangisinin daha az karşılaştırma yaptığı sorusunu hiç sormadı; bu soruyu yalnız yukarıdaki koşum yanıtladı ve yanıt yalnız bu koşum için geçerli — dizi değişirse, birinin kaynak kodu değişirse, aynı ölçümü yeniden koşturmadan sayıların hâlâ geçerli olduğunu söylemenin bir yolu yok. Bu derste ölçülen sınıf denetlenmiyor: iki yazımın göreli maliyeti hiçbir araç tarafından sürekli gözetilmiyor, yalnızca istendiğinde tek seferlik bir koşumla öğrenilebiliyor.

Bu, önceki derste ölçülen devredildi sınıfından ayrı bir yer. Orada bir özellik sınaması vardı ve o sınama, yeniden koşturulduğunda aynı soruyu yeniden yanıtlıyordu — sorumluluk yazan tarafa devredilmişti ama bir sınama biçiminde sürekli hâle getirilebilirdi. Bu derste öyle bir sınama yok; yukarıdaki koşum bir kerelik bir gözlem ve onu bir sınamaya dönüştürüp kaynak değiştikçe otomatik yeniden çalıştırmak bu dersin kapsamı dışında. Böyle bir sınama yazılsaydı bile, neyin “iyi” sayılacağına (hangi sayının hangi sınırın altında kalması gerektiğine) yine yazan taraf karar verirdi — ama en azından o zaman denetim sürekli hâle gelirdi. Bugünkü hâliyle denetim yalnız bu dersin koşumuyla sınırlı.

Sınırlayıcı Ölçüm

Yukarıdaki sayılar tek bir girdiye, on iki elemanlı karışık bir diziye ait. Aynı iki yazım farklı bir girdide koşturulunca sayılar nasıl değişiyor? Aşağıdaki koşum aynı iki işlevi, zaten sıralı bir diziye uyguluyor.

// sinir_olcum.rs — ayni yazimlar, siradan bir dizide islem sayisi nasil degisir
mod islem_sayaci;
use islem_sayaci::{eklemeli_sirala, secmeli_sirala, IslemSayaci};

fn main() {
    let siradan: Vec<i32> = (1..=12).collect();

    let mut a = siradan.clone();
    let mut sayac_a = IslemSayaci::default();
    secmeli_sirala(&mut a, &mut sayac_a);

    let mut b = siradan.clone();
    let mut sayac_b = IslemSayaci::default();
    eklemeli_sirala(&mut b, &mut sayac_b);

    println!(
        "secmeli kars={} kopya={}",
        sayac_a.karsilastirma, sayac_a.kopyalama
    );
    println!(
        "eklemeli kars={} kopya={}",
        sayac_b.karsilastirma, sayac_b.kopyalama
    );
}

secmeli kars=66 kopya=0
eklemeli kars=11 kopya=11

PY11. Seçmeli sıralamanın karşılaştırma sayısı değişmedi: hâlâ altmış altı — girdi zaten sıralı olsa da seçmeli sıralama kalan her elemanı yine de tek tek tarıyor, çünkü en küçüğü bulmanın tek yolu hepsine bakmak. Eklemeli sıralamanın karşılaştırma sayısı ise otuz ikiden on bire düştü ve kopyalama sayısı otuz dörtten on bire düştü: zaten sıralı bir dizide her eleman bir önceki elemandan büyük olduğu için tek bir karşılaştırmayla yerini koruyor, hiç kaydırma gerekmiyor.

Tersi yönde bir girdi tam tersi bir sonuç verir. Dizi büyükten küçüğe sıralanmış olsaydı, eklemeli sıralamanın her elemanı sıralı kısmın en başına kadar kaydırması gerekirdi — kopyalama sayısı karışık dizideki otuz dörtten de yukarı çıkar, seçmeli sıralamanınki yine altmış altıda sabit kalırdı. Aynı iki yazım, üç farklı girdi düzeninde (karışık, sıralı, ters sıralı) birbirine göre üç farklı konumda durur: bazen biri az iş yapar, bazen öbürü, bazen ikisi de aynı sabit sayıda. Seçmeli sıralamanın karşılaştırma sayısının hep aynı kalması bir kusur değil, algoritmanın yapısının doğrudan sonucu — hangi eleman nerede olursa olsun, kalan her eleman yine de taranır.

Bu, ilk koşumun sonucunu neredeyse tersine çeviriyor, tam tersine değil: seçmeli sıralamanın karşılaştırma sayısı hâlâ eklemeli sıralamanınkinden büyük, ama aradaki oran çok değişti. İlk dizide eklemeli sıralama daha az karşılaştırma yapmıştı; bu dizide de öyle, ama fark çok büyüdü — otuz ikiye karşı altmış altıdan, on bire karşı altmış altıya. Aynı iki yazım, aynı uzunluktaki farklı bir girdide, birbirine göre çok farklı bir oranda duruyor. PY12. Bu, işlem sayısının girdiye bağlı olduğunu ve tek bir girdide alınan bir ölçümün başka bir girdi için hiçbir şey söylemediğini gösteriyor — seçmeli sıralamanın karşılaştırma sayısı girdiden bağımsızken, eklemeli sıralamanınki girdiye tamamen bağlı.

İşlem sayısının kendisi de süre demek değil. Bir karşılaştırma ile bir kopyalama aynı maliyeti taşımayabilir — kopyalanan değer büyük bir yapıysa bir kopyalama, bir tam sayı karşılaştırmasından çok daha pahalı olabilir; burada i32 kopyalandığı için bu fark küçük, ama sayaç bu farkı hiç bilmiyor, yalnız kaç kez çalıştıklarını sayıyor. Daha az işlem yapan bir yazımın süresinin gerçekte daha uzun olması da mümkün: işlemlerin türü, bellek erişim düzeni ve donanımın kendisi sonucu etkiler.

Bellek erişim düzeni bunun somut bir örneği. Seçmeli sıralama kalan elemanları tararken diziyi sürekli baştan sona okur; eklemeli sıralama ise yalnız yakın komşularla ilgilenir. Bu iki erişim örüntüsü donanımın önbelleğini farklı kullanabilir ve bu fark işlem sayısında hiç görünmez — iki yazım aynı sayıda karşılaştırma yapsa bile, biri önbelleğe daha uygun bir sırayla erişebilir, öbürü daha dağınık bir sırayla. Bu ders böyle bir farkı ölçmüyor, çünkü ölçmek gerçek donanımı ve gerçek süreyi devreye sokar; burada yalnız “kaç kez” sorusu yanıtlanıyor, “hangi sürede” değil. Bu yüzden yukarıdaki tablo “eklemeli sıralama daha iyi” diye okunmamalı — yalnızca “bu girdide eklemeli sıralama daha az karşılaştırma ve daha az kopyalama yaptı” diye okunmalı, ki bu bile bir sonraki girdide tekrarlanacağının garantisi değil.

Özet

• İki sıralama yazımı (secmeli_sirala, eklemeli_sirala) paylaşılan bir sayaçla karşılaştırma ve kopyalama sayısını ayrı ayrı sayarak karşılaştırıldı; süre hiçbir yerde ölçülmedi, basılmadı ya da karşılaştırılmadı.
• Karışık bir on iki elemanlı dizide seçmeli sıralama altmış altı karşılaştırma dokuz kopyalama, eklemeli sıralama otuz iki karşılaştırma otuz dört kopyalama yaptı.
• Güvencenin sınıfı denetlenmiyor: hangi yazımın kaç işlem yaptığı hiçbir araç tarafından sürekli gözetilmiyor, yalnız istenildiğinde tek seferlik bir koşumla öğrenilebiliyor.
• Zaten sıralı bir dizide seçmeli sıralamanın karşılaştırma sayısı değişmedi (altmış altı), eklemeli sıralamanınki on bire düştü — işlem sayısı girdiye bağlı.
• İşlem sayısı süre demek değildir: bir karşılaştırma ile bir kopyalama aynı maliyeti taşımaz ve daha az işlem yapan bir yazımın süresi gerçekte daha uzun da olabilir.
• Tek bir girdide alınan bir ölçüm, başka bir girdi için hiçbir şey söylemez; “daha az işlem” iddiası hangi girdide ölçüldüğüne bağlanmadan yazılamaz.

Sonraki Adım

Bu ders, iki yazımın göreli maliyetinin yalnızca koşularak öğrenilebildiğini, bu öğrenmenin tek bir girdiyle sınırlı kaldığını ve derleyicinin bu konuda hiçbir görüş bildirmediğini gösterdi — üç ders de (Bağımlılık ve Özellik Bayrakları’ndaki kapalı bayrak, Test ve Özellik Tabanlı Sınama’daki koşarak kurulan güvence, bu dersteki işlem sayısı) aynı temel gerçeğin farklı yüzleri: derleyicinin durduğu yerde, kalan sorumluluk ya hiç kimseye kalıyor ya da koşan bir sürece devrediliyor. Sıradaki ve bu konunun son dersi, aynı “derleyicinin hiç bakmadığı yer” sorusunu bambaşka bir kaynağa uyguluyor: bir kod bloğunun yanına yazılan açıklama. Belgelendirme dersi, bir belge cümlesinin doğru olup olmadığını hiçbir aracın denetlemediğini, ama aynı belgenin içine gömülü çalışan bir örneğin gerçekten sınanabildiğini — aynı kaynakta iki farklı güvence sınıfının yan yana durabildiğini — gösteriyor.