Analizi
Bu derste oyunun haritası 🗺️
- Bilimsel yöntem: tahmin, deney, doğrulama
- Gözlem: süre ölçmek, iki katına çıkarma deneyi doubling test
- Matematiksel model: maliyet × sıklık, ~ gösterimi tilde
- Büyüme mertebeleri: 1, lg N, N, N lg N, N², N³, 2ᴺ order of growth
- Algoritmalar teorisi: en iyi/en kötü durum, Büyük-O Big-O
- Bellek: bir nesne kaç bayt?
- ⚠️ Tuzaklar: önbellek, JIT, ölçüm hataları
…“Oyunda 500 yerine 2000 düşman olursa ne olur?” sorusuna kodu çalıştırmadan, sayıyla cevap verebileceksiniz.
Oyununuzda 100 düşman var ve her düşman diğer her düşmanla çarpışma kontrolü yapıyor. Oyun 60 FPS’te akıcı.
Düşman sayısını 200’e çıkardınız. Çarpışma kontrolleri ne kadar uzun sürer?
A) 2 katı · B) 4 katı · C) 100 katı · D) değişmez
Cevap: ~4 katı. Çiftlerin sayısı N²/2 ile büyür: N iki katına → N² dört katına. 1000 düşmanda 100 katı! 😱
Oyun geliştirici neden umursamalı?
Mini sözlük
| running time | çalışma süresi | Programın bir girdi için harcadığı süre |
| order of growth | büyüme mertebesi | N büyüdükçe sürenin nasıl büyüdüğü: N, N², … |
| doubling test | iki katına çıkarma deneyi | N’i 2 katına çıkarıp sürenin kaç katına çıktığını ölçmek |
| power law | kuvvet yasası | T(N) = a · Nᵇ biçiminde bir ilişki |
| tilde notation | ~ gösterimi | Baskın terimi (katsayısıyla) tutup gerisini atmak |
| Big-O | Büyük-O | Üst sınır gösterimi (sabitleri de atar) |
| best / worst / average case | en iyi / en kötü / ortalama | Hangi girdide ne kadar sürer? |
| profiler | profil çıkarıcı | Programın zamanını nerede harcadığını gösteren araç |
- bilimsel yöntem
- gözlem: ölçmek
- matematiksel model
- büyüme mertebeleri
- algoritmalar teorisi
- bellek
- tuzaklar
Programlara bir fizikçi gibi bakmak
- Gözlemle: programı farklı N’lerle çalıştır, süreyi ölç.
- Hipotez kur: gözlemlere uyan bir model öner (ör. süre ≈ a · N²).
- Tahmin et: modelle daha büyük bir N için süreyi hesapla.
- Doğrula: o N ile gerçekten çalıştır; tahmin tuttu mu?
- Tekrarla: tutmadıysa modeli düzelt.
Önemli fark: doğa bize sunulur, ama programları biz yazarız → deneyleri tekrar tekrar, ucuza yapabiliriz.
- bilimsel yöntem
- gözlem: ölçmek
- matematiksel model
- büyüme mertebeleri
- algoritmalar teorisi
- bellek
- tuzaklar
Süre nasıl ölçülür? Kronometre
🎒 f"…{x:.2f}" (Python) ve $"…{x:F2}" (C#): değişkeni metnin içine yerleştir, 2 basamakla yaz (string interpolation).
🧪 İki katına çıkarma deneyi doubling test
📐 Kuvvet yasası ve log-log grafiği
Pek çok algoritmada süre şu biçimdedir: \( T(N) = a \cdot N^b \)
- İki tarafın logaritmasını alırsak: \( \lg T = b \cdot \lg N + \lg a \) → bir doğru! Eğimi b.
- N’i ikiye katlarsak: \( \frac{T(2N)}{T(N)} = \frac{a (2N)^b}{a N^b} = 2^b \) → oran 4 ise b = 2, oran 8 ise b = 3.
- b’yi bulunca a’yı da bir ölçümden hesaplarız → artık her N için tahmin yapabiliriz.
| oran | b | büyüme |
|---|---|---|
| ~1 | 0 | sabit / log |
| ~2 | 1 | doğrusal |
| ~2,1–2,3 | ~1,1 | N lg N |
| ~4 | 2 | karesel |
| ~8 | 3 | kübik |
🔗 Başka gözle: etkileşimli anlatımlar ve yazılar
Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.
- bilimsel yöntem
- gözlem: ölçmek
- matematiksel model
- büyüme mertebeleri
- algoritmalar teorisi
- bellek
- tuzaklar
Knuth’un formülü: maliyet × sıklık
Programın toplam süresi = her komutun maliyeti × o komutun kaç kez çalıştığı (sıklık), hepsinin toplamı.
- Maliyet: makineye, derleyiciye bağlı (bir toplama, bir karşılaştırma…)
- Sıklık: algoritmaya ve girdiye bağlı → bunu hesaplayabiliriz!
Örnek problem: ThreeSum — N sayı arasından toplamı tam 0 olan kaç üçlü var?
🎮 Oyun versiyonu: Kart oyununda +/− değerli kartlardan “toplam enerjisi 0 olan üç kartlık kombo” kaç tane?
Hangi satır kaç kez çalışır?
🎒 Ön bilgi: kaç çift, kaç üçlü?
for j in range(i + 1, n): j hep i’den büyük → her çift bir kez sayılır.
- N nesneden çift sayısı: \( \binom{N}{2} = \frac{N(N-1)}{2} \sim \frac{N^2}{2} \)
- N nesneden üçlü sayısı: \( \binom{N}{3} = \frac{N(N-1)(N-2)}{6} \sim \frac{N^3}{6} \)
\( \binom{N}{2} \) “N’den 2 seç” diye okunur (kombinasyon). Sıra önemsiz: (Ork, Goblin) ile (Goblin, Ork) aynı çift.
~ gösterimi: küçük terimleri at tilde notation
\( \frac{N(N-1)(N-2)}{6} = \frac{N^3}{6} - \frac{N^2}{2} + \frac{N}{3} \)
| N | N³/6 | tam değer | fark |
|---|---|---|---|
| 10 | 167 | 120 | %28 |
| 100 | 166.667 | 161.700 | %3 |
| 1.000 | 166,7 milyon | 166,2 milyon | %0,3 |
N büyüdükçe baskın terim (N³/6) her şeyi belirler. Yazarız: ~N³/6 (“yaklaşık N³/6”).
Hipotezimiz (b = 3, oran 8) ile matematiksel model aynı şeyi söylüyor ✔ — bilimsel yöntem!
🎬 Ara: Büyük-O, 100 saniyede
Big-O Notation in 100 Seconds
Fireship · 1 dk 39 sn · YouTube’da aç
Bu bölümdeki tilde (~) ve büyüme mertebesi fikrinin en kısa özeti. Derste izleyip “hangi slayttaki demoya karşılık geliyor?” diye eşleştirin.
tick() yaklaşık kaç kez çağrılır?for i in range(N):
for j in range(N):
tick()range(i + 1, N) olsaydı ~N²/2 olurdu. Sabit çarpan (½) büyüme mertebesini değiştirmez ama gerçek süreyi değiştirir.- bilimsel yöntem
- gözlem: ölçmek
- matematiksel model
- büyüme mertebeleri
- algoritmalar teorisi
- bellek
- tuzaklar
Birkaç fonksiyon her şeyi açıklıyor
| büyüme | adı | kod kalıbı | 🎮 örnek | T(2N)/T(N) |
|---|---|---|---|---|
| 1 | sabit | a[i] = x | bir değişken güncelle | 1 |
| lg N | logaritmik | yarıya böl | ikili arama, BST | ~1 |
| N | doğrusal | tek döngü | tüm düşmanları güncelle | 2 |
| N lg N | doğrusal-log. | böl ve fethet | sıralama (mergesort) | ~2 |
| N² | karesel | iki iç içe döngü | tüm çiftlerde çarpışma | 4 |
| N³ | kübik | üç iç içe döngü | ThreeSum | 8 |
| 2ᴺ | üstel | tüm alt kümeler | en iyi ekipman kombinasyonu | 2ᴺ (!) |
İlk dördü “iyi” sınıf: büyük problemlere ölçeklenir. Karesel ve kübik ancak küçük N’de. Üstel: N = 50’de bile evrenin ömrü yetmez.
🎮 Kare bütçesi: 60 FPS’te en fazla kaç N?
🔗 Ayrıntısı: Y18 · YZ Performansı (zaman dilimleme ve YZ LOD’u) sunumunda.
📜 Satranç tahtası ve buğday taneleri
Efsaneye göre satrancı icat eden bilge, hükümdardan ödül olarak şunu ister: ilk kareye 1 buğday tanesi, ikinciye 2, üçüncüye 4… her kareye bir öncekinin iki katı.
Hükümdar güler: “Bu kadar mı?” 64. kareye gelince toplam: \( 2^{64} - 1 \approx 1{,}8 \times 10^{19} \) tane — dünyanın yüzlerce yıllık buğday üretimi! 🌾
Envanterde 30 eşya var; her birini “giy/giyme” diye deneyerek en güçlü kombinasyonu arıyorsunuz: \( 2^{30} \approx \) 1 milyar deneme.
40 eşya → 1 trilyon. 60 eşya → imkânsız. Çözüm: daha akıllı algoritmalar (açgözlü yaklaşım, dinamik programlama) ya da yaklaşık çözümler.
for i in range(N):
j = 1
while j < N:
tick()
j = j * 2🧪 Kod laboratuvarı: kendi kodunun büyümesini ölç
- Şu anki kod: oran ve b ne çıkar?
- İç döngüyü
j = 0’dan başlat. Sayı nasıl değişti, b değişti mi? - İç döngüyü
for (let j = 1; j < N; j *= 2)yap. - Üçüncü bir iç içe döngü ekle. · Bonus: tek döngünün içine 10 turluk sabit bir döngü koy — b değişir mi?
Daha iyi algoritma, daha hızlı bilgisayardan iyidir
ThreeSum’u daha akıllı yapabilir miyiz?
- Diziyi sırala: N lg N (sıralama dersleri)
- Her (i, j) çifti için
−(a[i] + a[j])değerini ikili aramayla ara (arama dersi): N² çift × lg N - Toplam: ~N² lg N
| N | N³/6 (kaba kuvvet) | N² lg N |
|---|---|---|
| 1.000 | ~2 sn* | ~0,01 sn |
| 8.000 | ~17 dk | ~1 sn |
| 1 milyon | ~5 yıl | ~6 saat |
* kabaca, hızlı bir makinede. Hızlı bilgisayar sabiti küçültür; iyi algoritma üssü küçültür.
- bilimsel yöntem
- gözlem: ölçmek
- matematiksel model
- büyüme mertebeleri
- algoritmalar teorisi
- bellek
- tuzaklar
Girdiye bağlı: en iyi, en kötü, ortalama
- En kötü durum worst case: hiçbir girdi bundan uzun sürmez → garanti. Oyunlarda en önemlisi: kare asla takılmasın!
- Ortalama durum average case: “tipik” girdilerde beklenen süre (girdinin rastgele olduğu varsayımıyla)
- En iyi durum best case: en şanslı girdi — genelde pek bir şey söylemez
En iyi: aranan ilk eleman → 1 · Ortalama: ~N/2 · En kötü: N (ya da yok).
Oyun tasarımında “ortalama iyi ama bazen çok kötü” algoritmalar, ara sıra gelen takılmalara (frame spike) yol açar — oyuncunun en çok fark ettiği şey!
Büyük-O, Büyük-Omega, Büyük-Teta Big-O · Ω · Θ
| gösterim | anlamı | benzetme |
|---|---|---|
| Θ(N²) | tam olarak N² gibi büyür | “yolculuk ~2 saat” |
| O(N²) | en fazla N² gibi (üst sınır) | “en fazla 2 saat” |
| Ω(N²) | en az N² gibi (alt sınır) | “en az 2 saat” |
| ~N²/2 | yaklaşık N²/2 (katsayı dahil) | “1 saat 58 dakika” |
İş ilanlarında ve mülakatlarda Büyük-O sorulur. Algoritma analizinde ise çoğu zaman ~ (tilde) kullanılır, çünkü sabiti korur: selection sort (~N²/2) ile insertion sort (~N²/4) ikisi de O(N²) ama biri iki kat hızlı.
Dikkat: “O(N²)” teknik olarak bir üst sınırdır; günlük kullanımda çoğu zaman Θ anlamında söylenir.
- bilimsel yöntem
- gözlem: ölçmek
- matematiksel model
- büyüme mertebeleri
- algoritmalar teorisi
- bellek
- tuzaklar
Temel türlerin boyutları
| tür (C#) | bayt |
|---|---|
bool / byte | 1 |
char / short | 2 |
int / float | 4 |
long / double | 8 |
| referans (64-bit) | 8 |
Vector3 (struct) | 12 |
nesne başlığı (class) | ~16 |
Python’da her şey nesnedir: küçük bir int bile ~28 bayt, listedeki her eleman için +8 bayt referans.
JavaScript’te sayılar 8 baytlık ondalıklı sayıdır (motor bazen tamsayıları sıkıştırır). Bellek kritikse: Int32Array, Float32Array.
Dizi: eleman sayısı × eleman boyutu + küçük bir başlık. Nesne: başlık + alanlar, 8’in katına yuvarlanır (hizalama padding).
1 milyon düşman ne kadar yer kaplar?
- bilimsel yöntem
- gözlem: ölçmek
- matematiksel model
- büyüme mertebeleri
- algoritmalar teorisi
- bellek
- tuzaklar
⚠️ Ölçerken dikkat
- Isınma JIT warm-up: C# ve JS kodu ilk çalıştırmalarda derlenir → ilk ölçümler yavaş. Birkaç kez çalıştırıp en iyisini/ortancayı alın.
- Çöp toplayıcı: ölçümün ortasında GC çalışırsa süre fırlar.
- Önbellek: küçük N önbelleğe sığar, büyük N sığmaz → oran birden değişebilir.
- Arka plan: tarayıcı sekmeleri, güç tasarrufu modu, ısınan laptop.
- Girdi: rastgele girdi ≠ gerçek oyun verisi (çoğu zaman neredeyse sıralı!).
Derin hikâye: GTA Online’ın 6 dakikalık yükleme ekranı (2021)
- GTA Online’ın PC sürümü yıllarca yaklaşık 6 dakikada açılıyordu. Kaynak koduna erişimi olmayan bir oyuncu, takma adı t0st, 2021’de profilleyici ve tersine mühendislik araçlarıyla nedeni aradı.
- Sebep 1: Yaklaşık 10 MB’lık, 63.000 eşyalık bir JSON dosyası ayrıştırılırken her küçük okumada
sscanf, metnin tamamının uzunluğunu (strlen) yeniden hesaplıyordu: farkında olmadan O(n²). - Sebep 2: Her eşya listeye eklenmeden önce, listenin baştan sona taranmasıyla “zaten var mı?” diye kontrol ediliyordu: 63.000 eşya için yaklaşık 2 milyar karşılaştırma (yine O(n²)). Üstelik eşyaların hepsi zaten benzersizdi.
- İki düzeltmeyle yükleme süresi 6 dakikadan 1 dakika 50 saniyeye indi (%69,4 azalma). Rockstar düzeltmeyi oyuna ekledi ve t0st’a hata ödül programından 10.000 dolar verdi.
Kaynak: t0st: How I cut GTA Online loading times by 70% · bit-tech
🧰 Kütüphaneler ve araçlar
| ad | platform | ne yapar / sınırları | nasıl eklenir |
|---|---|---|---|
| BenchmarkDotNet | C# / .NET | Isınma, tekrar, istatistik ve bellek ayırma ölçümüyle güvenilir mikro ölçüm. Unity içinde değil, ayrı bir .NET projesinde çalışır. | NuGet: BenchmarkDotNet |
| Unity Performance Testing | Unity | Test Framework içinde ölçüm: Measure.Method, Measure.Frames; sonuçları sürümler arasında karşılaştırma. | Package Manager: com.unity.test-framework.performance |
| Unity Profiler | Unity | Kare bazında süre ve bellek ayırma; hedef cihaza bağlanarak ölçüm. | Window → Analysis → Profiler |
| timeit · cProfile | Python | Küçük kod parçalarını tekrar tekrar ölçme; fonksiyon bazında profil. | standart kütüphane |
| Tinybench | JavaScript | Tarayıcı ve Node için küçük, modern ölçüm kütüphanesi. | npm install tinybench |
🧩 Ölçerken dikkat
- Çift-boyut deneyi: N’yi 1.000, 2.000, 4.000… diye ikiye katlayın, süre oranına bakın: ~2 ise doğrusal, ~4 ise karesel, ~2,1 ise N log N.
- Isınma: ilk çağrılar (JIT derleme, önbellek) yavaştır; ilk ölçümleri atın.
- Release/IL2CPP derlemesi ve hedef cihaz: editörde ölçmek yanıltır.
- Bellek ayırma da maliyettir: Unity’de her karede “GC Alloc” sıfıra yakın olmalı.
- Tek sayı değil, dağılım: en kötü %1 (takılmalar) ortalamadan önemlidir.
List.Contains,IndexOf,Remove(item): liste taraması.- Döngüde
string +=: her seferinde yeni metin (StringBuilder kullanın). - LINQ zincirleri (
Where().ToList()) her karede: ayırma + tarama. GameObject.Find,FindObjectsOfType: bütün sahneyi tarar.
🤖 Bu konuyu bir YZ kod asistanıyla yazarken
- Asistanın “bu O(n log n)” iddiasına ölçmeden inanmak
- Debug derlemesinde ya da editörde ölçüp karar vermek
- Tek bir girdi boyutuyla sonuç çıkarmak
- Döngü içindeki Contains/IndexOf/string birleştirmeyi gözden kaçırmak
“C# (.NET 8). Aşağıdaki fonksiyonun zaman karmaşıklığını satır satır açıkla; döngü içindeki gizli O(n) çağrıları (Contains, IndexOf, Remove, string birleştirme, LINQ) işaretle ve daha iyi veri yapısı öner. Sonra N = 1.000’den 64.000’e ikişer katlanan bir BenchmarkDotNet deneyi yaz; her satırda süreyi ve bir önceki süreye oranı yazdırsın.”
- Kodun karmaşıklığını satır satır açıklatın
- Çift-boyut deneyini (N, 2N, 4N…) ve oranları isteyin
- Gizli doğrusal çağrıları işaretletin
- Release derlemesinde ölçmeyi hatırlatın
🚀 Proje ve araştırma önerileri
- [kolay] Çift-boyut deneyi — Üç fonksiyon (doğrusal, karesel, N log N) yazıp N’yi ikiye katlayarak süre oranlarını tablolayın.
- [kolay] Gizli O(n²) avı — GTA hikâyesindeki hatanın küçük bir kopyasını yazın (döngüde liste taraması), HashSet ile düzeltip ölçün.
- [orta] Unity performans testi — Bir yapay zekâ fonksiyonunuz için Performance Testing paketiyle otomatik ölçüm testi; sürümler arasında karşılaştırın.
- [araştırma] Önbellek etkisi — Aynı sayıda elemanı dizi ve bağlı liste üzerinde dolaşıp süreleri karşılaştırın; büyük-O’nun anlatmadığı farkı açıklayın.
📄 Akademik okumalar ve kaynaklar
Asimptotik gösterimin bugünkü anlamı.
Hesaplama karmaşıklığı alanının başlangıcı.
Çift-boyut deneyi ve bilimsel yöntem.
Neler öğrendik? 🎒
- Bilimsel yöntem: gözlemle, hipotez kur, tahmin et, doğrula.
- İki katına çıkarma deneyi: oran = 2ᵇ, b = lg oran.
- Kuvvet yasası: T(N) = a·Nᵇ → log-log grafikte doğru.
- Model: maliyet × sıklık; en sık işlemi say; ~ ile sadeleştir.
- Büyüme mertebeleri: 1, lg N, N, N lg N, N², N³, 2ᴺ.
- 🎮 Kare bütçesi: 16,6 ms’de kaç N?
- En kötü / ortalama; Büyük-O, Θ, Ω, ~.
- Bellek: struct dizisi vs nesneler vs bağlı liste.
- ⚠️ Ölçüm tuzakları; Profiler kullan.
Alıştırmalar 🏋️
- Laboratuvarda
while (N > 1) { N = Math.floor(N / 2); }döngüsünün büyümesini ölçün. Neden oran ~1? - p5.js’te N parçacıklık bir sahne yapın ve her karede tüm çiftler için mesafe hesaplayın. FPS’in 30’un altına düştüğü N’i bulun. N’i iki katına çıkarınca FPS ne oluyor?
- Unity Profiler ile bir sahnenin en pahalı 3 fonksiyonunu bulun. Hangisi kare sayısına (N’e) bağlı büyüyor?
- TwoSum: N sayı arasında toplamı 0 olan kaç çift var? Önce ~N²/2 kaba kuvvet, sonra sırala + ikili arama ile N lg N sürümü yazın; iki katına çıkarma deneyiyle karşılaştırın.
- Kendi oyununuzdaki bir varlığın (düşman, mermi) C# sınıfının kaç bayt tuttuğunu tahmin edin. 10.000 tanesi kaç MB?
- 🤖 Bir YZ asistanına yazdırdığınız bir fonksiyonun büyüme mertebesini sorun, sonra laboratuvarda ölçerek doğrulayın. Uyuştu mu?
🎮 Bu sunumdaki oyunlar
Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.
Kaynaklar: videolar 🎬
Big-O Notation in 100 SecondsFireship
Big-O notation in 5 minutesMichael Sambol
Big O NotationHackerRank
Introduction to Big O Notation and Time ComplexityCS Dojo
Learn Big O notation in 6 minutesBro Code
Getting Sorted & Big O NotationComputerphile
Complete Beginner’s Guide to Big O NotationColt Steele