Toplama Sorguları

Bir önceki ders sıralı bir belge listesi üretti ve o listenin ilk onunu tartıştı. Ödünç masasının panosunda duran sorular ise belge istemez: hangi konu başlığında kaç kitap var, bu aramanın sonuçları kitap başına kaç kez ödünç verilmiş, yıllara göre ödünç eğrisi nasıl gidiyor. Bu sorular aynı ters dizin üzerinde çalışır ama çıktıları sıralanmış bir liste değildir.

Üç biçim ayrılır. Ölçüt toplaması bir belge kümesinden tek bir sayı üretir: sayı, toplam, ortalama, en büyük. Kova toplaması kümeyi bir anahtara göre parçalara ayırır ve her parçada bir ölçüt hesaplar. Boru hattı toplaması girdisini belgelerden değil, başka bir toplamanın kovalarından alır: kümülatif pay, hareketli ortalama, kovalar arası fark.

Toplamanın sıraya bakmaması bu dersin ilk gözlemidir. Sorgu değerlendiricisi sıralı bir liste üretir; toplama o listenin sırasını değil kümesini okur. Kendi sırası vardır ama o sıra kova sırasıdır. Ders küme ile sırayı bu düzlemde ölçer, bedeli bayt olarak sayar.

Derlem, Ödünç Kaydı ve Üç Toplama

Kod	Varsayım	Değer	Gerekçe
SI14	ödünç kaydı	her kitap kendi ödünç sayısı kadar olay	kayıt derlemden türetilir, ayrı tohum gerekmez
SI15	okur havuzu	40.000 okur, çarpık seçim	tekil okur sayısı kova başına yüksek kardinalite üretsin
SI16	ölçüt kovası	kova başına üç sayı (sayı, toplam, en büyük)	24 baytlık sabit kova durumu
SI17	toplama girdisi	eşleşen kümenin tamamı	ilk N sonuç kısıtı toplamaya uygulanmaz

SI17 sessiz ama belirleyicidir: kullanıcıya on sonuç gösterilse de toplama 325 belgenin hepsini görür; maliyeti gösterilen sonuç sayısıyla değil eşleşen küme boyuyla büyür.

// derlem.mjs — kutuphane katalogu: tohumlu derlem, ters dizin ve eslesen kume.
export const N = 1200, TOHUM = 20260801, ALANLAR = ["ad", "ozet", "konu", "yazar"];
let d = TOHUM;                                            // 32 bit uretec, tasma yok
export 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 sec = (a) => a[Math.floor(rast() * a.length)];
const TEMA = [["öykü|hikâye", "edebiyat", "kısa seçki derleme anlatı kurgu taşra"],
  ["masal", "çocuk edebiyatı", "çocuk resimli okul genç orman uyku"],
  ["tarih", "tarih", "osmanlı cumhuriyet arşiv belge kronik vakıf"],
  ["deniz", "gezi", "kıyı balıkçı liman gemi ada fener"],
  ["matematik", "bilim", "geometri sayı kanıt kuram çözüm olasılık"],
  ["şiir", "şiir", "dize toplu divan çeviri seçme aruz"]]
  .map(([k, konu, a]) => ({ k: k.split("|"), konu, ana: a.split(" ") }));
const ORTAK = "kitap cilt baskı yayın inceleme notlar giriş sözlük".split(" ");
const AD = "Ahmet Elif Selim Nuray Kemal Deniz Ayşe Ozan Meral Barış".split(" ");
const SOY = "Yıldız Aksu Demir Karaca Toprak Şen".split(" ");

export const belgeler = Array.from({ length: N }, (_, id) => {
  const t = sec(TEMA), cek = t.k[t.k.length > 1 && rast() < 0.5 ? 1 : 0], oz = [cek, cek];
  const ad = [...new Set([cek, sec(t.ana), sec(t.ana)])];
  t.ana.forEach((s, j) => { if (rast() < 1 / (1 + j * 0.42)) oz.push(s); });
  ORTAK.forEach((s, j) => { if (rast() < 0.55 / (1 + j * 0.28)) oz.push(s); });
  if (rast() < 0.5) oz.push(sec(sec(TEMA).ana));          // baska temadan sizan sozcuk
  for (let k = oz.length - 1; k > 0; k -= 1) { const j = Math.floor(rast() * (k + 1));
    [oz[k], oz[j]] = [oz[j], oz[k]]; }
  // konu etiketi yayinevi kararidir: belgelerin dortte birinde metinle ayni temada degil
  return { id, ad: ad.join(" "), ozet: oz.join(" "), konu: (rast() < 0.25 ? sec(TEMA) : t).konu,
    yazar: `${sec(AD)} ${sec(SOY)}`, yil: 1975 + Math.floor(rast() ** 0.6 * 50),
    odunc: Math.floor(rast() ** 3 * 400) };
});

