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²) ifadelerini farklı veri yapıları ve algoritmalar için kullandık. Bu hafta bu dili tek yerde toparlayacağız ve küçük ölçüm deneyleriyle işlem sayısı, veri boyutu ve çalışma süresi arasındaki ilişkiyi gözlemleyeceğiz.

Amaç milisaniye ezberlemek değildir. Amaç şu soruyu daha sistematik sormaktır:

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ı büyüme davranışı açısından karşılaştırabilmeli,
sabit çarpan ile büyüme sınıfını ayırt edebilmeli,
işlem sayısı üzerinden basit maliyet analizi yapabilmeli,
O(n log n) büyümesini bölme-katmanlar ve her katmandaki toplam iş fikriyle sezgisel olarak 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,
tekrar ölçümlerini ve farklı veri boyutlarını karşılaştırabilmeli,
doğrusal arama, ikili arama ve temel sıralama örneklerinin büyüme davranışını yorumlayabilmeli,
veri yapısı seçimi ile performans arasındaki ilişkiyi gerekçelendirebilmelisiniz.

2 Big-O neyi anlatır?

Big-O notasyonu, bir algoritmanın maliyetinin veri boyutu büyüdükçe nasıl büyüdüğünü sınıflandırmak için kullanılır.

Bu derste matematiksel limit veya ispat yapmıyoruz. Sezgisel olarak:

Sınıf	Büyüme sezgisi	Örnek
O(1)	veri büyüse de yaklaşık sabit	liste indeks erişimi
O(log n)	her adımda büyük bölüm elenir	ikili arama
O(n)	elemanlarla birlikte doğrusal büyür	doğrusal arama
O(n log n)	yaklaşık log n katman, her katmanda toplam n iş	verimli genel sıralama ailesi sezgisi
O(n²)	veri iki kat olunca iş yaklaşık dört kat olabilir	temel karesel sıralamalar

3 Büyüme tablosu

Aşağıdaki değerler gerçek çalışma süresi değildir; yalnızca büyüme hızlarını karşılaştırmak için işlem sayısı benzetimidir.

#| edit: false
#| completion: false
import math

for n in [10, 100, 1000, 10000]:
    print(
        f"n={n:5}",
        f"log2(n)≈{math.log2(n):6.1f}",
        f"n={n:6}",
        f"nlogn≈{n * math.log2(n):10.0f}",
        f"n²={n*n:10}",
    )

Ö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 kodlamayacağız; özyineleme ve ayrıntılı merge sort uygulaması çekirdek kapsamımızın dışında. Ancak O(n log n) ifadesinin nereden gelebileceğini sezgisel olarak görmek yararlıdır.

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 yaklaşık log2(8) = 3 bölme katmanı gerektirir. Her katmanda bütün elemanların toplamda yaklaşık bir kez işlenmesi gerekiyorsa:

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 tam uygulaması değildir. Amaç yalnızca n log n büyümesinin log n kadar katman × her katmanda toplam n kadar iş fikrinden nasıl doğabileceğini görmektir.

5 Sabit çarpan ile büyüme sınıfı aynı şey değildir

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

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

B, aynı veri boyutunda A’dan daha yavaş olabilir; ancak ikisi de veri iki katına çıktığında yaklaşık iki kat iş yapar. Bu nedenle ikisi de O(n) büyüme sınıfındadır.

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 ölçüm yapmadan algoritmanın davranışını sayalım:

#| edit: false
#| completion: false
def linear_search_checks(values, target):
    checks = 0
    for value in values:
        checks += 1
        if value == target:
            return checks
    return checks

for n in [10, 100, 1000, 5000]:
    values = list(range(n))
    print(n, linear_search_checks(values, n - 1))

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

7 İkili aramada işlem sayısı

#| edit: false
#| completion: false
def binary_search_checks(values, target):
    low = 0
    high = len(values) - 1
    checks = 0

    while low <= high:
        mid = (low + high) // 2
        checks += 1

        if values[mid] == target:
            return checks
        elif target < values[mid]:
            high = mid - 1
        else:
            low = mid + 1

    return checks

for n in [16, 32, 64, 128, 256, 512, 1024, 2048]:
    values = list(range(n))
    print(n, binary_search_checks(values, n - 1))

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

8 O(n²) davranışını görünür kılma

