Kümeler ve Sıralı Kümeler

Karma yapı bir kaydın alanlarını ayırdı, ama bütün alanlar hâlâ tek bir kayda aitti. Kütüphanenin bazı soruları tek kayda ait değildir. “Bu kitap şu an ödünçte olanlar arasında mı” bir üyelik sorusudur ve yanıtı evet ya da hayırdır. “Bu kitap en çok ödünç alınanlar arasında kaçıncı” bir sıra sorusudur ve yanıtı bir sayıdır ama sıralı bir bütünden okunur. İki soru da aynı şeyi gerektirir: hangi üyelerin bulunduğunun bellekte tutulmasını.

Bu yapıların karmaşıklık çözümlemesi daha önce yapıldı; burada ölçülen şey tutulan bayt ile depo semantiğidir.

Üyelik: Evet mi Hayır mı

BY1: gün içinde 38.000 kitap ödünçtedir, üye kimliği 6 bayttır; 10.000 üyelik sorgusunun yarısı kümede olan, yarısı olmayan bir kitabı sorar. BY2: dizi yuvası 8, yapı üstverisi 56, küme girişi başına üstveri 48 bayttır (kova göstergesi, giriş yapısı, karma değeri, hizalama).

// bellek/uyelik.mjs — "bu kitap su an oduncte mi" sorusu uc yapida. Adimlar
// gerceklestirimin icinde sayilir; is yuku belirlenimlidir.
const USTVERI = 56, YUVA = 8, KUME_USTVERI = 48;          // BY2
const bl = (x) => Buffer.byteLength(String(x));
const ODUNCTE = 38_000, SORGU = 10_000, KITAP = 200_000;
const uye = (i) => String(100_000 + (i * 4241) % KITAP);
const uyeler = [...new Set(Array.from({ length: ODUNCTE }, (_, i) => uye(i)))];