export const belirtec = (s) => s.toLocaleLowerCase("tr").match(/[\p{L}\p{N}]+/gu) ?? [];
export function dizinKur(bs) {                            // alan basina ters dizin
  const dz = {};
  for (const a of ALANLAR) {
    const gonderi = new Map();
    for (const b of bs) for (const t of new Set(belirtec(b[a]))) {
      if (!gonderi.has(t)) gonderi.set(t, []);
      gonderi.get(t).push(b.id);
    }
    dz[a] = gonderi;
  }
  return dz;
}
export function eslesenler(dz, sorgu) {   // sorgu terimlerinden en az birini tasiyan belgeler
  const s = new Set();
  for (const a of ALANLAR) for (const t of belirtec(sorgu))
    for (const id of dz[a].get(t) ?? []) s.add(id);
  return s;
}

Kova Sayısı Bir Bellek Kararıdır

Kova toplaması “hangi alana göre gruplayalım” sorusuyla belirlenir ve bu bir bellek kararıdır: her kova, ölçütünü hesaplamak için kendi durumunu tutmak zorundadır. Sayı ve toplam gibi ölçütler kova başına sabit yer ister; tekil sayım istemez, çünkü kaç ayrı okur olduğunu bilmek o okurların bir temsilini tutmayı gerektirir. Düzenek beş kova anahtarı için ikisini de ölçer: kesin küme ve kardinalite kestirimi. Kestirimin yapısı M17/K06’da kurulup ölçülmüştü; burada araç olarak kullanılır, tuttuğu bayt kendi tamponundan okunur.

// toplama.mjs — kova sayisi ile tekil sayimin bayt maliyeti: kesin kume ve kestirim.
import { belgeler, rast, N, TOHUM } from "./derlem.mjs";
const OKUR = 40_000, olay = [];                           // her kitap kendi odunc sayisi kadar
for (const b of belgeler) for (let i = 0; i < b.odunc; i += 1)
  olay.push([b.id, 1 + Math.floor(rast() ** 2 * OKUR)]);  // okur secimi carpik

class Kume {                                              // acik adresleme, bos yuva 0
  constructor() { this.t = new Int32Array(16); this.n = 0; }
  yer(t, x) { let i = (Math.imul(x, 2654435761) >>> 0) & (t.length - 1);
    while (t[i] !== 0 && t[i] !== x) i = (i + 1) & (t.length - 1); return i; }
  ekle(x) {
    if ((this.n + 1) * 2 > this.t.length) { const y = new Int32Array(this.t.length * 2);
      for (const v of this.t) if (v !== 0) y[this.yer(y, v)] = v; this.t = y; }
    const i = this.yer(this.t, x);
    if (this.t[i] === 0) { this.t[i] = x; this.n += 1; }
  }
}
class Yaklasik {          // kardinalite kestirimi: yapisi M17/K06'da kuruldu, burada araç
  constructor(p) { this.p = p; this.R = new Uint8Array(1 << p); }
  ekle(x) { let h = Math.imul(x ^ 0x9e37, 0x85ebca6b) >>> 0;
    h = Math.imul(h ^ (h >>> 13), 0xc2b2ae35) >>> 0; h = (h ^ (h >>> 16)) >>> 0;
    const i = h >>> (32 - this.p), w = (h << this.p) >>> 0;
    const r = w === 0 ? 33 - this.p : Math.clz32(w) + 1;
    if (r > this.R[i]) this.R[i] = r; }
  say() { const m = this.R.length; let z = 0, s = 0;
    for (const v of this.R) { z += 2 ** -v; if (v === 0) s += 1; }
    const e = (0.7213 / (1 + 1.079 / m)) * m * m / z;
    return e <= 2.5 * m && s > 0 ? m * Math.log(m / s) : e; }
}

const tr = (x) => Math.round(x).toLocaleString("tr-TR");
const ANAHTAR = { konu: (b) => b.konu, "on yıl": (b) => `${Math.floor(b.yil / 10) * 10}`,
  yıl: (b) => `${b.yil}`, yazar: (b) => b.yazar, kitap: (b) => `${b.id}` };
