Uzamsal Dizinler

Akışın kimliği sıralanabilir olduğu için “şu andan sonrası” sorusu bir arama değil, bir konum belirlemesiydi. Kütüphanenin bir sorusu daha var ve o sorunun doğal bir sıralaması yok: okur, durduğu noktanın bir kilometre çevresindeki ödünç ve iade noktalarını istiyor. İki boyutlu bir konumu tek bir eksende sıralamanın her yolu bazı komşuları birbirinden uzağa düşürür; ne sıralı küme ne de akış bu soruya doğrudan yanıt verir.

Çözüm düzlemi hücrelere bölmek ve her noktaya bir uzamsal anahtar yazmaktır. Hücre boyunun nasıl seçileceği bu dersin konusu değildir; o karar Vaka Çalışmaları kursunun Veri Yoğun Sistemler konusunda, Konum Tabanlı Servis vakasında ölçülmüş ve verilmiştir. Burada tane bir girdidir ve sorulan şey başkadır: aynı yakınlık sorgusu bellek içi bir depoda hangi yapıyla kurulur, o yapı kaç bayt fazladan tutar ve karşılığında kaç adayı elemekten kurtarır.

Uzamsal Anahtar

Anahtar iki koordinatın bitlerinin sırayla dizilmesiyle üretilir: her eksen on altı bite niceleniyor, bitler dönüşümlü olarak yerleştiriliyor ve ortaya otuz iki bitlik tek bir sayı çıkıyor. Bu düzenin tek işe yarar özelliği şudur: bir hücrenin bütün noktaları anahtarın baştaki bitlerini paylaşır, dolayısıyla hücre sıralı bir dizide bitişik bir aralıktır. Kaç bitin paylaşıldığı taneyi belirler — ilk on iki bit 1 km’lik hücreyi, ilk on altı bit 0,25 km’lik hücreyi verir.

Kod	Varsayım	Değer	Gerekçe
BY18	ödünç ve iade noktası	120.000	şube, iade kutusu, okul ve istasyon noktaları
BY19	bölge	64 × 64 km	tek büyükşehir; düzlem yaklaşımı bir model basitleştirmesidir
BY20	temel kayıt	20 bayt	konum çifti 16 bayt, nokta kimliği 4 bayt
BY21	sorgu yarıçapı	1 km ve 0,25 km	yürüme mesafesi ve bina çevresi

BY21 bu dersin karar verdiren varsayımıdır: tek bir yarıçap olsaydı üç yapıdan ikisi ayırt edilemezdi.

Üç Yapı

Düzenek aynı 120.000 noktayı üç ayrı yapıya koyar ve aynı 300 sorguyu hepsine sorar. Bayt sayıları tamponların kendi boyundan, karma tabloların maliyeti ise kodda görünen bir formülden okunur.

// uzamsal.mjs — ayni yakinlik sorgusu uc bellek ici yapiyla: duz tarama, hucre kovasi ve
// uzamsal anahtarli sirali kume. Bayt sayilari tamponlardan ve acik bir formulden okunur.
// Bolge 64x64 km'lik bir duzlem olarak modellenir; noktalar kumelenmis, tohum gorunur.
const N = 120_000, KENAR = 64, SORGU = 300, TOHUM = 20260731, KUME = 24;
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 merkez = Array.from({ length: KUME }, () => [rast() * KENAR, rast() * KENAR]);
const nokta = () => {                                  // %35 duzgun, %65 kume cevresinde
  if (rast() < 0.35) return [rast() * KENAR, rast() * KENAR];
  const [mx, my] = merkez[Math.floor(rast() * KUME)];
  const a = rast() * 2 * Math.PI, r = -Math.log(1 - rast()) * 2.5;
  return [Math.min(KENAR - 1e-9, Math.max(0, mx + r * Math.cos(a))),
          Math.min(KENAR - 1e-9, Math.max(0, my + r * Math.sin(a)))];
};

const nx = new Float64Array(N), ny = new Float64Array(N), nid = new Int32Array(N);
for (let i = 0; i < N; i += 1) { const [x, y] = nokta(); nx[i] = x; ny[i] = y; nid[i] = 100000 + i; }
const TEMEL = nx.byteLength + ny.byteLength + nid.byteLength;

