Listeler

Sayaç “kaç” sorusunu tek bir sayıyla yanıtladı. Kütüphanenin ikinci sorusu bir sayıyla yanıtlanmaz: popüler bir kitabı bekleyenler kimlerdir ve hangi sırada. Bekleme listesinde sıranın kendisi bilginin bir parçasıdır; depo onu koruyacaksa her üyeyi ayrı ayrı ve konumuyla birlikte tutmak zorundadır.

Liste tek bir yapıdır, iki ayrı kullanımı vardır. Kuyruk bir uçtan eklenip öteki uçtan çıkarıldığında ortaya çıkar: bekleme listesi böyledir, ilk isteyen ilk alır. Yığıt aynı uçtan eklenip aynı uçtan çıkarıldığında ortaya çıkar: görevlinin son işlemini geri alması böyledir. Depo açısından fark yapıda değil, hangi ucun seçildiğindedir. Asıl soru şudur: iki uca da sabit adımda erişmek bellekte kaç bayta mal olur.

Aynı İş Yükü, Üç Gerçekleştirim

BY1: bekleme listesine 20.000 istek sondan eklenir, her dördüncü istekten sonra baştan bir karşılama yapılır (5.000 çıkarma) ve her kırkıncı istekte bir öncelikli istek başa alınır (500 ekleme); toplam 25.500 işlem. BY2: dizi yuvası 8 bayt, bağlı düğümün ek maliyeti 24 bayttır (önceki ve sonraki göstergeler ile düğüm başlığı), yapı başına üstveri 56 bayttır. BY3: halka tampon 1.024 yuvayla başlar ve dolduğunda kapasitesi iki katına çıkar; kopyalama adımları sayılır.

// bellek/liste.mjs — ayni bekleme listesi is yuku uc gerceklestirimde. Adim ve bayt
// sayaclari yapinin kendi icindedir; is yuku belirlenimlidir.
const USTVERI = 56, YUVA = 8, DUGUM_EK = 24;   // BY2

