Uzlaşma

Önceki ders eşleme kuralını liste düzeyinde kurdu: hangi kaydın hangi düğüme karşılık geldiğini anahtar belirler. Eşleştikten sonrası açık kaldı — öznitelikleri nasıl karşılaştırılır, çocukları hangi sırayla gezilir, türü değiştiğinde ne olur.

Bu ders bu kuralların tamamını tek bir algoritmada toplar. Algoritmanın adı uzlaşma (reconciliation) dır: girdisi iki görünüm tanımı, çıktısı ağaca uygulanacak işlemlerin listesidir.

Uzlaşmanın Girdisi ve Çıktısı

Çerçeve, en son ürettiği görünüm tanımını bellekte tutar. Bu saklanan tanıma sanal ağaç (virtual tree) denir: belge ağacının o anki hâlinin sade veriden yapılmış bir kopyası.

Durum değiştiğinde yeni bir tanım üretilir ve iki tanım karşılaştırılır. Karşılaştırmanın sonucu bir yama listesidir — düğüm oluştur, kaldır, taşı, öznitelik yaz, metin yaz. Belge ağacına yalnızca bu liste uygulanır.

Sanal ağacın varlık nedeni buradadır. Karşılaştırma belge ağacı üzerinde yapılsaydı, her adımda ağaçtan okuma yapılırdı; ağaçtan okumak yerleşim hesabını tetikleyebilir ve Başarım Kaydı dersindeki yerleşim sarsıntısını üretir. Sade veriden yapılmış bir kopya üzerinde karşılaştırma yapmak bu okumaları ortadan kaldırır.

Karşılaştırmayı Ucuzlatan Üç Varsayım

İki sıralı ağaç arasındaki en küçük dönüşüm dizisini bulmak, ağaç boyutuna göre kübik mertebede bir iştir. Her karede yapılamayacak kadar pahalıdır. Uzlaşma bu problemi üç varsayımla doğrusala indirir.

Türü değişen düğümün alt ağacı karşılaştırılmaz. Bir konumda liste ögesi yerine bölüm ögesi belirmişse, eski alt ağaç bütünüyle atılır ve yenisi baştan kurulur. Varsayımın gerekçesi, farklı türde iki ögenin farklı yapılar üretmesinin beklenmesidir. Bedeli, aynı içeriği taşıyan iki farklı sarmalayıcı arasında geçiş yapmanın bütün alt ağacı — ve içindeki durumu — yeniden kurmasıdır.

Karşılaştırma düzey düzeyde yapılır. Bir düğümün başka bir düzeye taşınmış olabileceği hiç denenmez. Bir satırın tablodan çıkıp bir açılır panele girmesi, taşıma değil kaldırma ve oluşturma olarak görülür.

Kardeşler anahtarla eşleşir. Önceki dersin kuralı, algoritmanın çocuk gezinme adımıdır. Anahtarı olmayan kardeşler konumlarına göre eşleşir.

Algoritma

Aşağıdaki gerçekleştirim bu üç varsayımı uygular ve yama listesini üretir.

// uzlasma.mjs — iki gorunum tanimini karsilastirip yama listesi uretir
const oge = (ad, ozn = {}, cocuklar = [], anahtar = null) =>
  ({ ad, ozn, cocuklar, anahtar });

function gorunum(durum) {
  return oge("section", { class: "pano" }, [
    oge("h2", {}, [`Kuzey Yamaç — ${durum.olcumler.length} ölçüm`]),
    oge("ul", { class: "tablo" }, durum.olcumler.map((o) =>
      oge("li", { class: o.deger >= o.esik ? "rozet asim" : "rozet" },
        [`${o.ad}: ${o.deger} ${o.birim}`], o.kimlik))),
  ]);
}