console.log(`derlem ${N} belge, tohum ${TOHUM}; ödünç kaydı ${tr(olay.length)} olay, ` +
  `${tr(OKUR)} okur havuzu\n`);
console.log("kova alanı".padEnd(11) + "kova".padStart(6) + "ölçüt".padStart(8) +
  "kesin tekil".padStart(13) + "kestirim p8".padStart(13) + "sapma".padStart(8) +
  "kestirim p12".padStart(14) + "sapma".padStart(8) + "en büyük kova".padStart(15));
for (const [ad, f] of Object.entries(ANAHTAR)) {
  const kesin = new Map(), yak = [new Map(), new Map()], P = [8, 12];
  for (const [kitap, okur] of olay) {
    const k = f(belgeler[kitap]);
    if (!kesin.has(k)) { kesin.set(k, new Kume()); P.forEach((p, j) => yak[j].set(k, new Yaklasik(p))); }
    kesin.get(k).ekle(okur); yak.forEach((m) => m.get(k).ekle(okur));
  }
  let kb = 0, enBuyuk = 0;
  const yb = [0, 0], sapma = [0, 0];
  for (const [k, s] of kesin) {
    kb += s.t.byteLength; enBuyuk = Math.max(enBuyuk, s.n);
    yak.forEach((m, j) => { yb[j] += m.get(k).R.byteLength;
      sapma[j] = Math.max(sapma[j], Math.abs(m.get(k).say() - s.n) / s.n); });
  }
  console.log(ad.padEnd(11) + tr(kesin.size).padStart(6) + tr(kesin.size * 3 * 8).padStart(8) +
    tr(kb).padStart(13) + tr(yb[0]).padStart(13) + `%${(sapma[0] * 100).toFixed(1)}`.padStart(8) +
    tr(yb[1]).padStart(14) + `%${(sapma[1] * 100).toFixed(1)}`.padStart(8) +
    `${tr(enBuyuk)} tekil`.padStart(15));
}

derlem 1200 belge, tohum 20260801; ödünç kaydı 120.809 olay, 40.000 okur havuzu

kova alanı   kova   ölçüt  kesin tekil  kestirim p8   sapma  kestirim p12   sapma  en büyük kova
konu            6     144      786.432        1.536   %11.1        24.576    %1.6   15.257 tekil
on yıl          6     144      819.200        1.536    %6.5        24.576    %2.1   20.949 tekil
yıl            50   1.200    1.202.176       12.800   %18.5       204.800    %2.8    4.392 tekil
yazar          60   1.440    1.318.912       15.360   %14.8       245.760    %3.3    3.908 tekil
kitap       1.045  25.080    1.401.216      267.520   %33.1     4.280.320    %8.2      394 tekil

Bayt sütunları yapıların kendi tamponlarından okunur; ölçüt sütunu kova sayısı çarpı yirmi dörttür.

Ölçüt sütunu bir kova toplamasının neden ucuz sanıldığını gösteriyor: 1.045 kova için 25.080 bayt. Kova sayısı bin katına çıksa bile bu sütun megabayta ulaşmaz; “kova sayısı bellek yer” cümlesi ölçüt toplamasında neredeyse yanlıştır.

Tekil sayım sütunu başka bir dünyadır. Aynı 1.045 kova için kesin kümeler 1.401.216 bayt tutuyor, ölçüt durumunun elli beş katı. Kesin sütun kova sayısıyla birlikte fazla da artmıyor — altı kovada 786.432, bin kırk beş kovada 1.401.216 — çünkü maliyeti belirleyen kova sayısı değil, kovalara dağılmış farklı okur sayısıdır.

Kestirim sütunları kararın asıl yerini gösteriyor. Altı kovada p8 kestirimi 1.536 bayt istiyor, kesin kümenin beş yüz on ikide biri, karşılığında en kötü kovada yüzde 11,1 sapma. p12’ye çıkmak sapmayı yüzde 1,6’ya indiriyor ve maliyeti 24.576 bayta çıkarıyor — hâlâ kesinin otuz ikide biri. Ama son satırda işaret ters dönüyor: bin kırk beş kova için p12 kestirimi 4.280.320 bayt istiyor, kesin kümelerin üç katı. Kestirim kova başına sabit bir tampon ister; kovalar küçüldükçe o sabit, temsil etmesi gereken tekil sayısını geçer. M17/K06 bunu tek bir yapı için ölçmüştü; kova toplamasında aynı kırılma, kova sayısının kendisiyle gelir.

