COMPUTER ENGINEER

← BlogDATA STRUCTURES / ALGORITHMSPython örnek paketi ↓

Bellek ve özyineleme · 06 / 53

Stack, heap, pointer ve referans

Anla → iz sür → uygula → gerekçelendir

3 dk okuma · uygulama için ayrıca zaman ayır

Çağrı stack'i fonksiyon çerçevelerini, dönüş bilgilerini ve bazı yerel değerleri taşır. Heap, yaşam süresi çağrı sınırını aşabilen dinamik nesnelerin alanıdır. “Yerel değişkenlerin hepsi stack'te, nesnelerin hepsi heap'te” farklı dil/runtime'larda doğru bir evrensel kural değildir: optimizasyon, escape analysis ve değer türleri yerleşimi değiştirebilir.

C pointer'ı adres değeridir; dereference o adresin gösterdiği veriye ulaşır. Geçersiz, serbest bırakılmış veya sınır dışı adrese erişim undefined behavior yaratabilir. Referans bir nesneye erişim bağını temsil eder; Python değişkenleri nesneye bağlanan isimlerdir. C# value type ataması değer kopyalar; reference type ataması genellikle aynı nesne referansını kopyalar. Struct'ın nerede durduğu içinde bulunduğu yapıya bağlıdır.

Aliasing, iki yolun aynı nesneyi göstermesidir. Shallow copy yalnız dış kabuğu kopyalar; iç mutable nesneler paylaşılır. Garbage collector erişilemeyen nesneleri yönetir, dosya/socket gibi kaynakların zamanında kapanmasını garanti eden genel bir araç değildir. Ownership, RAII ve IDisposable yaşam döngüsü sözleşmeleri kurar. Heap veri yapısı ile heap bellek bölgesi farklı kavramlardır.

Ömür, sahiplik ve gerçek adres farkı

C'de int *p bir adres tutar; *p işaret edilen değere erişir. Yerel değişkenin adresini döndürmek, değişkenin ömrü bitince dangling pointer üretir. free sonrası başka alias'ların var olması use-after-free riskidir. “Pointer hâlâ aynı sayıyı gösteriyor” geçerli erişim kanıtı değildir. Null, dangling ve out-of-bounds farklı hata sınıflarıdır.

C# reference type değerleri nesneye reference taşır. Value type ataması normalde değeri kopyalar, fakat struct içindeki reference field aynı nesneyi paylaşabilir. List<T> kapasitesi büyüyünce iç array değişir; bunu programcının elle free yapması gerekmez. Span<T> ve ref struct ömür kuralları managed dünyada da önemlidir. Dosya veya socket'in kapatılmasını GC zamanına bırakmak doğru resource yönetimi değildir; using/IDisposable deterministik temizliği sağlar.

Python'da isim bağlaması nesneye reference verir. b=a yeni liste üretmez; b=a.copy() yalnız outer listeyi kopyalar. İçteki mutable elemanlar paylaşılır. Deep copy'nin maliyeti ve döngülü graph davranışı ayrı değerlendirilir. Her şeyi deep copy yapmak alias problemini otomatik iyi tasarıma dönüştürmez.

Temel: Shallow copy'de iç listeyi değiştirince iki outer listede ne görüldüğünü çiz. Orta: Bir ownership graph üzerinde hangi node'ların paylaşılacağını belirle. İleri: Immutable persistent yapı ile snapshot oluştur; versionların ömrü bitince reclaim politikasını açıklayıp aynı adresin yeniden kullanımını tartış.

Adım adım iz sürme

a=[[1],[2]]; b=a.copy(); b[0].append(9) sonrası a[0] da [1,9] olur. Dış liste farklı, iç liste aynıdır.

Maliyet ve varsayımlar

Shallow copy n referans için Θ(n); deep copy erişilen nesne grafının büyüklüğüne bağlıdır. Pointer takibi cache miss yaratabilir.

Çalıştırılabilir örnek

Python 3 ile çalıştır. Assert küçük bir örneği denetler; genel doğruluk ispatı değildir. Bazı ileri örnekler özellikle küçük model veya referans oracle'dır; tam üretim uygulaması değildir.

Python 3
a = [[1], [2]]
b = a.copy()
b[0].append(9)
assert a[0] == [1, 9]
assert a is not b and a[0] is b[0]

KAVRADIĞINI KONTROL ET

Sıra sende

“GC varsa memory leak olmaz” doğru mu?

Çözümün mantığını göster

Hayır. Kullanılmayan büyük nesneye cache/event handler üzerinden referans tutuluyorsa erişilebilir kalır ve toplanmaz. Kaynak sızıntıları da ayrı konudur.

Bir adım ileri

  1. Örneği değiştirmeden önce girdi sözleşmesini ve invariantı yaz.
  2. Uygun olan boş, sınır, tekrar ve adversarial girdileri ekle. Basit bir oracle ile karşılaştır.
  3. Belirtilen modelde maliyeti çıkar; farklı girdi büyüklüklerini ölç ve farkları gerekçelendir.

Temel kaynaklar ve ders notları

Bu eğitimde özgün anlatım kullanıldı; aşağıdaki kaynaklar ispatlar ve ileri okumalar sunar. Bağlantılar daha geniş ders modülünü kapsayabilir.

Pat Morin · Open Data Structures ↗
İlerlemeden önce alıştırmayı çöz.