#| edit: false
#| completion: false
def pair_checks(n):
    checks = 0
    for i in range(n):
        for j in range(n):
            checks += 1
    return checks

for n in [10, 20, 40, 80]:
    print(n, pair_checks(n))

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

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

İşlem saymak çoğu zaman algoritmik davranışı daha temiz gösterir. Kronometre ise gerçek çalışma ortamının etkilerini de içerir. Bu yüzden iyi bir küçük deney şu sırayı izler:

algoritmanın hangi işlemleri yaptığını anlamaya çalış,
farklı n değerlerinde işlem sayısını gözle,
sonra çalışma süresini ölç,
tek bir sayıya değil ölçeklenme eğilimine bak.

10 `timeit` ile küçük deney

Python’ın timeit modülü, kısa kod parçalarını birçok kez çalıştırarak zaman ölçümü yapmaya yardımcı olur.

#| edit: false
#| completion: false
import timeit

list_time = timeit.timeit(
    "9999 in values",
    setup="values = list(range(10000))",
    number=100,
)

set_time = timeit.timeit(
    "9999 in values",
    setup="values = set(range(10000))",
    number=100,
)

print("list membership:", list_time)
print("set membership:", set_time)

Bu deney genellikle kümedeki üyelik kontrolünün belirgin biçimde daha hızlı olduğunu gösterir. Ancak tek bir çalıştırmadaki mutlak süreyi evrensel gerçek olarak yorumlamayın.

11 Kurulum maliyetini ayırmak

Şu iki soruyu ayırmak önemlidir:

veri yapısını oluşturmak ne kadar sürüyor?
oluşturulduktan sonra işlem ne kadar sürüyor?

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

#| edit: false
#| completion: false
import timeit

build_set = timeit.timeit(
    "set(values)",
    setup="values = list(range(10000))",
    number=100,
)

print("Küme oluşturma:", build_set)

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ı kararını tek bir işlemden değil, toplam kullanım deseninden çıkarın.

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

#| edit: false
#| completion: false
from time import perf_counter

values = list(range(100000))
target = values[-1]

start = perf_counter()
found = target in values
elapsed = perf_counter() - start

print("Bulundu:", found)
print("Süre:", elapsed)

perf_counter() kısa süre ölçümlerinde kullanılabilecek yüksek çözünürlüklü bir sayaçtır. Ancak tek ölçüm gürültülü olabilir.

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

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

işletim sisteminin o anda yaptığı işler,
tarayıcı veya Python çalışma zamanı,
işlemci önbelleği,
arka plan süreçleri,
veri oluşturma maliyetinin yanlışlıkla ölçüme dahil edilmesi,
çok küçük sürelerde zamanlayıcı gürültüsü.

Bu yüzden performans deneylerinde:

işlemi birkaç kez tekrar etmek,
veri hazırlığını mümkünse ölçüm dışına almak,
farklı veri boyutlarını karşılaştırmak,
tek sayıya değil büyüme eğilimine bakmak

daha anlamlıdır.

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, tek bir sıra dışı ölçümün sonucu fazla etkilemesini azaltır.

#| edit: false
#| completion: false
from statistics import median
from time import perf_counter


def median_time(fn, repeats=7):
    times = []

    for _ in range(repeats):
        start = perf_counter()
        fn()
        times.append(perf_counter() - start)

    return median(times)

values = list(range(50000))

def task():
    return -1 in values

print("Medyan süre:", median_time(task))

Tip

Burada amaç profesyonel benchmark altyapısı kurmak değildir. Öğrencinin tek ölçüm yerine tekrar ölçümü daha güvenilir bir deney alışkanlığı olarak görmesi yeterlidir.

15 Alıştırma — doubling deneyi

Aşağıdaki fonksiyon doğrusal miktarda iş yapar. Her veri boyutunu birkaç kez ölçüp medyan süreyi kaydedin. n yaklaşık iki katına çıktığında sürenin nasıl değiştiğini gözlemleyin.

#| exercise: hafta11-scaling
#| completion: false
#| persist: true
from statistics import median
from time import perf_counter


def work(n):
    total = 0
    for i in range(n):
        total += i
    return total


def measure(n, repeats=5):
    times = []
    for _ in range(repeats):
        start = perf_counter()
        work(n)
        times.append(perf_counter() - start)
    return median(times)

sizes = [20000, 40000, 80000, 160000]
results = []

