Maliyet modelini bütünleştirme ve performans gözlemi

Dönem boyunca O(1), O(log n), O(n), O(n log n) ve O(n²) gösterimlerini farklı veri yapıları ve algoritmalar için kullandık. Bu hafta hepsini bir arada göreceğiz. Küçük ölçüm deneyleriyle de işlem sayısı, veri boyutu ve çalışma süresi arasındaki ilişkiye bakacağız.

Ölçtüğümüz milisaniyeler bilgisayardan bilgisayara değişir, onları ezberlemenin anlamı yok. Deneylerle şu soruya cevap arayacağız:

Veri büyüdükçe çözümün maliyeti nasıl değişiyor?

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

• Temel Big-O sınıflarının veri büyüdükçe nasıl davrandığını karşılaştırabilmeli,
• Sabit çarpan ile büyüme sınıfını ayırt edebilmeli,
• İşlem sayarak basit bir maliyet hesabı yapabilmeli,
• O(n log n) büyümesini “kaç bölme katmanı var, her katmanda toplam ne kadar iş var” sorularıyla açıklayabilmeli,
• timeit ve perf_counter ile küçük deneyler kurabilmeli,
• Tek bir zaman ölçümünün neden güvenilir olmayabileceğini açıklayabilmeli,
• Aynı ölçümü tekrarlayıp farklı veri boyutlarındaki sonuçları karşılaştırabilmeli,
• Doğrusal arama, ikili arama ve temel sıralama örneklerinin büyüme davranışını yorumlayabilmeli,
• Seçtiğiniz veri yapısının programın hızını nasıl etkilediğini gerekçelendirebilmelisiniz.

2 Big-O neyi anlatır?

Big-O gösterimi, veri büyüdükçe bir algoritmanın maliyetinin nasıl büyüdüğünü sınıflandırır.

Bu derste matematiksel limit ya da ispat yapmıyoruz. Kabaca şöyle düşünebilirsiniz:

Sınıf	Nasıl büyür?	Örnek
O(1)	veri büyüse de yaklaşık sabit	liste indeks erişimi
O(log n)	her adımda verinin büyük bir kısmı elenir	ikili arama
O(n)	eleman sayısıyla aynı oranda büyür	doğrusal arama
O(n log n)	yaklaşık log n katman, her katmanda toplam n iş	verimli, genel amaçlı sıralamalar
O(n²)	veri iki kat olunca iş yaklaşık dört kat olabilir	temel sıralamalar (insertion, selection, bubble)

3 Büyüme tablosu

Aşağıdaki değerler çalışma süresi değildir. Büyüme hızlarını karşılaştırmak için hesaplanmış işlem sayılarıdır.

Özellikle n² değerinin hızlı büyümesine, n log n değerinin ise n ile n² arasında kaldığına dikkat edin.

4 O(n log n) nereden gelir? Böl ve birleştir sezgisi

Bu derste merge sort’u (veriyi tekrar tekrar ikiye bölüp parçaları sıralı biçimde birleştiren algoritma) kodlamayacağız. Özyineleme (bir fonksiyonun kendini çağırması) ve merge sort’un ayrıntıları bu dersin konusu değil. Yine de O(n log n) ifadesinin nereden geldiğini kabaca görmekte yarar var.

Bir sıralama yaklaşımının veriyi tekrar tekrar ikiye böldüğünü düşünün:

8 eleman
→ 4 + 4
→ 2 + 2 + 2 + 2
→ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

8 elemanı 1 elemanlık parçalara ayırmak için log2(8) = 3 kez bölmek gerekir, yani 3 katman oluşur. Her katmanda bütün elemanlar toplamda yaklaşık bir kez işleniyorsa:

katman sayısı ≈ log n
her katmandaki toplam iş ≈ n

→ toplam ≈ n × log n

flowchart TD
    A["8 öğe"] --> B1["4"]
    A --> B2["4"]
    B1 --> C1["2"]
    B1 --> C2["2"]
    B2 --> C3["2"]
    B2 --> C4["2"]
    C1 --> D["1'lik parçalar"]
    C2 --> D
    C3 --> D
    C4 --> D

Note

Bu şema merge sort’un tamamını göstermez. Yalnızca n log n çarpımının nereden geldiğini gösterir: log n katman × her katmanda toplam n iş.

5 Sabit çarpan büyüme sınıfını değiştirmez

İki doğrusal algoritma düşünelim:

A: yaklaşık n işlem
B: yaklaşık 10n işlem