const yay = (v) => { v = (v | (v << 8)) & 0x00ff00ff; v = (v | (v << 4)) & 0x0f0f0f0f;
  v = (v | (v << 2)) & 0x33333333; v = (v | (v << 1)) & 0x55555555; return v >>> 0; };
const nicele = (u) => Math.min(65535, Math.floor((u / KENAR) * 65536));
const anahtar = (x, y) => ((yay(nicele(y)) << 1) | yay(nicele(x))) >>> 0;   // 32 bit uzamsal anahtar
const p2 = (n) => { let k = 1; while (k < n) k *= 2; return k; };

const ua = new Uint32Array(N), us = new Int32Array(N);   // sirali kume: anahtar + uye kimligi
for (let i = 0; i < N; i += 1) { ua[i] = anahtar(nx[i], ny[i]); us[i] = i; }
us.sort((a, b) => ua[a] - ua[b]);
const sa = new Uint32Array(N);
for (let i = 0; i < N; i += 1) sa[i] = ua[us[i]];
const SK_TABLO = p2(2 * N) * 8;                          // uye -> puan karma tablosu, yuva 8 bayt
const SK = sa.byteLength + us.byteLength + SK_TABLO;

const BIT = 6, KAYMA = 2 * (16 - BIT);                   // 2^6 = 64 hucre/eksen, hucre 1 km
const kovalar = new Map();
for (let i = 0; i < N; i += 1) {
  const h = Math.floor(ua[i] / 2 ** KAYMA);
  if (kovalar.has(h)) kovalar.get(h).push(i); else kovalar.set(h, [i]);
}
const dolu = kovalar.size;
const KOVA = p2(2 * dolu) * 12 + dolu * 8 + N * 4;       // yuva 12 + dizi ustverisi 8 + uye 4

const sorgular = Array.from({ length: SORGU }, nokta);
const tr = (x) => x.toLocaleString("tr-TR", { maximumFractionDigits: 2 });
const yakin = (q, i, R) => (nx[i] - q[0]) ** 2 + (ny[i] - q[1]) ** 2 <= R * R;
const altSinir = (v) => { let l = 0, r = N; while (l < r) {
  const m = (l + r) >> 1; if (sa[m] < v) l = m + 1; else r = m; } return l; };

function calis(R, bit) {                                 // sorgu kutusunu kaplayan hucreler
  const c = KENAR / 2 ** bit, k = Math.ceil(R / c), kayma = 2 * (16 - bit);
  let duzAday = 0, duzEs = 0, kovaAday = 0, kovaEs = 0, skAday = 0, skEs = 0, aralik = 0;
  for (const q of sorgular) {
    for (let i = 0; i < N; i += 1) { duzAday += 1; if (yakin(q, i, R)) duzEs += 1; }
    const cx = Math.floor(q[0] / c), cy = Math.floor(q[1] / c);
    for (let dy = -k; dy <= k; dy += 1) for (let dx = -k; dx <= k; dx += 1) {
      const x = cx + dx, y = cy + dy;
      if (x < 0 || y < 0 || x >= 2 ** bit || y >= 2 ** bit) continue;
      const h = ((yay(y) << 1) | yay(x)) >>> 0;
      if (bit === BIT) {                                 // hucre kovasi yalniz kendi tanesini bilir
        for (const i of kovalar.get(h) ?? []) { kovaAday += 1; if (yakin(q, i, R)) kovaEs += 1; }
      }
      const alt = h * 2 ** kayma, ust = alt + 2 ** kayma;   // sirali kumede bitisik aralik
      aralik += 1;
      for (let j = altSinir(alt); j < N && sa[j] < ust; j += 1) {
        skAday += 1; if (yakin(q, us[j], R)) skEs += 1;
      }
    }
  }
  return { duzAday: duzAday / SORGU, duzEs: duzEs / SORGU, kovaAday: kovaAday / SORGU,
    kovaEs: kovaEs / SORGU, skAday: skAday / SORGU, skEs: skEs / SORGU, aralik: aralik / SORGU, c };
}