Hata payı da kova boyuyla okunur: en kötü sapma altı kovada yüzde 6,5 iken bin kırk beş kovada yüzde 33,1. Kestirimin hata payı toplam kardinalite üzerinden değil en küçük kova üzerinden değerlendirilmelidir; raporun yanlış çıkacağı yer büyük kovalar değil, küçük olanlardır.

Toplama Hangi Küme Üzerinde Çalışır

İkinci karar bellekle değil anlamla ilgilidir: toplama bütün derlem üzerinde mi, sorgunun eşleşen kümesi üzerinde mi, yoksa kullanıcının uyguladığı süzgeçten sonra kalan küme üzerinde mi hesaplanacak. Üçü üç ayrı sayı verir ve üçü de “doğru” olabilir.

// kova.mjs — toplama hangi kume uzerinde: derlem, eslesen kume, suzulmus kume; ve boru hatti.
import { belgeler, dizinKur, eslesenler } from "./derlem.mjs";
const dz = dizinKur(belgeler);
const eslesen = [...eslesenler(dz, "deniz gemi")].map((id) => belgeler[id]);
const suzulmus = eslesen.filter((b) => b.konu === "gezi");
const tr = (x) => Math.round(x).toLocaleString("tr-TR");
const kovala = (bs, f) => {                               // kova: anahtar -> sayi ve odunc
  const m = new Map();
  for (const b of bs) {
    const k = f(b), v = m.get(k) ?? { n: 0, odunc: 0 };
    v.n += 1; v.odunc += b.odunc; m.set(k, v);
  }
  return [...m].sort((x, y) => y[1].n - x[1].n || (x[0] < y[0] ? -1 : 1));
};

const derlemKova = new Map(kovala(belgeler, (b) => b.konu));
console.log(`konu kovaları — derlem ${belgeler.length}, eşleşen ${eslesen.length}, ` +
  `konu süzgecinden sonra ${suzulmus.length} belge\n`);
console.log("konu".padEnd(17) + "derlem".padStart(8) + "eşleşen".padStart(9) +
  "eşleşen ödünç".padStart(15) + "kitap başına".padStart(14));
for (const [k, v] of kovala(eslesen, (b) => b.konu))
  console.log(k.padEnd(17) + tr(derlemKova.get(k).n).padStart(8) + tr(v.n).padStart(9) +
    tr(v.odunc).padStart(15) + (v.odunc / v.n).toFixed(1).padStart(14));
console.log("aynı toplama süzülmüş küme üzerinde çalıştırılırsa kova sayısı: " +
  `${kovala(suzulmus, (b) => b.konu).length}`);

const yilKova = kovala(eslesen, (b) => `${b.yil}`);
const enBuyuk = [...yilKova].sort((x, y) => y[1].odunc - x[1].odunc);
const toplam = (l) => l.reduce((s, [, v]) => s + v.odunc, 0);
console.log(`\nboru hattı: yıl kovalarının ödünç toplamı üzerinde kümülatif pay`);
console.log("kova kümesi".padEnd(16) + "kova".padStart(6) + "ödünç".padStart(9) +
  "ilk üç kovanın payı".padStart(21) + "en yüksek kovanın payı".padStart(24));
for (const [ad, l] of [["tam", enBuyuk], ["ilk 10 kova", enBuyuk.slice(0, 10)],
  ["ilk 3 kova", enBuyuk.slice(0, 3)]]) {
  const t = toplam(l);
  console.log(ad.padEnd(16) + `${l.length}`.padStart(6) + tr(t).padStart(9) +
    `%${((toplam(l.slice(0, 3)) / t) * 100).toFixed(1)}`.padStart(21) +
    `%${((l[0][1].odunc / t) * 100).toFixed(1)}`.padStart(24));
}

konu kovaları — derlem 1200, eşleşen 325, konu süzgecinden sonra 168 belge

konu               derlem  eşleşen  eşleşen ödünç  kitap başına
gezi                  208      168         14.842          88.3
şiir                  208       35          3.761         107.5
bilim                 185       34          2.886          84.9
tarih                 206       33          2.937          89.0
edebiyat              220       30          3.875         129.2
çocuk edebiyatı       173       25          3.895         155.8
aynı toplama süzülmüş küme üzerinde çalıştırılırsa kova sayısı: 1