class ListeUyelik {                             // sira korunur, uyelik taramadir
  #a = []; adim = 0; eklemeAdim = 0;
  ekle(v) { this.eklemeAdim += 1; this.#a.push(v); }
  var_mi(v) { for (const x of this.#a) { this.adim += 1; if (x === v) return true; } return false; }
  bayt() { return USTVERI + this.#a.reduce((t, v) => t + bl(v) + YUVA, 0); }
  get n() { return this.#a.length; }
}
class SiraliDiziUyelik {                        // ikili arama; ekleme kaydirma ister
  #a = []; adim = 0; eklemeAdim = 0;
  #yer(v) { let d = 0, y = this.#a.length;
    while (d < y) { this.adim += 1; const o = (d + y) >> 1; if (this.#a[o] < v) d = o + 1; else y = o; }
    return d; }
  ekle(v) { const i = this.#yer(v); this.eklemeAdim += this.#a.length - i + 1; this.#a.splice(i, 0, v); }
  var_mi(v) { const i = this.#yer(v); return this.#a[i] === v; }
  bayt() { return USTVERI + this.#a.reduce((t, x) => t + bl(x) + YUVA, 0); }
  get n() { return this.#a.length; }
}
class KumeUyelik {                              // karma: tek adim, giris basina ek ustveri
  #s = new Set(); adim = 0; eklemeAdim = 0;
  ekle(v) { this.eklemeAdim += 1; this.#s.add(v); }
  var_mi(v) { this.adim += 1; return this.#s.has(v); }
  bayt() { let b = USTVERI; for (const v of this.#s) b += bl(v) + KUME_USTVERI; return b; }
  get n() { return this.#s.size; }
}

const yapi = [["liste", new ListeUyelik()], ["sirali dizi", new SiraliDiziUyelik()],
  ["kume", new KumeUyelik()]];
for (const [, y] of yapi) for (const v of uyeler) y.ekle(v);

// sorgularin yarisi kumede olan, yarisi olmayan bir kitabi sorar
const sorgu = Array.from({ length: SORGU }, (_, j) =>
  j % 2 === 0 ? uyeler[(j * 7919) % uyeler.length] : String(100_000 + KITAP + j));
let bulunan = 0;
for (const [, y] of yapi) { let b = 0; for (const s of sorgu) if (y.var_mi(s)) b += 1; bulunan = b; }

console.log(`${uyeler.length} kitap oduncte (uye ${bl(uyeler[0])} bayt), ${SORGU} uyelik sorgusu, ` +
  `${bulunan} tanesi bulundu`);
console.log(`${"yapi".padEnd(13)}${"tutulan bayt".padStart(14)}${"giris basina".padStart(13)}` +
  `${"sorgu adimi".padStart(13)}${"sorgu basina".padStart(14)}${"ekleme adimi".padStart(14)}`);
for (const [ad, y] of yapi)
  console.log(ad.padEnd(13) + String(y.bayt()).padStart(14) + (y.bayt() / y.n).toFixed(1).padStart(13) +
    String(y.adim).padStart(13) + (y.adim / SORGU).toFixed(1).padStart(14) +
    String(y.eklemeAdim).padStart(14));

38000 kitap oduncte (uye 6 bayt), 10000 uyelik sorgusu, 5000 tanesi bulundu
yapi           tutulan bayt giris basina  sorgu adimi  sorgu basina  ekleme adimi
liste                532056         14.0    284642000       28464.2         38000
sirali dizi          532056         14.0       676550          67.7     360742025
kume                2052056         54.0        10000           1.0         38000

Liste ve sıralı dizi aynı 532.056 baytı tutuyor, giriş başına 14,0. Küme aynı 38.000 üye için 2.052.056 bayt istiyor — giriş başına 54,0, yani 3,86 kat. Fark tek kalemdir: kova göstergesi ve giriş yapısı için üye başına 40 bayt. Altı baytlık bir kitap kimliğini kümede tutmak, kimliğin kendisinin dokuz katı yer harcıyor.

Karşılığı sorgu sütununda: liste her soruyu ortalama 28.464 adımda, küme 1 adımda yanıtlıyor. Sıralı dizi ilginç bir orta yol gibi görünüyor — listenin belleğiyle 67,7 adım — ama ekleme sütunu onu bitiriyor. Sıralı dizide her ekleme kalan girişleri kaydırır: 38.000 ekleme 360.742.025 adım, ekleme başına 9.493. Ödünçte olan kitaplar kümesi durağan değildir; gün içinde her ödünç bir ekleme, her iade bir çıkarma demektir. Sıralı dizi bu iş yükünde sorgudan kazandığını eklemede yüz kat fazlasıyla geri veriyor.

Kümenin fazladan tuttuğu 1.520.000 bayt hem sorguyu hem eklemeyi tek adıma indiriyor. Kaybettiği şey sütunlarda görünmez: küme sırayı tutmaz. Liste 38.000 kitabı eklenme sırasıyla taşıyordu; küme aynı kitapları taşır ama hangisinin önce ödünç verildiği bilgisi yoktur. Üyelik yanıtı alınırken sıra bırakılmıştır.

Sıra: Kaçıncı

Sıralama tablosu iki soruyu birden sorar: bir kitabın puanı kaç, ve o puan kaçıncı sıraya karşılık geliyor. Birincisi için üye–puan karması yeterlidir ve üç yolda da ortaktır; ikincisi bir sıra dizini ister. BY3: 50.000 kitabın popülerlik puanı vardır, 10.000 ödünç puan artırır, 2.000 sıra sorgusu ve 200 “en üst 20” sorgusu gelir. BY4: atlamalı listenin düğüm düzeyleri tohumu görünür bir üreticiden gelir; düğüm başlığı 24, düzey başına gösterge çifti 16 bayttır. Üç yolun verdiği sıralar kaba kuvvetle karşılaştırılır.

// bellek/siralama.mjs — populer kitap siralamasi: uye->puan karmasi uzerine uc sira dizini.
// Atlamali listenin duzeyleri tohumlu ureticten gelir; siralar kaba kuvvetle dogrulanir.
const USTVERI = 56, YUVA = 8, KUME_USTVERI = 48, DUGUM = 24, GOSTERGE = 16;   // BY2
const KITAP = 50_000, GUNCELLEME = 10_000, SORGU = 2_000, UST = 20, TOHUM = 20240115;
const bl = (x) => Buffer.byteLength(String(x));
let c = TOHUM;
const rast = () => (c = (c * 1103515245 + 12345) % 2147483648) / 2147483648;

const uye = (i) => String(100_000 + i);
const puan0 = (i) => 1 + (i * 7919) % 4096;
const once = (p1, u1, p2, u2) => p1 > p2 || (p1 === p2 && u1 < u2);   // puan azalan, uye artan

class AtlamaliListe {
  #bas; #duzey = 1; #n = 0; #max; adim = 0; gosterge = 0;
  constructor(max = 16) { this.#max = max;
    this.#bas = { uye: "", puan: 0, ileri: new Array(max).fill(null), acik: new Array(max).fill(0) }; }
  #duzeySec() { let d = 1; while (rast() < 0.5 && d < this.#max) d += 1; return d; }
  #yol(puan, u) {
    const g = new Array(this.#max), s = new Array(this.#max).fill(0);
    let x = this.#bas;
    for (let i = this.#duzey - 1; i >= 0; i -= 1) {
      s[i] = i === this.#duzey - 1 ? 0 : s[i + 1];
      while (x.ileri[i] && once(x.ileri[i].puan, x.ileri[i].uye, puan, u)) {
        this.adim += 1; s[i] += x.acik[i]; x = x.ileri[i]; }
      g[i] = x;
    }
    return [g, s, x.ileri[0]];
  }
  ekle(u, puan) {
    const [g, s] = this.#yol(puan, u);
    const d = this.#duzeySec();
    if (d > this.#duzey) { for (let i = this.#duzey; i < d; i += 1) {
      s[i] = 0; g[i] = this.#bas; this.#bas.acik[i] = this.#n; } this.#duzey = d; }
    const y = { uye: u, puan, ileri: new Array(d), acik: new Array(d) };
    this.gosterge += d;
    for (let i = 0; i < d; i += 1) {
      y.ileri[i] = g[i].ileri[i]; g[i].ileri[i] = y;
      y.acik[i] = g[i].acik[i] - (s[0] - s[i]); g[i].acik[i] = (s[0] - s[i]) + 1;
    }
    for (let i = d; i < this.#duzey; i += 1) g[i].acik[i] += 1;
    this.#n += 1;
  }
  cikar(u, puan) {
    const [g, , x] = this.#yol(puan, u);
    if (!x || x.uye !== u || x.puan !== puan) return false;
    for (let i = 0; i < this.#duzey; i += 1) {
      if (g[i].ileri[i] === x) { g[i].acik[i] += x.acik[i] - 1; g[i].ileri[i] = x.ileri[i]; }
      else g[i].acik[i] -= 1;
    }
    this.gosterge -= x.ileri.length;
    while (this.#duzey > 1 && this.#bas.ileri[this.#duzey - 1] === null) this.#duzey -= 1;
    this.#n -= 1; return true;
  }
  sira(u, puan) { const [, s, x] = this.#yol(puan, u); return x && x.uye === u ? s[0] + 1 : -1; }
  ust(k) { const r = []; let x = this.#bas.ileri[0];
    while (x && r.length < k) { this.adim += 1; r.push(x.uye); x = x.ileri[0]; } return r; }
  bayt() { let b = USTVERI; let x = this.#bas.ileri[0];
    while (x) { b += bl(x.uye) + DUGUM + x.ileri.length * GOSTERGE; x = x.ileri[0]; } return b; }
  get duzey() { return this.#duzey; }
}

const karma = new Map();                        // uye -> puan; uc yolda da ortak
for (let i = 1; i <= KITAP; i += 1) karma.set(uye(i), puan0(i));
const karmaBayt = [...karma].reduce((t, [u]) => t + bl(u) + YUVA + KUME_USTVERI, USTVERI);

const dizi = [...karma].map(([u, p]) => [p, u]).sort((a, b) => (once(a[0], a[1], b[0], b[1]) ? -1 : 1));
const atlama = new AtlamaliListe();
for (const [u, p] of karma) atlama.ekle(u, p);
let diziAdim = 0, dizinsizAdim = 0;
const yer = (p, u) => { let d = 0, y = dizi.length;
  while (d < y) { diziAdim += 1; const o = (d + y) >> 1;
    if (once(dizi[o][0], dizi[o][1], p, u)) d = o + 1; else y = o; } return d; };

// gunluk yuk: puan artirma, sira sorgusu, en ust K
const olay = Array.from({ length: GUNCELLEME }, (_, j) => uye(1 + (j * 4241) % KITAP));
for (const u of olay) {
  const eski = karma.get(u), yeni = eski + 1;
  const i = yer(eski, u); diziAdim += dizi.length - i; dizi.splice(i, 1);        // kaydirma
  const k = yer(yeni, u); diziAdim += dizi.length - k; dizi.splice(k, 0, [yeni, u]);
  atlama.cikar(u, eski); atlama.ekle(u, yeni); karma.set(u, yeni);
}
const sorgu = Array.from({ length: SORGU }, (_, j) => uye(1 + (j * 7919) % KITAP));
let esit = 0;
for (const u of sorgu) {
  const p = karma.get(u);
  let s1 = 1; for (const [v, q] of karma) { dizinsizAdim += 1; if (once(q, v, p, u)) s1 += 1; }
  const s2 = yer(p, u) + 1, s3 = atlama.sira(u, p);
  if (s1 === s2 && s2 === s3) esit += 1;
}
for (let j = 0; j < 200; j += 1) {
  [...karma].sort((a, b) => { dizinsizAdim += 1; return once(a[1], a[0], b[1], b[0]) ? -1 : 1; }).slice(0, UST);
  diziAdim += UST; dizi.slice(0, UST); atlama.ust(UST);
}

console.log(`${KITAP} kitap, ${GUNCELLEME} puan artirma, ${SORGU} sira sorgusu, 200 "en ust ${UST}"`);
console.log(`${esit}/${SORGU} sorguda uc yol ayni sirayi verdi; atlamali liste duzeyi ${atlama.duzey}, ` +
  `gosterge ${atlama.gosterge} (dugum basina ${(atlama.gosterge / KITAP).toFixed(2)}), tohum ${TOHUM}`);
const yol = [
  ["sira dizini yok", karmaBayt, dizinsizAdim],
  ["sirali dizi", karmaBayt + USTVERI + dizi.reduce((t, [, u]) => t + bl(u) + YUVA + YUVA, 0), diziAdim],
  ["atlamali liste", karmaBayt + atlama.bayt(), atlama.adim],
];
console.log(`\n${"sira dizini".padEnd(17)}${"tutulan bayt".padStart(14)}${"dizin payi".padStart(12)}` +
  `${"giris basina".padStart(13)}${"toplam adim".padStart(13)}`);
for (const [ad, b, adim] of yol)
  console.log(ad.padEnd(17) + String(b).padStart(14) + String(b - karmaBayt).padStart(12) +
    (b / KITAP).toFixed(1).padStart(13) + String(adim).padStart(13));

50000 kitap, 10000 puan artirma, 2000 sira sorgusu, 200 "en ust 20"
2000/2000 sorguda uc yol ayni sirayi verdi; atlamali liste duzeyi 13, gosterge 102228 (dugum basina 2.04), tohum 20240115

sira dizini        tutulan bayt  dizin payi giris basina  toplam adim
sira dizini yok         3100056           0         62.0    212473400
sirali dizi             4200112     1100056         84.0    500247667
atlamali liste          6235760     3135704        124.7      1336074

Üç yol da 2.000 sorgunun tamamında aynı sırayı veriyor; ayrım yalnız fiyattadır. Sıra dizini tutulmazsa karma 3.100.056 bayttadır ve her sıra sorgusu bütün girişleri gezer, her “en üst 20” sorgusu bütün tabloyu sıralar: 212.473.400 adım.

Sıralı dizi bu iş yükünde hiçbir şey satın almıyor. 1.100.056 bayt fazla tutuyor ve toplam adımı 500.247.667’ye çıkarıyor — dizinsiz yoldan da kötü. Nedeni önceki bölümdekiyle aynıdır: sıra sorgusu ikili aramayla ucuzken, her puan artırması girişi eski yerinden çıkarıp yenisine sokmak için ortalama yirmi beş bin girişi kaydırıyor. Sıralı dizi durağan bir tabloda iyi, sürekli değişen bir sıralama tablosunda yanlış seçimdir.

Atlamalı liste 3.135.704 bayt fazla tutuyor — giriş başına 124,7 bayt, üyelik kümesinin iki katından fazla — ve toplam adımı 1.336.074’e indiriyor. Fazladan tuttuğu her bayt 67,3 adım önlüyor. Bu baytların yarıdan fazlası ne puan ne kimliktir: 102.228 gösterge çifti, düğüm başına 2,04 düzey, 1.635.648 bayt. Sıra dizininin maliyeti verinin kendisi değil, veriye sıradan erişmenin yoludur. Karşılığında hem sıra sorgusu hem “en üst 20” sorgusu tablonun boyundan bağımsız hâle gelir; puan güncellemesi de öyle.

Özet

• Üyelik sorusu üç yapıda da doğru yanıtlanır: liste 28.464,2, sıralı dizi 67,7, küme 1,0 adımda.
• Küme aynı 38.000 üyeyi 2.052.056 baytta tutar; liste ve sıralı dizi 532.056 baytta. Fark üye başına 40 baytlık kova ve giriş üstverisidir — altı baytlık kimliğin dokuz katı.
• Sıralı dizi üyelikte kandırıcıdır: sorgu ucuzdur ama 38.000 ekleme 360.742.025 adım harcar (ekleme başına 9.493). Sürekli değişen bir üyelik kümesinde en kötü seçimdir.
• Kümenin kaybettiği şey sıradır: hangi kitabın önce ödünç verildiği bilgisi kümede yoktur.
• Sıralama tablosunda sıra dizini tutmamak 3.100.056 bayt ve 212.473.400 adım demektir; sıralı dizi 1.100.056 bayt fazla tutup adımı 500.247.667’ye çıkarır, çünkü her puan artırması kaydırma ister.
• Atlamalı liste 3.135.704 bayt fazla tutar ve adımı 1.336.074’e indirir: bayt başına 67,3 adım. Bu baytların 1.635.648’i saf göstergedir — düğüm başına 2,04 düzey.

Sonraki Adım

Bu dersteki iki yapı da doğru yanıt verdi ve ikisi de aynı şeyi yaptı: saydıkları şeyi tam tuttular. Küme 38.000 kitabın kimliğini tek tek taşıdı, sıralı küme 50.000 kitabın hem kimliğini hem puanını hem de sıradaki yerini. Aynı şey önceki derslerde de geçerliydi — karma yapı her alanı, liste her girişi, sayaç her anahtarı ayrı ayrı tuttu.

Oysa kütüphanenin sorularının bir bölümü üyelerin kendisini istemiyor. “Bugün kaç farklı üye sisteme girdi”, “bu kitabı daha önce ödünç alan biri mi”, “hangi günlerde ödünç verildi” — bunların yanıtı bir sayı ya da bir evet–hayırdır, üyelerin listesi değil. Yanıt için sayı yeterken üyelerin tamamını bellekte tutmanın bedeli bu derslerin hiçbirinde sorulmadı. Sonraki ders bu soruyu açıyor.