console.log(`model: ${tr(N)} nokta, ${KENAR}x${KENAR} km, ${KUME} kume, ${SORGU} sorgu, tohum ${TOHUM}`);
console.log(`yogunluk ${tr(N / KENAR ** 2)} nokta/km2, dolu hucre ${tr(dolu)} (1 km tanesinde)\n`);
console.log("yapi".padEnd(30) + "temel bayt".padStart(12) + "dizin eki".padStart(12) +
  "uye basina ek".padStart(15) + "toplam".padStart(12));
for (const [ad, ek] of [["duz tarama (dizi)", 0], ["hucre kovasi, 1 km tane", KOVA],
                        ["uzamsal anahtarli sirali kume", SK]])
  console.log(ad.padEnd(30) + tr(TEMEL).padStart(12) + tr(ek).padStart(12) +
    (ek / N).toFixed(2).padStart(15) + tr(TEMEL + ek).padStart(12));

console.log("\nsorgu basina taranan aday (ayni 300 sorgu, ayni yaricap)");
console.log("yaricap".padEnd(10) + "tane".padStart(9) + "hucre".padStart(7) + "duz".padStart(10) +
  "kova".padStart(9) + "s.kume".padStart(9) + "eslesme (duz/kova/s.kume)".padStart(27));
for (const [R, bit] of [[1, BIT], [0.25, BIT], [0.25, 8]]) {
  const s = calis(R, bit), k = bit === BIT;
  console.log(`${R} km`.padEnd(10) + `${KENAR / 2 ** bit} km`.padStart(9) +
    s.aralik.toFixed(0).padStart(7) + tr(s.duzAday).padStart(10) +
    (k ? tr(s.kovaAday) : "-").padStart(9) + tr(s.skAday).padStart(9) +
    `${s.duzEs.toFixed(2)} / ${k ? s.kovaEs.toFixed(2) : "-"} / ${s.skEs.toFixed(2)}`.padStart(27));
}

model: 120.000 nokta, 64x64 km, 24 kume, 300 sorgu, tohum 20260731
yogunluk 29,3 nokta/km2, dolu hucre 4.096 (1 km tanesinde)

yapi                            temel bayt   dizin eki  uye basina ek      toplam
duz tarama (dizi)                2.400.000           0           0.00   2.400.000
hucre kovasi, 1 km tane          2.400.000     611.072           5.09   3.011.072
uzamsal anahtarli sirali kume    2.400.000   3.057.152          25.48   5.457.152

sorgu basina taranan aday (ayni 300 sorgu, ayni yaricap)
yaricap        tane  hucre       duz     kova   s.kume  eslesme (duz/kova/s.kume)
1 km           1 km      9   120.000   821,22   821,22   372.25 / 372.25 / 372.25
0.25 km        1 km      9   120.000   821,22   821,22      40.90 / 40.90 / 40.90
0.25 km     0.25 km      9   120.000        -    97,39          40.90 / - / 40.90

Bu sayılar ölçüm sınıfındadır; aday ve eşleşme sayıları tohuma ve kümelenme parametrelerine bağlı, bayt sayıları bağlı değil — onlar tampon boylarıdır.

Son sütun her satırda üç yapının aynı eşleşmeyi bulduğunu söylüyor: 1 km’de 372,25, 0,25 km’de 40,90. Dizin bir yaklaşıklık değil, bir ön elemedir; kesin uzaklık her adayda ayrıca hesaplanır ve hiçbir yapı bir sonucu kaçırmaz.

Ek Baytın Karşılığı

Üç yapı da aynı 2.400.000 baytlık temel kaydı taşıyor; fark dizin eki sütunundadır. Hücre kovası üye başına 5,09 bayt ekliyor ve sorgu başına taranan adayı 120.000’den 821,22’ye indiriyor — yüz kırk altı kat. Bu, dersteki en ucuz kazanç: 611.072 bayt karşılığında sorgu maliyetinin yüzde 99,3’ü gidiyor.

Sıralı küme aynı sorguda hiçbir şey kazandırmıyor. Üye başına 25,48 bayt, yani hücre kovasının beş katı yer tutuyor ve 1 km sorgusunda tastamam aynı 821,22 adayı tarıyor. Bu satır tek başına okunursa sıralı küme kötü bir seçimdir.