// Eski siralamasi artan kalan en uzun alt dizi: yerinde kalabilecek dugumler.
function enUzunArtanAltDizi(dizi) {
  const kuyruk = [], geri = [];
  for (const [k, deger] of dizi.entries()) {
    let alt = 0, ust = kuyruk.length;
    while (alt < ust) {
      const orta = (alt + ust) >> 1;
      if (dizi[kuyruk[orta]] < deger) alt = orta + 1; else ust = orta;
    }
    geri[k] = alt > 0 ? kuyruk[alt - 1] : -1;
    kuyruk[alt] = k;
  }
  const sonuc = new Set();
  for (let k = kuyruk.at(-1); k !== undefined && k !== -1; k = geri[k]) sonuc.add(k);
  return sonuc;
}

function uzlas(eski, yeni, yol, yamalar) {
  if (typeof eski === "string" || typeof yeni === "string") {
    if (eski !== yeni) yamalar.push(`METIN   ${yol}  ${JSON.stringify(yeni)}`);
    return;
  }
  // 1. Tur ya da anahtar farkliysa alt agac karsilastirilmaz, yenisiyle degistirilir.
  if (eski.ad !== yeni.ad || eski.anahtar !== yeni.anahtar) {
    yamalar.push(`DEGISTIR ${yol}  <${eski.ad}> → <${yeni.ad}>`);
    return;
  }
  // 2. Oznitelikler iki yonlu karsilastirilir.
  for (const [k, v] of Object.entries(yeni.ozn))
    if (eski.ozn[k] !== v) yamalar.push(`OZNITELIK ${yol}  ${k}=${JSON.stringify(v)}`);
  for (const k of Object.keys(eski.ozn))
    if (!(k in yeni.ozn)) yamalar.push(`SIL-OZN ${yol}  ${k}`);
  // 3. Cocuklar: anahtarli olanlar anahtarla, anahtarsizlar konumla eslesir.
  const eskiSira = new Map();
  eski.cocuklar.forEach((c, i) =>
    eskiSira.set(typeof c === "string" || c.anahtar === null ? `#${i}` : c.anahtar, i));
  const eslesenler = [];
  yeni.cocuklar.forEach((c, i) => {
    const anahtar = typeof c === "string" || c.anahtar === null ? `#${i}` : c.anahtar;
    const eskiDizin = eskiSira.get(anahtar);
    if (eskiDizin === undefined) yamalar.push(`OLUSTUR ${yol}/${i}  ${anahtar}`);
    else eslesenler.push({ i, eskiDizin, anahtar });
  });
  for (const [anahtar, i] of eskiSira)
    if (!eslesenler.some((e) => e.anahtar === anahtar))
      yamalar.push(`KALDIR  ${yol}/${i}  ${anahtar}`);
  const kalanlar = enUzunArtanAltDizi(eslesenler.map((e) => e.eskiDizin));
  eslesenler.forEach((e, k) => {
    if (!kalanlar.has(k)) yamalar.push(`TASI    ${yol}/${e.eskiDizin} → ${yol}/${e.i}  ${e.anahtar}`);
    uzlas(eski.cocuklar[e.eskiDizin], yeni.cocuklar[e.i], `${yol}/${e.i}`, yamalar);
  });
}

const O = (kimlik, ad, deger, birim, esik) => ({ kimlik, ad, deger, birim, esik });
const ONCE = { olcumler: [
  O("s1", "Sıcaklık", -4.2, "°C", 30), O("n1", "Bağıl nem", 72, "%", 90),
  O("r1", "Rüzgâr", 11.4, "m/s", 25), O("k1", "Kar derinliği", 38, "cm", 60),
] };
const SONRA = { olcumler: [
  O("k1", "Kar derinliği", 38, "cm", 60), O("s1", "Sıcaklık", -4.2, "°C", 30),
  O("n1", "Bağıl nem", 94, "%", 90), O("b1", "Basınç", 964, "hPa", 1050),
] };

const yamalar = [];
uzlas(gorunum(ONCE), gorunum(SONRA), "kok", yamalar);
const sayilan = (tanim) => typeof tanim === "string"
  ? 1 : 1 + tanim.cocuklar.reduce((t, c) => t + sayilan(c), 0);
