--- title: 'Kümeler ve Sıralı Kümeler' source: 'https://academia.sh/tr/kurslar/bellek-ici-depolar/kumeler-ve-sirali-kumeler' course: 'Bellek İçi Depolar ve Önbellek Sistemleri' language: tr updated: '2026-08-17T18:08:58+00:00' license: 'CC BY-SA 4.0' --- # Kümeler ve Sıralı Kümeler Üyelik ve sıra sorularının bellekteki fiyatı: aynı ödünçte olan kitaplar kümesinin liste, sıralı dizi ve karma tabanlı küme olarak kurulup sorgu adımı, ekleme adımı ve giriş başına bayt cinsinden ölçülmesi, popüler kitap sıralamasının üye–puan karması üzerine üç ayrı sıra dizini ile kurulması, atlamalı listenin gösterge maliyetinin sıra sorgusunu kaç adıma indirdiği ve sıralı dizinin güncelleme yükü altında hiçbir şey satın almadığı. 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). ```js // 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. ```js // 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.