Bit Eşlemler ve Olasılıksal Yapılar

Buraya kadarki yapılar saydıkları şeyi tam tutuyor. Bir kümenin kaç üyesi olduğu bilinsin diye üye numaralarının hepsi bellekte duruyor; bir karma yapının kaç alanı olduğu bilinsin diye alan adlarının hepsi bellekte duruyor. Üye geri istendiğinde bu zorunludur. Ama her soru üyeyi geri istemez: kütüphanenin gün sonu raporundaki “bugün kaç ayrı okur ödünç aldı” satırının yanıtı tek bir sayıdır ve o sayıyı üretmek için yüz binlerce okur numarasının bellekte tutulması bir karar olarak hiç sorgulanmadı.

Bu ders o kararı sorgular. İki soru ayrılır: kardinalite kestirimi (“kaç ayrı okur”) ve üyelik (“şu okur bugün ödünç aldı mı”). İkisi farklı yapılarla, farklı bayt bütçeleriyle ve farklı kesinlik derecesiyle yanıtlanabilir.

İki Soru, Dört Yapı

Kütüphanenin ödünç kaydı gün boyunca bellek içi depoda birikir. Gün sonunda rapor tekil okur sayısını ister; gün içinde ödünç ekranı “bu okur bugün zaten işlem yaptı mı” sorusunu sorar.

Kod	Varsayım	Değer	Gerekçe
BY10	kayıtlı okur	2.000.000	üye numarası 1’den başlayan yoğun bir aralık
BY11	günlük ödünç olayı	900.000	bütün şubelerin toplamı
BY12	olayların dağılımı	%70’i okurların %15’inden	sık ödünç alan bir çekirdek var
BY13	rapor için kabul edilen sapma	%2	gün sonu raporu kesin sayı istemiyor

BY10 bu dersin karar verdiren varsayımıdır: üye numarası yoğun bir aralık olduğu için okur numarası doğrudan bir bit sırası olarak kullanılabilir. Aralık seyrek olsaydı aşağıdaki tablonun ikinci satırı bambaşka bir sayı gösterirdi; ders bunu sonunda ölçer.

Kesin İki Yapı

İlk düzenek iki kesin yapıyı aynı veriyle doldurur. Tam küme açık adreslemeli bir karma tablodur ve tuttuğu bayt tamponunun boyudur; bit eşlem okur numarasını doğrudan bit sırası olarak kullanır.

// tekil-sayim.mjs — gunun tekil odunc alan okuru: tam kume ile bit eslem.
// Bayt sayilari yapinin kendi tamponundan okunur, tahmin yok; tohum gorunur.
const OKUR = 2_000_000, OLAY = 900_000, TOHUM = 20260731;
let d = TOHUM;                                        // 32 bit tam sayi uretec, tasma yok
const rast = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; };
const okur = () => rast() < 0.7                       // %70 olay, okurlarin %15'inden
  ? 1 + Math.floor(rast() * OKUR * 0.15) : 1 + Math.floor(rast() * OKUR);

class TamKume {                                       // acik adresleme, bos yuva 0
  constructor() { this.k = 1024; this.t = new Int32Array(this.k); this.n = 0; }
  yer(t, k, x) { let i = (Math.imul(x, 2654435761) >>> 0) & (k - 1);
    while (t[i] !== 0 && t[i] !== x + 1) i = (i + 1) & (k - 1); return i; }
  ekle(x) { if ((this.n + 1) * 2 > this.k) this.buyut();
    const i = this.yer(this.t, this.k, x);
    if (this.t[i] === 0) { this.t[i] = x + 1; this.n += 1; } }
  icerir(x) { return this.t[this.yer(this.t, this.k, x)] !== 0; }
  buyut() { const y = new Int32Array(this.k * 2);
    for (const v of this.t) if (v !== 0) y[this.yer(y, this.k * 2, v - 1)] = v;
    this.t = y; this.k *= 2; }
  bayt() { return this.t.byteLength; }
}
class BitEslem {                                      // okur numarasi dogrudan bit sirasidir
  constructor(n) { this.b = new Uint8Array(Math.ceil(n / 8)); }
  ekle(x) { this.b[x >> 3] |= 1 << (x & 7); }
  icerir(x) { return (this.b[x >> 3] & (1 << (x & 7))) !== 0; }
  say() { let s = 0; for (let v of this.b) while (v) { s += v & 1; v >>= 1; } return s; }
  bayt() { return this.b.byteLength; }
}