console.log(`tanimdaki dugum sayisi: ${sayilan(gorunum(SONRA))}`);
console.log(`uretilen yama sayisi  : ${yamalar.length}\n`);
console.log(yamalar.join("\n"));

tanimdaki dugum sayisi: 12
uretilen yama sayisi  : 5

OLUSTUR kok/1/3  b1
KALDIR  kok/1/2  r1
TASI    kok/1/3 → kok/1/0  k1
OZNITELIK kok/1/2  class="rozet asim"
METIN   kok/1/2/0  "Bağıl nem: 94 %"

Aynı anda dört şey değişmiştir: bir ölçüm eklenmiş, biri çıkarılmış, liste yeniden sıralanmış ve bir ölçümün değeri eşiği aşmıştır. On iki düğümlük tanım için beş yama üretilmiştir.

Tek taşıma yeterlidir. Dört satırın sırası değişmiş olsa da, eski sıralaması artan kalan en uzun alt dizide bulunan satırlar yerinde bırakılmış, yalnızca kar derinliği taşınmıştır.

Eşik aşımı iki ayrı yama üretmiştir. Bağıl nemin sınıfı ve metni ayrı alanlardır; her alan kendi karşılaştırmasından geçer. Bu ayrım, öznitelik yazmanın metin yazmaktan farklı bir maliyeti olması nedeniyle korunur.

Başlık hiç yama üretmemiştir. Ölçüm sayısı dörtte kaldığı için başlığın metni değişmemiştir; karşılaştırma bunu görmüş ve hiçbir işlem yazmamıştır. Bir alanın karşılaştırılması ile yazılması arasındaki fark budur: karşılaştırma ucuz, yazma pahalıdır.

Değişen ölçümün kendisi taşınmamıştır. Kaldırma, oluşturma ve taşıma anahtarla çözüldüğü için, güncellenen satır listede yer değiştirmiş olmasına rağmen kendi düğümünde kalmıştır. Anahtar olmasaydı bu satır da yeniden yazılırdı.

Maliyet Nerede

Uzlaşma, üretilen tanımın büyüklüğüne göre doğrusaldır. Buradan pratik bir sonuç çıkar: maliyeti düşürmenin yolu karşılaştırmayı hızlandırmak değil, daha küçük bir tanım üretmektir.

Tanımın büyüklüğünü belirleyen şey, üçüncü derste ölçülen yeniden çizim alanıdır. Kökteki bir durum değiştiğinde bütün ağaç yeniden çizilir ve tanımın tamamı üretilip karşılaştırılır. Durumu olabildiğince aşağıda tutmak, girdisi değişmemiş alt ağaçların üretimini atlamak ve pahalı hesapların sonucunu saklamak bu alanı daraltan araçlardır; son ikisi kursun ilerleyen konularında ele alınır.

Karşılaştırma Yapmayan Yaklaşımlar

Uzlaşma, “hangi değerin hangi düğümü etkilediği” sorusunu her seferinde yeniden çözer. Aynı soruyu bir kez çözüp saklamak da olanaklıdır ve çerçeve ailelerini ayıran temel tasarım farkı budur.

// yaklasimlar.mjs — tek bir olcum degeri degistiginde uc yaklasimin yaptigi is
const N = 12;
const OLCUMLER = Array.from({ length: N }, (_, i) => ({
  kimlik: `s${i}`, ad: `Sensör ${String(i + 1).padStart(2, "0")}`, deger: 10 + i,
}));
const DEGISEN = 6, YENI_DEGER = 17.5;
const satirMetni = (o) => `${o.ad}: ${o.deger}`;

// --- A) Sanal agac: tanimi yeniden uret, eskisiyle karsilastir ---------------
let uretim = 0, karsilastirma = 0, yazmaA = 0;
const oge = (ad, cocuklar) => { uretim++; return { ad, cocuklar }; };
const metin = (s) => { uretim++; return s; };
const gorunum = (olcumler) =>
  oge("ul", olcumler.map((o) => oge("li", [metin(satirMetni(o))])));

