--- title: 'Bit Eşlemler ve Olasılıksal Yapılar' source: 'https://academia.sh/tr/kurslar/bellek-ici-depolar/bit-eslemler-ve-olasiliksal-yapilar' course: 'Bellek İçi Depolar ve Önbellek Sistemleri' language: tr updated: '2026-08-17T18:08:57+00:00' license: 'CC BY-SA 4.0' --- # Bit Eşlemler ve Olasılıksal Yapılar Sayının kendisi yeterken üyelerin listesini tutmanın bedeli: aynı tekil okur sorusunun tam küme, bit eşlem, olasılıksal üyelik yapısı ve kardinalite kestirimiyle çözülmesi, dört yapının tuttuğu baytın kendi tamponundan okunması, yanlış olumlu oranının ölçülmesi ve kesinlikten vazgeçmenin kaç bayt satın aldığının sayılması. 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. ```js // 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. ```js // 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.