class DiziListe {                              // bitisik dizi: bastan islem kaydirma ister
  #a = []; adim = 0;
  sonaEkle(v) { this.adim += 1; this.#a.push(v); }
  basaEkle(v) { this.adim += this.#a.length + 1; this.#a.unshift(v); }
  bastanCikar() { this.adim += this.#a.length; return this.#a.shift(); }
  get uzunluk() { return this.#a.length; }
  get bayt() { return USTVERI + this.#a.reduce((t, v) => t + Buffer.byteLength(v) + YUVA, 0); }
  sira(v) { let n = 0; for (const x of this.#a) { n += 1; if (x === v) return n; } return -1; }
}

class BagliListe {                             // iki uctan da tek adim; dugum basina ek gosterge
  #bas = null; #son = null; #n = 0; #b = 0; adim = 0;
  #dugum(v) { this.#n += 1; this.#b += Buffer.byteLength(v) + YUVA + DUGUM_EK; return { v, on: null, ar: null }; }
  sonaEkle(v) { this.adim += 1; const d = this.#dugum(v);
    d.on = this.#son; if (this.#son) this.#son.ar = d; else this.#bas = d; this.#son = d; }
  basaEkle(v) { this.adim += 1; const d = this.#dugum(v);
    d.ar = this.#bas; if (this.#bas) this.#bas.on = d; else this.#son = d; this.#bas = d; }
  bastanCikar() { this.adim += 1; const d = this.#bas; if (!d) return undefined;
    this.#bas = d.ar; if (this.#bas) this.#bas.on = null; else this.#son = null;
    this.#n -= 1; this.#b -= Buffer.byteLength(d.v) + YUVA + DUGUM_EK; return d.v; }
  get uzunluk() { return this.#n; }
  get bayt() { return USTVERI + this.#b; }
  sira(v) { let n = 0; for (let d = this.#bas; d; d = d.ar) { n += 1; if (d.v === v) return n; } return -1; }
}

class HalkaTampon {                            // sabit yuva; dolunca kapasite iki katina cikar
  #a; #bas = 0; #n = 0; adim = 0; kopya = 0; buyume = 0;
  constructor(kapasite) { this.#a = new Array(kapasite); }
  #buyut() { if (this.#n < this.#a.length) return;
    const yeni = new Array(this.#a.length * 2);
    for (let i = 0; i < this.#n; i += 1) yeni[i] = this.#a[(this.#bas + i) % this.#a.length];
    this.adim += this.#n; this.kopya += this.#n; this.buyume += 1; this.#a = yeni; this.#bas = 0; }
  sonaEkle(v) { this.#buyut(); this.adim += 1; this.#a[(this.#bas + this.#n) % this.#a.length] = v; this.#n += 1; }
  basaEkle(v) { this.#buyut(); this.adim += 1;
    this.#bas = (this.#bas - 1 + this.#a.length) % this.#a.length; this.#a[this.#bas] = v; this.#n += 1; }
  bastanCikar() { this.adim += 1; if (this.#n === 0) return undefined;
    const v = this.#a[this.#bas]; this.#a[this.#bas] = undefined;
    this.#bas = (this.#bas + 1) % this.#a.length; this.#n -= 1; return v; }
  get uzunluk() { return this.#n; }
  get kapasite() { return this.#a.length; }
  get bayt() { let d = 0;
    for (let i = 0; i < this.#n; i += 1) d += Buffer.byteLength(this.#a[(this.#bas + i) % this.#a.length]);
    return USTVERI + this.#a.length * YUVA + d; }
  sira(v) { for (let i = 0; i < this.#n; i += 1) if (this.#a[(this.#bas + i) % this.#a.length] === v) return i + 1; return -1; }
}

// --- is yuku: 20.000 istek sona, her 4 istekte 1 karsilama bastan, her 40 istekte 1 oncelikli basa
const ISTEK = 20_000;
const deger = (i) => `${10_000 + i}:${40_000 + i * 2}`;
const islem = [];
for (let i = 1; i <= ISTEK; i += 1) {
  islem.push(["sona", deger(i)]);
  if (i % 4 === 0) islem.push(["cikar", null]);
  if (i % 40 === 0) islem.push(["basa", `9${deger(i)}`]);
}
const kosum = (l) => { for (const [k, v] of islem) {
  if (k === "sona") l.sonaEkle(v); else if (k === "basa") l.basaEkle(v); else l.bastanCikar(); } return l; };

const h = new HalkaTampon(1024);
const yapi = [["bitisik dizi", kosum(new DiziListe())], ["bagli dugum", kosum(new BagliListe())],
  ["halka tampon", kosum(h)]];
console.log(`${islem.length} islem (${ISTEK} sona, ${ISTEK / 4} bastan cikarma, ${ISTEK / 40} basa)`);
console.log(`${"yapi".padEnd(15)}${"uzunluk".padStart(9)}${"tutulan bayt".padStart(14)}` +
  `${"giris basina".padStart(13)}${"toplam adim".padStart(13)}${"islem basina".padStart(14)}`);
for (const [ad, l] of yapi)
  console.log(ad.padEnd(15) + String(l.uzunluk).padStart(9) + String(l.bayt).padStart(14) +
    (l.bayt / l.uzunluk).toFixed(1).padStart(13) + String(l.adim).padStart(13) +
    (l.adim / islem.length).toFixed(1).padStart(14));
console.log(`halka tampon: ${h.buyume} buyume, ${h.kopya} kopyalama adimi, kapasite ${h.kapasite}, ` +
  `bos yuva ${h.kapasite - h.uzunluk}`);

const hedef = deger(19_000);
console.log(`\n"${hedef}" kacinci sirada: ` + yapi.map(([ad, l]) => `${ad} -> ${l.sira(hedef)}. sira`).join(", "));

25500 islem (20000 sona, 5000 bastan cikarma, 500 basa)
yapi             uzunluk  tutulan bayt giris basina  toplam adim  islem basina
bitisik dizi       15500        294557         19.0     42662750        1673.0
bagli dugum        15500        666557         43.0        25500           1.0
halka tampon       15500        301629         19.5        40860           1.6
halka tampon: 4 buyume, 15360 kopyalama adimi, kapasite 16384, bos yuva 884

"29000:78000" kacinci sirada: bitisik dizi -> 14500. sira, bagli dugum -> 14500. sira, halka tampon -> 14500. sira

Üç yapı aynı 15.500 kişilik bekleme listesini taşıyor; tuttukları bayt ve harcadıkları adım birbirinden çok uzak. Bitişik dizi giriş başına 19,0 bayt ile en ucuzudur ama baştan yapılan her işlem kalan bütün girişleri kaydırdığı için işlem başına 1.673 adım harcar; 25.500 işlemin toplamı 42,7 milyon adımdır. Bekleme listesinden birinin çağrılması, listedeki herkesin yerinin değişmesi demektir.

Bağlı düğüm bunu tersine çevirir: her işlem tam 1 adım, toplam 25.500. Fiyatı giriş başına 43,0 bayttır — dizi maliyetinin 2,26 katı. Fark yalnız gösterge maliyetidir: her giriş, iki komşu göstergesi ve düğüm başlığı için fazladan 24 bayt taşır. Bir üye kimliğinin kendisi 11 bayt iken onu sıraya bağlamak 24 bayt istiyor; veri kadar yer, verinin yerini tarif etmeye gidiyor.

Halka tampon üçüncü yolu gösteriyor ve bu iş yükünde en iyi alımdır: giriş başına 19,5 bayt — diziden yalnız 0,5 bayt fazla — ve işlem başına 1,6 adım. Bir baş göstergesi tutarak baştan çıkarmayı kaydırma olmaktan çıkarır. Bedeli kapasite yönetimidir: 1.024 yuvayla başlayıp dört kez büyümüş, 15.360 kopyalama adımı harcamış ve sonunda 884 boş yuvayı elde tutuyor. Bağlı düğümün halka tampona göre satın aldığı tek şey o 15.360 adımdır ve fiyatı 364.928 bayttır: adım başına 23,8 bayt. Bu, bekleme listesi için kötü bir alımdır; kararın yönü yapının adıyla değil bu oranla verilir.

Son satır üçünün de ortak sınırını gösteriyor. Belirli bir üyenin kaçıncı sırada olduğu üç yapıda da 14.500. sıradadır ve bulunması için 14.500 giriş gezilir. Liste sırayı tutar ama sıraya göre arama vermez; üyelikten konuma gitmek her durumda taramadır.

Kırpmanın Fiyatı

İkinci kullanım son etkinlik listesidir: her ödünç, iade, uzatma ve rezerv listenin sonuna yazılır ve görevli paneli “son m etkinlik” diye sorar. Bu liste hiç çıkarılmazsa gün boyunca büyür. BY4: gün 43.200 saniyedir ve 60.000 etkinlik üretir; giriş ortalama 24 bayttır. BY5: 2.000 sorgu gelir, istenen m küçük değerlere eğiktir ve tohumu görünür bir üreticiden gelir; kırpılmış liste halka tampon maliyetiyle sayılır.

// bellek/kirpma.mjs — son etkinlik listesi: sinirsiz tutmak ile belli uzunlukta kirpmak.
// Kirpilan liste halka tampon maliyetiyle sayilir: 56 + kapasite*8 + canli deger baytlari.
const USTVERI = 56, YUVA = 8, GUN = 43_200, ETKINLIK = 60_000, SORGU = 2_000, TOHUM = 20240115;
let c = TOHUM;
const rast = () => (c = (c * 1103515245 + 12345) % 2147483648) / 2147483648;

const TUR = ["odunc", "iade", "uzatma", "rezerv"];
const etkinlik = Array.from({ length: ETKINLIK }, (_, i) =>
  `${Math.floor(i * GUN / ETKINLIK)}|${10_000 + (i * 7919) % 20_000}|${TUR[i % 4]}|${100_000 + (i * 4241) % 200_000}`);
const degerBayt = etkinlik.map((e) => Buffer.byteLength(e));
const toplamBayt = degerBayt.reduce((t, x) => t + x, 0);

// sorgu: "son m etkinlik" — kucuk m'ye egik, tohumlu
const sorgu = Array.from({ length: SORGU }, () => 1 + Math.floor(3_000 * rast() ** 2));

console.log(`${ETKINLIK} etkinlik / ${GUN} sn, ornek "${etkinlik[41]}" (${degerBayt[41]} bayt), ` +
  `ortalama ${(toplamBayt / ETKINLIK).toFixed(1)} bayt`);
console.log(`${SORGU} sorgu, en buyuk m ${Math.max(...sorgu)}, ortanca m ${[...sorgu].sort((a, b) => a - b)[SORGU / 2]}`);
console.log(`\n${"sinir".padStart(9)}${"tutulan bayt".padStart(14)}${"dusurulen".padStart(11)}` +
  `${"kapsanan sn".padStart(13)}${"karsilanan sorgu".padStart(18)}${"oran".padStart(8)}`);
for (const k of [100, 1_000, 10_000, ETKINLIK]) {
  const canli = etkinlik.slice(ETKINLIK - k);
  const bayt = USTVERI + k * YUVA + degerBayt.slice(ETKINLIK - k).reduce((t, x) => t + x, 0);
  const kapsam = Number(canli.at(-1).split("|")[0]) - Number(canli[0].split("|")[0]);
  const karsilanan = sorgu.filter((m) => m <= k).length;
  console.log(String(k === ETKINLIK ? "sinirsiz" : k).padStart(9) + String(bayt).padStart(14) +
    String(ETKINLIK - k).padStart(11) + String(kapsam).padStart(13) +
    String(karsilanan).padStart(18) + `%${(100 * karsilanan / SORGU).toFixed(1)}`.padStart(8));
}

60000 etkinlik / 43200 sn, ornek "29|14679|iade|273881" (20 bayt), ortalama 24.0 bayt
2000 sorgu, en buyuk m 2999, ortanca m 752

    sinir  tutulan bayt  dusurulen  kapsanan sn  karsilanan sorgu    oran
      100          3281      59900           71               368   %18.4
     1000         32306      59000          719              1167   %58.4
    10000        322556      50000         7199              2000  %100.0
 sinirsiz       1919625          0        43199              2000  %100.0

Sınırsız liste günü 1.919.625 baytla kapatıyor ve ertesi gün aynı hızla büyümeye devam eder; bir listenin doğal bir durma noktası yoktur. 10.000’lik kırpma aynı 2.000 sorgunun tamamını karşılıyor ve bunu sınırsız listenin %16,8’i kadar bellekle yapıyor: 1,6 MB tasarrufun sorgu tarafında bedeli sıfırdır.

Bedelin nerede olduğunu kapsanan sn sütunu söylüyor. 10.000 giriş yalnız son 7.199 saniyeyi, yani iki saati taşır; sınırsız liste on iki saati taşır. Bu iş yükünde kimse iki saatten geriye sormadığı için kayıp görünmez — ama görünmez olması yok olduğu anlamına gelmez. Sınır 1.000’e çekildiğinde bellek 32.306 bayta iner ve liste yalnız 719 saniyeyi, on iki dakikayı kapsar; sorguların %41,6’sı eksik yanıt alır. 100’lük sınırda kapsam 71 saniyeye, karşılama %18,4’e düşer.

Buradaki asıl uyarı sayıların kendisinde değil, hatanın biçimindedir. Kırpılmış liste “elimde yok” demez; elindeki kadarını verir. 2.400 etkinlik isteyen bir sorgu, 1.000 sınırlı listeden 1.000 kayıt alır ve yanıtı eksik olduğunu bilmeden kullanır. Sınır, bellek bütçesiyle sorgu dağılımının kesiştiği yerde seçilir ve dağılım değiştiğinde sessizce yanlış yanıt üretmeye başlar.

Özet

• Kuyruk ve yığıt ayrı yapılar değildir; aynı listenin hangi ucundan eklenip çıkarıldığıdır. Bekleme listesi kuyruk, görevlinin geri alma dizisi yığıttır.
• Aynı 25.500 işlemde bitişik dizi giriş başına 19,0 bayt tutar ama işlem başına 1.673 adım harcar; bağlı düğüm işlem başına 1 adıma iner ve giriş başına 43,0 bayt ister (2,26 kat).
• Halka tampon ikisinin arasını kapatır: 19,5 bayt ve 1,6 adım. Bağlı düğümün ona göre satın aldığı 15.360 adımın fiyatı 364.928 bayttır — adım başına 23,8 bayt.
• Sıra sorgusu üç yapıda da taramadır: hedef giriş 14.500. sıradadır ve bulunması 14.500 adım ister. Liste sırayı tutar, sıraya göre arama vermez.
• Son etkinlik listesi kırpılmadığında günü 1.919.625 baytla kapatır ve durma noktası yoktur. 10.000’lik sınır belleği %16,8’e indirir ve bu iş yükündeki 2.000 sorgunun tamamını karşılar.
• Kırpmanın gerçek bedeli kapsanan zaman penceresidir: 10.000 giriş iki saati, 1.000 giriş on iki dakikayı taşır. Kırpılmış liste eksik yanıt verdiğini bildirmez, elindeki kadarını verir.

Sonraki Adım

Buraya kadar depoya konan her şey tek parça bir değerdi: oturum kaydı bir bütün, sayaç bir sayı, liste girişi bir dizgi. Kütüphanenin asıl kaydı böyle değildir. Bir kitabın adı, yazarı, raf kodu, durumu ve ödünç sayısı vardır; durum saatte birkaç kez değişirken ad hiç değişmez. Bütün kaydı tek değerde tutmak, tek alanı güncellemek için bütün kaydı yazmak demektir. Sonraki ders bu kaydı iki biçimde kurup üçünü ölçüyor: tek alan güncellemesinde yazılan bayt, tek alan okumasında okunan bayt, ve alanları ayrı ayrı yönetmenin üstveri olarak geri istediği pay.