boru hattı: yıl kovalarının ödünç toplamı üzerinde kümülatif pay
kova kümesi       kova    ödünç  ilk üç kovanın payı  en yüksek kovanın payı
tam                 49   32.196                %15.4                    %5.4
ilk 10 kova         10   13.181                %37.6                   %13.1
ilk 3 kova           3    4.961               %100.0                   %34.8

İlk iki sütun aynı kovanın iki farklı sayısıdır. Derlemde 208 gezi kitabı var, “deniz gemi” sorgusunun eşleşen kümesinde 168 tane. Kullanıcıya “gezi (208)” yazan bir yüzey sorgudan bağımsız bir bilgi verir; “gezi (168)” sorgunun içinde gezinmeyi anlatır. İkisi karıştırıldığında toplam tutmaz: eşleşen sütunun toplamı 325, derlem sütununun toplamı 1.200.

Kitap başına ödünç sütunu ölçütün okunma kuralını gösteriyor: en yüksek değer 155,8 ile çocuk edebiyatı kovasında, ama o kovada yalnız 25 belge var. Yirmi beş belgeden çıkan ortalama ile yüz altmış sekiz belgeden çıkan ortalama aynı güvende değildir.

Süzme satırı gezinme yüzeylerinin klasik hatasını sayıya çeviriyor. Kullanıcı “gezi” seçtiğinde sonuç kümesi 168 belgeye iner ve aynı konu toplaması o küme üzerinde çalıştırılırsa tek kova döner: yüzeyde başka hiçbir konu görünmez, seçim değiştirilemez. Konu toplaması kendi süzgeci uygulanmadan önceki küme üzerinde, öteki süzgeçler uygulandıktan sonra hesaplanmalıdır. Toplama ile süzmenin sırası bir görsel tercih değil, kümeyi belirleyen bir karardır.

Boru hattı tablosu son sorunu gösteriyor. “İlk üç yılın toplam ödünç içindeki payı” sorusunun yanıtı elli kovanın hepsi görüldüğünde yüzde 15,4, yalnız en yüksek on kova görüldüğünde yüzde 37,6, üç kova görüldüğünde yüzde 100. Boru hattı toplaması girdisini belgelerden değil kovalardan aldığı için, girdisi kırpılmışsa çıktısı da yanlıştır ve yanlışlığı çıktıya bakarak anlaşılmaz — üç sayı da kendi içinde tutarlıdır. Kova kırpma bir sunum kararı gibi görünür, oysa boru hattının girdisini değiştirir.

Özet

• Toplama belge sırasını kullanmaz, kümeyi okur; kendi sırası kova sırasıdır ve kovalar sayıya, anahtara ya da ölçüte göre dizilebilir.
• Ölçüt kovası kova başına yirmi dört bayttır: 1.045 kova için 25.080 bayt. Tekil sayım kovası aynı kovalarda kesin kümelerle 1.401.216 bayt ister ve maliyeti kova sayısına değil kovalardaki farklı okur sayısına bağlıdır.
• Kardinalite kestirimi az kovada beş yüz kat kazandırır (altı kovada 1.536 bayta karşı 786.432), çok kovada kaybettirir: bin kırk beş kova için p12 kestirimi 4.280.320 bayt, kesinin üç katı.
• Kestirimin hata payı en küçük kovada okunur: en kötü sapma altı kovada yüzde 6,5, bin kırk beş kovada yüzde 33,1.
• Aynı konu toplaması derlem üzerinde 208, eşleşen küme üzerinde 168, kendi süzgecinden sonra tek kova verir; boru hattının yanıtı da girdisindeki kova sayısına göre yüzde 15,4 ile yüzde 100 arasında değişir.

Sonraki Adım

Toplamalar sayı üretti, sorgu değerlendiricisi sıralı bir liste üretti; ikisi de sonucun okura nasıl görüneceğini konuşmadı. Ekranda duran şey belge kimliği değil, kitabın adından ve özetinden alınmış bir parçadır; o parçanın hangi bölümünün seçileceği sorgunun hangi sözcüğünün nerede eşleştiğine bağlıdır ve bu bilgi puanlama sırasında tutulmadı. İkinci soru daha ağırdır: okur yirminci sayfaya geçtiğinde aynı sıralamanın nasıl korunacağı ve bunun kaç adayı bellekte tutmayı gerektirdiği sorulmadı. Sonraki ders sonuç sunumunu ve derin sayfalamanın maliyetini ele alır.