const kume = new TamKume(), eslem = new BitEslem(OKUR + 1);
for (let i = 0; i < OLAY; i += 1) { const o = okur(); kume.ekle(o); eslem.ekle(o); }
const n = kume.n, tr = (x) => x.toLocaleString("tr-TR");
console.log(`model: ${tr(OKUR)} kayitli okur, ${tr(OLAY)} odunc olayi, tohum ${TOHUM}`);
console.log(`tekil okur: ${tr(n)} (bit eslem ayni sayiyi veriyor: ${tr(eslem.say())})\n`);
console.log("yapi".padEnd(14) + "tutulan bayt".padStart(14) + "tekil basina".padStart(14) +
  "uyelik".padStart(9) + "sayi".padStart(9));
for (const [ad, y] of [["tam kume", kume], ["bit eslem", eslem]])
  console.log(ad.padEnd(14) + tr(y.bayt()).padStart(14) + (y.bayt() / n).toFixed(2).padStart(14) +
    "kesin".padStart(9) + "kesin".padStart(9));

let yanlis = 0;                                       // iki yapi da ayni yaniti veriyor mu
for (let x = 1; x <= OKUR; x += 7) if (kume.icerir(x) !== eslem.icerir(x)) yanlis += 1;
console.log(`\n${tr(Math.ceil(OKUR / 7))} uyelik sorgusunda iki yapinin ayrildigi sorgu: ${yanlis}`);
const SEYREK = 1_000_000_000;                         // 9 haneli uye numarasi kullanilsaydi
console.log(`bit eslem numara araligina baglidir: 1..${tr(OKUR)} icin ${tr(eslem.bayt())} bayt, ` +
  `1..${tr(SEYREK)} icin ${tr(Math.ceil(SEYREK / 8))} bayt (tam kume degismez: ${tr(kume.bayt())})`);

model: 2.000.000 kayitli okur, 900.000 odunc olayi, tohum 20260731
tekil okur: 482.085 (bit eslem ayni sayiyi veriyor: 482.085)

yapi            tutulan bayt  tekil basina   uyelik     sayi
tam kume           4.194.304          8.70    kesin    kesin
bit eslem            250.001          0.52    kesin    kesin

285.715 uyelik sorgusunda iki yapinin ayrildigi sorgu: 0
bit eslem numara araligina baglidir: 1..2.000.000 icin 250.001 bayt, 1..1.000.000.000 icin 125.000.000 bayt (tam kume degismez: 4.194.304)

Bu sayılar ölçüm sınıfındadır; tekil okur sayısı tohuma bağlı, yapıların tuttuğu bayt bağlı değil — o sayı doğrudan tamponun boyudur ve aynı giriş sayısında her koşumda aynıdır.

Bit eşlem tam kümeden on altı kat az yer tutuyor (250.001’e karşı 4.194.304 bayt) ve hiçbir şey kaybetmiyor: tekil sayısı aynı, 285.715 üyelik sorgusunun hiçbirinde iki yapı ayrılmıyor. Bunun nedeni bit eşlemin okur numarasını veri olarak değil adres olarak kullanmasıdır. Tam küme numarayı saklamak zorundadır, çünkü bir yuvada hangi numaranın durduğu ancak yazılıysa bilinir; bit eşlemde numaranın nerede duracağı zaten numaranın kendisidir, dolayısıyla saklanacak bir şey kalmaz ve giriş başına maliyet 8,70 bayttan 0,52 bayta iner.