Ek baytın nereye gittiği de sayılabilir: 3.057.152 baytın 2.097.152’si, yani yüzde 68,6’sı, üye kimliğinden anahtara giden karma tablodur. Bu tablo sorgu için değil güncelleme için tutulur. Gezici kütüphane durağı yer değiştirdiğinde üyenin sıralı dizideki eski yerini bulmak gerekir; tablo olmadan bu, dizinin taranması demektir. Noktalar hiç kımıldamasaydı sıralı kümenin eki üye başına 25,48 bayttan 8 bayta inerdi — o durumda hücre kovasından yalnız üç bayt pahalı olurdu.

Tane Sorgu Anında Seçilirse

Farkı ikinci ve üçüncü satır gösteriyor. Okur bina çevresini, yani 0,25 km’yi sorduğunda hücre kovası hâlâ 821,22 aday tarıyor: kovalar ekleme anında 1 km’lik taneye göre kurulmuştur ve daha ince bir soru sorulduğunda kova yine dokuz kilometrekarelik alanı döndürür. Daha ince bir tane istemek, bütün kovaların yeniden kurulması demektir.

Sıralı kümede anahtar otuz iki bitin tamamını taşıdığı için her önek uzunluğu geçerli bir aralıktır. Aynı 0,25 km sorgusu ilk on altı biti kullanarak sorulduğunda taranan aday 97,39’a iniyor: sekiz kat az iş ve aynı 40,90 eşleşme. Sıralı kümenin satın aldığı şey adaydan tasarruf değil, taneyi ekleme anında değil sorgu anında seçebilme yeteneğidir.

Bu, üç yapıyı bir karar tablosuna oturtur. Düz tarama sıfır ek bayt tutar ve her sorguda yüz yirmi bin kayda dokunur; nokta sayısı birkaç bini geçmiyorsa doğru seçimdir. Hücre kovası sorgu yarıçapı sabitse en ucuz dizindir ve 5,09 baytla adayın yüzde 99,3’ünü eler. Uzamsal anahtarlı sıralı küme, yarıçap sorgudan sorguya değiştiğinde ya da noktalar yer değiştirdiğinde 25,48 baytı hak eder; sabit yarıçaplı ve durağan bir kümede o bayt boşa gider.

Özet

• Uzamsal anahtar iki koordinatın bitlerini dönüşümlü dizerek tek bir sıralanabilir sayı üretir; bir hücre böylece sıralı dizide bitişik bir aralık olur ve önek uzunluğu taneyi belirler.
• Üç yapı da aynı sonucu döndürür: 1 km’de 372,25, 0,25 km’de 40,90 eşleşme. Dizin bir yaklaşıklık değil ön elemedir ve kesin uzaklık her adayda ayrıca hesaplanır.
• Hücre kovası dersin en ucuz kazancıdır: üye başına 5,09 bayt karşılığında taranan aday 120.000’den 821,22’ye iner, yani sorgu maliyetinin yüzde 99,3’ü gider.
• Sıralı küme üye başına 25,48 bayt ister ve kendi tanesindeki sorguda hiçbir aday kazandırmaz; bu baytın yüzde 68,6’sı sorgu için değil, üyenin yerini güncelleyebilmek için tutulan karma tablodur.
• Fazladan baytın karşılığı yarıçap değiştiğinde görünür: 0,25 km sorgusunda hücre kovası 821,22, sıralı küme 97,39 aday tarar, çünkü tane ekleme anında değil sorgu anında seçilir.

Sonraki Adım

Yakınlık sorgusu bir liste döndürüyor ve iş orada bitmiyor. Okur listeden bir noktayı seçtiğinde kütüphane şunları yapmak zorunda: o noktadaki kopya sayısını okumak, okurun açık ödünç sınırını denetlemek, kopya sayısını bir azaltmak, ödünç kümesine kaydı eklemek ve etkinlik akışına giriş yazmak. Buraya kadarki her yapı bu adımlardan birini atomik yapabiliyor; beşini birden yapabilen bir şey görülmedi. Adımlar tek tek gönderildiğinde araya başka bir okurun aynı kopyayı alması sığar. Sonraki ders bu çok adımlı işi iki biçimde kurar ve aradaki farkı gidiş sayısı, yarış penceresi ve engellenen süre olarak sayar.