Aynı veride B, A’dan yavaş olabilir. Ama veri iki katına çıkınca ikisinin de işi yaklaşık iki katına çıkar. Bu yüzden ikisi de O(n) sınıfındadır. Big-O, 10n içindeki 10 gibi sabit çarpanları hesaba katmaz.

Big-O her performans ayrıntısını anlatmaz. Donanım, dil, veri düzeni ve sabit maliyetler gerçek süreyi etkiler.

6 İşlem saymak

Önce süre ölçmeden algoritmanın kaç işlem yaptığını sayalım:

Son elemanı aradığımız için kontrol sayısı doğrudan n ile büyür.

7 İkili aramada işlem sayısı

Veri iki katına çıkarken kontrol sayısı genellikle yalnızca yaklaşık bir artar.

8 O(n²) davranışını gözlemleme

n iki katına çıktığında n² yaklaşık dört katına çıkar:

10 → 100
20 → 400
40 → 1600
80 → 6400

9 Önce işlem sayısı, sonra kronometre

İşlem sayısı çoğu zaman algoritmanın davranışını daha net gösterir. Kronometreyle ölçülen süreye ise bilgisayarın o anki durumu da karışır. Bu yüzden küçük bir deneyi şu sırayla yapın:

1. Algoritmanın hangi işlemleri yaptığını anlayın,
2. Farklı n değerlerinde işlem sayısına bakın,
3. Sonra çalışma süresini ölçün,
4. Tek bir sayıya değil, n büyüdükçe sürenin nasıl değiştiğine bakın.

10 timeit ile küçük deney

Python’ın timeit modülü kısa bir kod parçasını birçok kez çalıştırır ve toplam süreyi ölçer.

Bu deneyde üyelik kontrolü (in ile bir değerin koleksiyonda olup olmadığına bakmak) kümede genellikle çok daha hızlı çıkar. Yine de bir kez ölçtüğünüz süreyi her bilgisayarda aynı çıkacakmış gibi yorumlamayın.

11 Kurulum maliyetini ayırmak

Şu iki soruyu birbirinden ayırın:

1. Veri yapısını oluşturmak ne kadar sürüyor?
2. Yapı hazır olduktan sonra her işlem ne kadar sürüyor?

Örneğin listeyi kümeye dönüştürmenin bir maliyeti vardır:

Yalnızca bir kez üyelik kontrolü yapacaksak listeyi kümeye dönüştürmek gereksiz olabilir. Binlerce üyelik kontrolü yapacaksak dönüşüm maliyeti karşılığını verebilir.

Veri yapısını seçerken tek bir işleme bakmayın. Yapıyı toplamda nasıl ve kaç kez kullanacağınızı düşünün.

12 perf_counter ile kendi ölçümümüz

perf_counter() kısa süreleri ölçmek için çok hassas bir sayaçtır. Ama tek bir ölçüme rastgele sapmalar (gürültü) karışabilir.

13 Neden tek ölçüm yanıltıcıdır?

Çalışma süresi şunlardan etkilenebilir:

• İşletim sisteminin o anda yaptığı işler,
• Tarayıcı veya Python çalışma zamanı,
• İşlemci önbelleği,
• Arka plan süreçleri,
• Veriyi oluşturma süresinin yanlışlıkla ölçüme katılması,
• Çok kısa sürelerde sayacın kendi sapması.

Bu yüzden performans deneylerinde şunları yapın:

• İşlemi birkaç kez tekrarlayın,
• Veriyi mümkünse ölçüm başlamadan hazırlayın,
• Farklı veri boyutlarını karşılaştırın,
• Sonucu tek bir sayıyla değil, boyutlar arasındaki oranla yorumlayın.

14 Tek ölçüm yerine tekrarlar

Aşağıdaki yardımcı fonksiyon aynı işi birkaç kez ölçer ve medyan süreyi döndürür. Medyan, ölçümler küçükten büyüğe dizildiğinde ortada kalan değerdir. Tek bir sıra dışı ölçüm medyanı pek etkilemez.

Tip

Profesyonel bir ölçüm (benchmark) düzeni kurmanız gerekmez. Ölçümü bir kez yapıp bırakmayın, tekrarlamayı alışkanlık edinin. Sonuç daha güvenilir olur.

15 Alıştırma: doubling deneyi