Kaybedilen şey son satırda: bit eşlemin maliyeti kaç okur ödünç aldığına değil, numara aralığının genişliğine bağlıdır. Kütüphane dokuz haneli üye numarasına geçse aynı 482.085 okur için 250.001 bayt yerine 125.000.000 bayt gerekirdi; tam kümenin maliyeti değişmezdi. Bit eşlem, aralığın yoğun olduğu yerde bedava, seyrek olduğu yerde ödenemez bir yapıdır.

Kesinlikten Vazgeçmek

İki kesin yapı da her okuru ayrı ayrı temsil ediyor. Bir sonraki adım bu temsili bırakmaktır: aynı soruyu, hangi okurun içeride olduğunu belirsiz bırakan yapılarla yanıtlamak.

// olasiliksal-sayim.mjs — ayni gunun ayni iki sorusu, bu kez kesinlikten vazgecerek.
// Uyelik yapisi ve kardinalite kestirimi; dogruluk olcusu icin ayrica tam liste tutulur.
const OKUR = 2_000_000, OLAY = 900_000, TOHUM = 20260731, SORGU = 300_000;
let d = TOHUM;
const rast = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; };
const okur = () => rast() < 0.7
  ? 1 + Math.floor(rast() * OKUR * 0.15) : 1 + Math.floor(rast() * OKUR);
const karma = (x, tohum) => { let h = Math.imul(x ^ tohum, 0x85ebca6b) >>> 0;
  h = Math.imul(h ^ (h >>> 13), 0xc2b2ae35) >>> 0; return (h ^ (h >>> 16)) >>> 0; };

const gercek = new Uint8Array(OKUR + 1);              // yalniz dogruluk olcusu, olculen yapi degil
for (let i = 0; i < OLAY; i += 1) gercek[okur()] = 1;
const uyeler = [], disaridakiler = [];
for (let x = 1; x <= OKUR; x += 1) (gercek[x] ? uyeler : disaridakiler).push(x);
const sorgular = disaridakiler.slice(0, SORGU), n = uyeler.length;
const tr = (x) => x.toLocaleString("tr-TR");
console.log(`model: ${tr(n)} tekil okur, ${tr(SORGU)} olumsuz uyelik sorgusu, tohum ${TOHUM}\n`);

console.log("olasiliksal uyelik yapisi (k = 3 karma)");
console.log("bit".padEnd(10) + "tutulan bayt".padStart(14) + "tekil basina".padStart(14) +
  "yanlis olumlu".padStart(15) + "beklenen".padStart(10) + "kacirilan".padStart(11));
for (const p of [17, 18, 19, 20, 21, 22]) {
  const m = 1 << p, K = 3, b = new Uint8Array(m / 8);
  const yerler = (x) => Array.from({ length: K }, (_, i) => karma(x, 0x1000 + i * 0x9e3779b1) % m);
  for (const x of uyeler) for (const i of yerler(x)) b[i >> 3] |= 1 << (i & 7);
  const icerir = (x) => yerler(x).every((i) => (b[i >> 3] & (1 << (i & 7))) !== 0);
  let yo = 0, kacan = 0;
  for (const x of sorgular) if (icerir(x)) yo += 1;
  for (const x of uyeler) if (!icerir(x)) kacan += 1;
  const beklenen = (1 - Math.exp((-K * n) / m)) ** K;
  console.log(`2^${p}`.padEnd(10) + tr(b.byteLength).padStart(14) +
    (b.byteLength / n).toFixed(2).padStart(14) +
    `%${((yo / SORGU) * 100).toFixed(2)}`.padStart(15) +
    `%${(beklenen * 100).toFixed(2)}`.padStart(10) + `${kacan}`.padStart(11));
}

console.log("\nkardinalite kestirimi (yalniz sayi; uyelik sorusuna yanit vermez)");
console.log("yazmac".padEnd(10) + "tutulan bayt".padStart(14) + "tekil basina".padStart(14) +
  "kestirim".padStart(12) + "sapma".padStart(9) + "kuramsal".padStart(10));