function uzlas(eski, yeni, agac) {
  karsilastirma++;
  if (typeof yeni === "string") {
    if (eski !== yeni) { agac.metinler[agac.k] = yeni; yazmaA++; }
    agac.k++;
    return;
  }
  eski.cocuklar.forEach((c, i) => uzlas(c, yeni.cocuklar[i], agac));
}

const agacA = { metinler: OLCUMLER.map(satirMetni), k: 0 };
const eskiTanim = gorunum(OLCUMLER);
uretim = 0;                                    // ilk cizim sayilmaz
const yeniOlcumler = OLCUMLER.map((o, i) =>
  i === DEGISEN ? { ...o, deger: YENI_DEGER } : o);
uzlas(eskiTanim, gorunum(yeniOlcumler), agacA);

// --- B) Tepkisel bagimlilik takibi: baglama okudugu hucreye abone olur -------
let kayitB = 0, yazmaB = 0;
const agacB = { metinler: OLCUMLER.map(satirMetni) };
const hucreler = OLCUMLER.map((o, i) => {
  const hucre = { deger: o.deger, aboneler: [] };
  hucre.aboneler.push((v) => { agacB.metinler[i] = `${o.ad}: ${v}`; yazmaB++; });
  kayitB++;                                     // kurulumda bir abonelik kaydi
  return hucre;
});
const hucreYaz = (i, v) => {
  hucreler[i].deger = v;
  for (const abone of hucreler[i].aboneler) abone(v);
};
hucreYaz(DEGISEN, YENI_DEGER);

// --- C) Derleme zamaninda tepkisellestirme: eslesme derleyiciden gelir -------
// Derleyici sablonu okur: satir metni yalnizca "deger" alanina baglidir.
let yazmaC = 0;
const agacC = { metinler: OLCUMLER.map(satirMetni) };
const DERLENMIS = {
  deger: (i, v) => { agacC.metinler[i] = `${OLCUMLER[i].ad}: ${v}`; yazmaC++; },
};
DERLENMIS.deger(DEGISEN, YENI_DEGER);

// --- Sonuc ------------------------------------------------------------------
const beklenen = yeniOlcumler.map(satirMetni);
const ayni = (m) => JSON.stringify(m) === JSON.stringify(beklenen);
console.log(`${N} satirlik tabloda tek bir olcum degeri degisti\n`);
console.log("yaklasim".padEnd(26) + "kurulum  uretim  karsilastirma  yazma  sonuc");
console.log(`${"sanal agac".padEnd(26)}${String(0).padEnd(9)}${String(uretim).padEnd(8)}` +
  `${String(karsilastirma).padEnd(15)}${String(yazmaA).padEnd(7)}${ayni(agacA.metinler)}`);
console.log(`${"tepkisel bagimlilik".padEnd(26)}${String(kayitB).padEnd(9)}${String(0).padEnd(8)}` +
  `${String(0).padEnd(15)}${String(yazmaB).padEnd(7)}${ayni(agacB.metinler)}`);
console.log(`${"derleme zamani".padEnd(26)}${String(0).padEnd(9)}${String(0).padEnd(8)}` +
  `${String(0).padEnd(15)}${String(yazmaC).padEnd(7)}${ayni(agacC.metinler)}`);

12 satirlik tabloda tek bir olcum degeri degisti

yaklasim                  kurulum  uretim  karsilastirma  yazma  sonuc
sanal agac                0        25      25             1      true
tepkisel bagimlilik       12       0       0              1      true
derleme zamani            0        0       0              1      true

Üç yaklaşım aynı sonucu üretir; yaptıkları iş farklıdır.

Sanal ağaç tutan yaklaşım güncelleme başına tanımın tamamını üretir ve gezer: yirmi beş düğüm üretimi, yirmi beş karşılaştırma, bir yazma. Karşılığında hiçbir şey kaydetmez ve görünüm işlevine hiçbir kısıt koymaz — koşul, döngü, yardımcı işlev, hepsi sıradan koddur.