Doubling (ikiye katlama) deneyinde veri boyutunu her seferinde iki katına çıkarır ve sürenin nasıl değiştiğine bakarsınız. Aşağıdaki fonksiyonun işi n ile aynı oranda artar. Her veri boyutunu birkaç kez ölçüp medyan süreyi kaydedin. n iki katına çıkınca süre nasıl değişiyor?

Oranların tam 2.0 çıkması beklenmez. Yorumunuz şu soruyu cevaplasın: veri boyutu iki katına çıkınca medyan süre de aşağı yukarı iki katına çıkıyor mu?

15.1 Doubling oranını hesaplayın

Bu oran bir şey ispatlamaz. Veri büyüdükçe sürenin nasıl değiştiğini görmenize yardım eder.

16 Hazır sıralama ile temel sıralama karşılaştırması

Tarayıcınızı gereksiz yere uzun bir hesaplamayla yormamak için aşağıdaki örneği küçük tuttuk.

Bu deneyden “sorted() her bilgisayarda şu kadar kat hızlı” gibi bir sonuç çıkmaz. Ama gerçek programlarda neden yerleşik sıralamanın kullanıldığını görürsünüz.

17 Maliyet sınıflarını bir arada düşünme

flowchart TD
    A["İşlem gereksinimi"] --> B{"Doğrudan erişim mi?"}
    B -- Evet --> C["O(1) olabilir"]
    B -- Hayır --> D{"Veri sıralı mı?"}
    D -- Evet --> E["İkili arama: O(log n)"]
    D -- Hayır --> F["Doğrusal arama: O(n)"]
    A --> G{"Bölme katmanları + her katmanda toplam n iş mi?"}
    G -- Evet --> H["O(n log n)"]
    A --> I{"Temel iç içe karşılaştırma mı?"}
    I -- Evet --> J["O(n²) riski"]

Bu şemayı adım adım izlenecek bir karar yolu gibi kullanmayın. Yalnızca dönem boyunca gördüğümüz maliyet sınıflarını hatırlatır.

18 Kısa karar örnekleri

18.1 Senaryo 1

10 elemanlı listede bir kez arama yapacaksınız.

• Doğrusal arama yeterli olabilir,
• Veriyi ayrıca sıralayıp ikili arama yapmak gereksiz olabilir.

18.2 Senaryo 2

100.000 kullanıcı adında binlerce kez üyelik kontrolü yapacaksınız.

• Listede tekrar tekrar doğrusal arama yapmak yavaş kalabilir,
• set bu iş için daha uygun olabilir.

18.3 Senaryo 3

Sıralı 1 milyon kimlik üzerinde çok sayıda arama yapacaksınız.

• İkili arama ya da kimliğe göre kurulmuş bir sözlük (indeks) mantıklı olabilir.

19 Bölüm özeti

• Big-O, veri büyüdükçe maliyetin büyüme biçimini anlatır.
• O(1), O(log n), O(n), O(n log n) ve O(n²) farklı büyüme sınıflarıdır.
• O(n log n), yaklaşık log n katman ve her katmanda toplam n iş olarak düşünülebilir.
• Big-O gerçek çalışma süresindeki tüm ayrıntıları açıklamaz.
• İşlem saymak, zaman ölçmeden önce algoritmanın davranışını anlamaya yardımcı olur.
• timeit ve perf_counter küçük performans deneyleri için kullanılabilir.
• Tek ölçüme güvenmeyin. Ölçümü tekrarlayın, medyanını alın ve farklı veri boyutlarını karşılaştırın.
• Doubling deneyi, veri boyutu iki katına çıktıkça sürenin nasıl değiştiğini gösterir.
• Bir veri yapısını oluşturmanın maliyetini, o yapıda kaç kez işlem yapılacağıyla birlikte düşünün.

20 Kendinizi kontrol edin

1. O(n) ile O(n²) arasında veri iki katına çıktığında nasıl bir büyüme farkı beklenir?
2. O(n log n) büyümesini “katman sayısı × her katmandaki toplam iş” fikriyle açıklayın.
3. Tek bir süre ölçümü neden bir algoritmanın Big-O sınıfını kanıtlamaz?
4. Listeyi kümeye dönüştürmenin maliyeti neden toplam kararın parçasıdır?
5. İkili aramanın O(log n) davranışını yarıya indirme fikriyle açıklayın.
6. Performans deneyinde veri hazırlığını ölçüm dışında tutmak neden yararlı olabilir?
7. Ölçümü tekrarlayıp medyanını almak, tek ölçüme göre ne kazandırır?