for (const p of [8, 10, 12, 14]) {
  const m = 1 << p, R = new Uint8Array(m);
  for (const x of uyeler) { const h = karma(x, 0x9e37), i = h >>> (32 - p), w = (h << p) >>> 0;
    const r = w === 0 ? 33 - p : Math.clz32(w) + 1; if (r > R[i]) R[i] = r; }
  let z = 0, sifir = 0;
  for (const v of R) { z += 2 ** -v; if (v === 0) sifir += 1; }
  let e = (0.7213 / (1 + 1.079 / m)) * m * m / z;
  if (e <= 2.5 * m && sifir > 0) e = m * Math.log(m / sifir);   // dogrusal sayim duzeltmesi
  console.log(`2^${p}`.padEnd(10) + tr(R.byteLength).padStart(14) +
    (R.byteLength / n).toFixed(4).padStart(14) + tr(Math.round(e)).padStart(12) +
    `%${(((e - n) / n) * 100).toFixed(2)}`.padStart(9) +
    `%${((1.04 / Math.sqrt(m)) * 100).toFixed(2)}`.padStart(10));
}

model: 482.085 tekil okur, 300.000 olumsuz uyelik sorgusu, tohum 20260731

olasiliksal uyelik yapisi (k = 3 karma)
bit         tutulan bayt  tekil basina  yanlis olumlu  beklenen  kacirilan
2^17              16.384          0.03         %99.99   %100.00          0
2^18              32.768          0.07         %98.83    %98.80          0
2^19              65.536          0.14         %82.26    %82.16          0
2^20             131.072          0.27         %42.09    %41.89          0
2^21             262.144          0.54         %12.41    %12.37          0
2^22             524.288          1.09          %2.53     %2.48          0

kardinalite kestirimi (yalniz sayi; uyelik sorusuna yanit vermez)
yazmac      tutulan bayt  tekil basina    kestirim    sapma  kuramsal
2^8                  256        0.0005     476.215   %-1.22     %6.50
2^10               1.024        0.0021     481.111   %-0.20     %3.25
2^12               4.096        0.0085     474.849   %-1.50     %1.63
2^14              16.384        0.0340     478.877   %-0.67     %0.81

Üst tabloda kaçırılan sütunu her satırda sıfır: olasılıksal üyelik yapısı bir üyeyi asla “yok” diye yanıtlamaz, çünkü eklenen her üyenin bitleri kurulmuştur ve hiç silinmez. Hata tek yönlüdür ve adı yanlış olumlu: yapı, hiç eklenmemiş bir okur için de üç bitin üçünü birden kurulmuş bulabilir. Ölçülen oran kuramsal oranla satır satır örtüşüyor (2^21’de %12,41’e karşı %12,37), yani bu oran bir sürpriz değil, yapının boyuyla seçilen bir niceliktir.

Aynı sözcük çifti yazılım testi bağlamında da geçer; oradaki yanlış alarm kusursuz kodu kusurlu diye işaretleyen bir testin giderilebilir hatasıdır, burada ölçülen yanlış olumlu oranı ise yapının tanımına yazılıdır: bayt eklenerek düşürülebilir, sıfırlanamaz.

Alt tablo takasın en keskin biçimidir. 4.096 bayt tutan yazmaç dizisi 482.085 tekil okuru %1,50 sapmayla sayıyor: tam kümenin bin yirmi dört katı, bit eşlemin altmış bir katı az yer tutuyor. Seçilecek boy son sütundan okunur, ölçülen sapmadan değil. 256 baytlık dizi bu koşumda %1,22 sapmayla çıktı ama kuramsal hata payı %6,50; BY13’ün %2’lik toleransını güvenle karşılayan ilk boy kuramsal payı %1,63 olan 4.096 bayttır. Karşılığında verdiği şey mutlaktır: bu yapı “şu okur ödünç aldı mı” sorusuna hiçbir kesinlik derecesinde yanıt veremez, çünkü okurun kendisi hiçbir zaman temsil edilmemiştir; yalnız karmasının baştaki sıfırlarının kaç tane olduğu tutulmuştur.

Hangi Yapı Neyi Satın Alır