Tepkisel bağımlılık takibi yapan yaklaşım, kurulumda hangi bağlamanın hangi değeri okuduğunu kaydeder. Güncellemede tanım üretmez ve karşılaştırma yapmaz; doğrudan ilgili bağlamayı çalıştırır. Bedeli, her bağlama için tutulan kayıt ve okumaların izlenebilir olması zorunluluğudur: değerlere doğrudan değil, izlenen bir sarmalayıcı üzerinden erişilir.

Derleme zamanında tepkiselleştiren yaklaşım aynı eşlemeyi çalışma zamanında değil, derleyicide kurar. Şablonun hangi parçasının hangi alanı okuduğu derlemede bellidir; çıktı, doğrudan o alanı yazan koddur. Çalışma zamanında ne kayıt tutulur ne karşılaştırma yapılır. Bedeli, bir derleme adımının zorunlu olması ve şablon dilinin çözümlenebilir kalacak kadar kısıtlı tutulmasıdır: derleyicinin göremediği devingen yapılar bu eşlemenin dışında kalır.

Tabloda görünmeyen bir ödünleşim daha vardır. Sanal ağaç yaklaşımında güncelleme maliyeti yeniden çizilen alanla, diğer ikisinde değişen değer sayısıyla orantılıdır. Küçük bir arayüzde fark ölçülemez; on beş rozetin saniyede birkaç kez güncellendiği bir panoda belirginleşir. Seçimi yalnızca bu sayı belirlemez — kursun son konusu ölçütlerin tamamını ele alır.

Özet

• Uzlaşma, yeni görünüm tanımı ile saklanan öncekini karşılaştırıp yama listesi üretir; saklanan tanıma sanal ağaç denir ve belge ağacından okuma yapılmasını önler.
• İki sıralı ağaç arasındaki en küçük dönüşümü bulmak kübik mertebededir; üç varsayım — tür değişiminde alt ağacı atmak, düzey düzey karşılaştırmak, kardeşleri anahtarla eşlemek — problemi doğrusala indirir.
• Varsayımların bedeli vardır: sarmalayıcı türünü değiştirmek alt ağacı ve durumunu yeniden kurar, düzey değiştiren bir düğüm taşınmaz, kaldırılıp yeniden oluşturulur.
• Karşılaştırma ucuz, yazma pahalıdır; değişmeyen alanlar için hiçbir yama üretilmez.
• Uzlaşmanın maliyeti üretilen tanımın büyüklüğüne bağlıdır; düşürmenin yolu daha küçük bir tanım üretmek, yani yeniden çizim alanını daraltmaktır.
• Aynı işi tepkisel bağımlılık takibi kurulumda tutulan kayıtla, derleme zamanı yaklaşımı derleyicideki eşlemeyle çözer; ilki izlenebilir erişim, ikincisi kısıtlı bir şablon dili ve derleme adımı ister.

Sonraki Adım

Bu konu, arayüzün durumdan nasıl üretildiğini ve üretilenin ağaca nasıl yansıdığını kurdu: görünüm bir işlevdir, bileşen bu işlevin sözleşmeli bir parçasıdır, şablon işaretlemeyi veriye bağlar, anahtar kimliği korur, uzlaşma farkı yamaya çevirir. Geriye çözülmeyen bir şey kaldı: durumun kendisi. Uzlaşma her zaman bir yeniden çizimden sonra çalışır — peki yeniden çizimi ne başlatır? Bir olay işleyicisi iki değeri arka arkaya güncellediğinde iki kez mi çizilir, yoksa güncellemeler toplu mu işlenir? Bir bileşenin yerel durumu tam olarak nerede tutulur ve o değeri güncelleyen çağrı, hemen sonraki satırda okunduğunda neyi döndürür? Sonraki konu, Bileşen Yaşam Döngüsü ve Durum, Yerel Durum dersiyle bu sorularla başlar.