Statik/dinamik diziler ve cache locality | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython örnek paketi ↓

Dizi, indeksle erişimi adres hesabına çevirir: taban + i·elemanBoyutu. Sabit boyutlu eleman temsili ve geçerli indeks varsayımında O(1) erişim sağlanır. Python listesi nesnelerin kendisini değil referanslarını tutan dinamik bir dizidir; referanslar yan yana olsa da nesneler başka yerlerde olabilir.

Ortaya ekleme/silme, sonraki elemanları kaydırır. Sonuna ekleme kapasite varken ucuzdur; kapasite dolunca yeni alan ayırıp kopyalamak gerekir. Size kullanılan, capacity ayrılan yer sayısıdır. Çok erken küçültüp yeniden büyütmek thrashing yaratır; büyütme/küçültme eşiklerini ayır.

Ardışık tarama CPU cache ve prefetch için elverişlidir. Linked list'in O(1) eklemesi yalnız ekleme noktası zaten eldeyse geçerlidir; noktayı aramak O(n) olabilir. Sık indeks erişimi olan işte diziyi, sürekli bilinen düğüm çevresinde bağlantı değişimi olan işte listeyi değerlendir. Dilin hazır koleksiyonunun gerçek sözleşmesini öğren.

Adım adım iz sürme

[10,20,30,40] dizisine indeks 1'+'’de 15 ekle: 40,30,20 sağa kayar; sonuç [10,15,20,30,40].

Maliyet ve varsayımlar

İndeks O(1), tarama Θ(n), ortada ekleme Θ(n), append amortize O(1).

Ç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 = [10, 20, 30, 40]
a.insert(1, 15)
assert a == [10, 15, 20, 30, 40]
# Repeated pop(0) shifts the remaining references.

KAVRADIĞINI KONTROL ET

Sıra sende

Her tur pop(0) ile bütün listeyi boşaltmanın toplam maliyeti?

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

(n−1)+(n−2)+…+0 kaydırma ⇒ Θ(n²). FIFO için deque.popleft kullan.

Bir adım ileri

Örneği değiştirmeden önce girdi sözleşmesini ve invariantı yaz.
Uygun olan boş, sınır, tekrar ve adversarial girdileri ekle. Basit bir oracle ile karşılaştır.
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.

RasimAtaberkŞahin