Dört yapı aynı gün için sırasıyla 4.194.304, 250.001, 524.288 ve 4.096 bayt tutuyor. Sıralama şaşırtıcı bir yerde kırılıyor: yoğun bir numara aralığında olasılıksal üyelik yapısı bit eşleme yenilir. %2,53 yanlış olumluyla çalışan yapı 524.288 bayt istiyor, kesin bit eşlem 250.001 bayt. Yani bu koşullarda kesinlikten vazgeçmek bellek kazandırmıyor, tersine kaybettiriyor.

Olasılıksal üyelik yapısının kazandığı yer aralığın seyrek olduğu yerdir. Kütüphanenin ikinci sorusu şudur: bugün hangi kitap kimliği en az bir kez elden geçti? Kitap kimliği yoğun bir sayı değil, on üç haneli bir dizgi; bit eşlem için adres yok. Orada tam küme dizginin kendisini tutmak zorundadır, olasılıksal yapı ise dizginin karmasını kullanır ve boyu üye sayısına bağlı kalır. Seçim kuralı yapının adında değil, anahtar uzayının yoğunluğundadır.

Bir de birleştirme var. Haftalık tekil okur sorusu yedi günün sonucunu birleştirmeyi gerektirir. Bit eşlemler bit düzeyinde “veya” ile birleşir ve sonuç kesin kalır; kardinalite kestirimleri yazmaç başına en büyüğü alınarak birleşir ve sapma büyümez; tam kümeler birleştirilirken bütün üyeler yeniden dokunulur ve maliyet gün sayısıyla çarpılır. Günlük 4.096 baytlık yazmaç dizisi bir yıl saklandığında 1.495.040 bayt tutar — tek bir günün tam kümesinden hâlâ küçüktür ve yıl içindeki her alt aralık için ayrı yanıt verebilir.

Özet

• Tekil sayım ile üyelik iki ayrı sorudur ve ayrı yapılarla yanıtlanır: kardinalite kestirimi sayıyı verir ama üyeliği hiçbir kesinlikte yanıtlamaz, çünkü üyeyi temsil etmez.
• Yoğun bir numara aralığında bit eşlem tam kümeden on altı kat az yer tutar (250.001’e karşı 4.194.304 bayt) ve hiçbir şey kaybetmez; maliyeti giriş sayısına değil aralık genişliğine bağlıdır ve dokuz haneli numarada 125.000.000 bayta çıkar.
• Olasılıksal üyelik yapısının hatası tek yönlüdür: kaçırılan üye sıfır, yanlış olumlu oranı ise yapının boyuyla seçilir — 131.072 baytta %42,09, 524.288 baytta %2,53 ve ölçülen oran kuramsal oranla örtüşür.
• Yoğun aralıkta kesinlikten vazgeçmek bellek kazandırmaz: %2,53 hatalı yapı 524.288 bayt, kesin bit eşlem 250.001 bayt ister. Olasılıksal yapı ancak anahtar uzayı seyrekken kazanır.
• Kardinalite kestirimi 4.096 baytla %1,50 sapma verir; tam kümenin bin yirmi dört katı az yer tutar ve karşılığında hangi okurun sayıldığı bilgisini geri alınamaz biçimde bırakır.

Sonraki Adım

Bu derste ölçülen yapılar zamanı hiç umursamadı. Bit eşlem “bugün ödünç aldı mı” sorusuna yanıt veriyor ama ne zaman aldığını bilmiyor; kardinalite kestirimi gün sonunda bir sayı üretiyor ama o sayının hangi sırayla toplandığını söyleyemiyor. Aynı gün içinde okunması gereken bir soru daha var: kütüphanenin raf yerleştirme ekibi, gecikme bildirimi işi ve arama dizini güncellemesi, olayları oldukları sırayla ve her biri kendi kaldığı yerden görmek zorunda. Buraya kadarki hiçbir yapı bunu vermiyor — küme sıra tutmuyor, sayaç geçmiş tutmuyor, liste ise okuyan her tarafın kendi konumunu ayrı ayrı hatırlamasına yardım etmiyor. Sonraki ders olayları sırasıyla saklayan ve her okuyan tarafın konumunu yapının kendisinde tutan yapıyı ele alır.