for n in sizes:
    results.append((n, measure(n)))

for n, elapsed in results:
    print(n, elapsed)

Bu etkinlikte oranların tam 2.0 olması beklenmez. Yorumunuz şu düzeyde olmalıdır: veri boyutu iki katına çıktığında medyan süre yaklaşık iki kat büyüme eğilimi gösteriyor mu?

15.1 Doubling oranını görünür kılın

#| edit: false
#| completion: false
previous = None

for n, elapsed in results:
    if previous is None:
        print(n, "oran: -")
    else:
        ratio = elapsed / previous if previous > 0 else float("inf")
        print(n, "oran:", round(ratio, 2))
    previous = elapsed

Bu oran bir ispat değildir; sadece ölçeklenme davranışını gözlemlemeye yardımcı olur.

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

Aşağıdaki örnek küçük tutulmuştur; tarayıcınızda gereksiz uzun hesaplama yapılmasını istemiyoruz.

#| edit: false
#| completion: false
from statistics import median
from time import perf_counter


def insertion_sort(values):
    values = values.copy()
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1
        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1
        values[j + 1] = current
    return values


def measure_call(fn, repeats=5):
    times = []
    for _ in range(repeats):
        start = perf_counter()
        fn()
        times.append(perf_counter() - start)
    return median(times)

for n in [100, 250, 500]:
    data = list(range(n, 0, -1))

    insertion_time = measure_call(lambda: insertion_sort(data))
    builtin_time = measure_call(lambda: sorted(data))

    print(n, "insertion:", insertion_time, "sorted:", builtin_time)

Amaç “Python her bilgisayarda şu kadar kat hızlı” demek değildir. Amaç, gerçek uygulamada yerleşik sıralama araçlarının neden tercih edildiğini gözlemlemektir.

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) sezgisi 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) sezgisi"]
    A --> I{"Temel iç içe karşılaştırma mı?"}
    I -- Evet --> J["O(n²) riski"]

Bu şema bir karar algoritması değildir; dönem boyunca gördüğümüz maliyet dilini 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.

liste üzerinde tekrar tekrar doğrusal arama pahalı olabilir,
set daha doğal bir yapı olabilir.

18.3 Senaryo 3

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

ikili arama veya uygun indeksli yapı anlamlı 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) sezgisi, yaklaşık log n katman ve her katmanda toplam n kadar iş fikriyle anlaşılabilir.
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çüm yerine tekrarlar, medyan gibi basit özetler ve farklı veri boyutları daha anlamlıdır.
Doubling deneyleri veri boyutu arttıkça çalışma süresindeki eğilimi gözlemlemeye yardımcı olur.
Veri yapısı oluşturma maliyeti ile yapı üzerindeki tekrar eden işlemler birlikte düşünülmelidir.

20 Kendinizi kontrol edin

O(n) ile O(n²) arasında veri iki katına çıktığında nasıl bir büyüme farkı beklenir?
O(n log n) büyümesini “katman sayısı × her katmandaki toplam iş” fikriyle açıklayın.
Neden tek bir milisaniye ölçümü algoritmik karmaşıklığı kanıtlamaz?
Listeyi kümeye dönüştürmenin maliyeti neden toplam kararın parçasıdır?
İkili aramanın O(log n) davranışını yarıya indirme fikriyle açıklayın.
Performans deneyinde veri hazırlığını ölçüm dışında tutmak neden yararlı olabilir?
Tek ölçüm yerine medyan tekrar ölçümü kullanmak ne kazandırır?

1 Bu hafta neleri yapabilmelisiniz?

2 Big-O neyi anlatır?

3 Büyüme tablosu

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

5 Sabit çarpan ile büyüme sınıfı aynı şey değildir

6 İşlem saymak

7 İkili aramada işlem sayısı

8 O(n²) davranışını görünür kılma

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

10 timeit ile küçük deney

11 Kurulum maliyetini ayırmak

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

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

14 Tek ölçüm yerine tekrarlar

15 Alıştırma — doubling deneyi

15.1 Doubling oranını görünür kılın

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

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

18 Kısa karar örnekleri

18.1 Senaryo 1

18.2 Senaryo 2

18.3 Senaryo 3

19 Bölüm özeti

20 Kendinizi kontrol edin

10 `timeit` ile küçük deney

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