Bölüm 13: Çevrimiçi Algoritmalar

13.1Çevrimiçi problem modeli

Bir algoritmanın girdisi iki biçimde gelebilir. Birinci biçimde girdinin tamamı algoritma çalışmaya başlamadan hazırdır. İkinci biçimde girdi zaman içinde, parça parça açığa çıkar. Algoritma her parçaya o anda bir cevap vermek zorundadır. Bu bölüm ikinci biçimi inceler. Önce modelin kendisi, sonra bu modelde “iyi algoritma” kavramının nasıl ölçüldüğü ele alınır.

13.1.1Bilgi parça parça gelince

Gündelik kararların çoğu eksik bilgiyle verilir. Satranç oyuncusu rakibin bir sonraki hamlesini bilmeden hamlesini yapar. Hamle bir kez yapılınca geri alınamaz. Rakip hamlesini yaptıktan sonra oyuncu “keşke öbür taşı oynasaydım” diyebilir, ama tahtadaki durum değişmez. Bir sürücü de trafik sıkışıklığında hangi yola sapacağına o anki bilgiyle karar verir. Yolun ileride kapalı olduğunu ancak oraya varınca öğrenir.

Labirentte yürüyen bir yolcu bu durumun iyi bir örneğidir. Labirentin tamamı görünmez; yolcu yalnız önündeki koridoru görür. Her kavşakta o ana kadar gördükleriyle bir yön seçer. Kuşbakışı haritası olan biri aynı labirentte en kısa yolu hiç yanılmadan bulur. Yolcu ise bazı çıkmazlara girmek zorunda kalır. Çevrimiçi algoritmanın sorusu şudur: haritası olmayan yolcu, haritası olana göre en kötü durumda ne kadar fazla yol yürür?

Bilgisayar sistemlerinde de aynı yapı sık görülür. Trafik ışıklarını yöneten bir program, kavşaktaki yoğunluğu anlık olarak ölçer ve yeşil ışığın süresini buna göre ayarlar. Program bir dakika sonra hangi yönden kaç araç geleceğini bilmez. Beklemek de bir seçenek değildir: ışığın şimdi bir renk göstermesi gerekir. Çevrimiçi algoritma (online algorithm) bu koşullarda çalışan algoritmadır.

Tanımdaki iki koşul birlikte önemlidir. Birincisi, gelecek bilinmez: σ_t geldiğinde σ_t+1 hakkında hiçbir bilgi yoktur. İkincisi, verilen karar geri alınamaz. Yalnız birinci koşul olsaydı algoritma bütün girdiyi bekleyip sonra karar verebilirdi. Yalnız ikinci koşul olsaydı geleceği bilen algoritma her seferinde doğru kararı verirdi. Zorluk iki koşulun bir arada olmasından doğar.

13.1.2Çevrimiçi ve çevrimdışı

İki model arasındaki fark, girdinin içeriğinde değil, algoritmanın girdiyi ne zaman gördüğündedir. Aynı istek dizisi iki modelde de işlenebilir. Çevrimdışı algoritma bütün diziye bakar, en iyi kararları hesaplar ve sonra uygular. Çevrimiçi algoritma her isteğe geldiği anda cevap verir. Tablo 13.1 iki modeli beş açıdan karşılaştırır.

Tablodaki son satır bölümün ana fikrini taşır. Çevrimdışı bir algoritma için “iyi” demek çoğunlukla “hızlı” demektir. Algoritma en iyi çözümü bulur; soru, bunu ne kadar sürede bulduğudur. Çevrimiçi bir algoritma ise en iyi çözümü çoğu zaman bulamaz, çünkü en iyi çözüm geleceğe bağlıdır. Burada soru, verilen kararların toplam maliyetinin en iyi çözümden ne kadar uzak olduğudur. Bu uzaklığı ölçen sayıya rekabet oranı denir.

“Çevrimiçi” sözcüğü burada internet bağlantısı anlamına gelmez. Sözcük girdinin zaman içinde açığa çıkmasını anlatır. Bir sıralama algoritması bile çevrimiçi çalışabilir ya da çalışamaz. Bunu görmek için iki tanıdık sıralama algoritmasına bakmak yeterlidir.

13.1.3Sınırlı bellek ve öğe başına iş

Çevrimiçi modelin pratikteki en yaygın biçimi sürekli gelen veridir. Algılayıcılar saniyede binlerce ölçüm üretir. Bir ağ yönlendiricisinden her saniye milyonlarca paket geçer. Bu verinin tamamını saklamak çoğu zaman olanaksızdır. Şekil 13.1 bu durumu gösterir: veri algoritmaya sürekli gelir, algoritma küçük bir tamponla (buffer) çalışır ve hemen çıktı üretir.

Tampon girdinin tamamını tutamıyorsa geçmiş ancak bir özet olarak saklanabilir. Özet; bir toplam, bir sayaç, iki heap ya da küçük bir örneklem olabilir. Doğru özeti seçmek, akış algoritması tasarımının özüdür. Bir özetin iki özelliği olmalıdır. Birincisi, yeni bir öğe geldiğinde özet hızla güncellenebilmelidir. İkincisi, sorulan soru özetten cevaplanabilmelidir. Örneğin “şu ana kadarki ortalama nedir?” sorusu için öğe sayısı ile toplam yeterlidir. Her yeni öğede toplam ve sayaç birer kez güncellenir, ortalama bir bölmeyle bulunur.

Bu yüzden akış algoritmalarında iki maliyet ölçülür: öğe başına iş ve bellek. Öğe başına işin çoğunlukla O(1) ya da O(log n) olması istenir. Öğe başına O(n) iş yapan bir algoritma, n öğe geldiğinde toplam O(n²) iş yapar. Saniyede bir milyon öğe gelen bir akışta bu kabul edilemez. Bellek de akışın uzunluğundan bağımsız ya da ona göre çok küçük olmalıdır.

13.1.4Uygulama alanları

Çevrimiçi problemler bilgisayar biliminin hemen her alanında karşımıza çıkar. Tablo 13.2 başlıca örnekleri toplar. Örneklerin ortak noktası üçtür: ortam dinamiktir, karar gerçek zamanlı verilir ve geleceğe dair bilgi eksiktir.

Bu alanların bazılarında karar geri alınamaz, bazılarında ise geri almak pahalıdır. Önbellekten atılan bir sayfa geri yüklenebilir, ama yükleme bir maliyet doğurur. Gösterilen bir reklam geri alınamaz; reklam yeri başka bir reklama verilemez. Model hep aynıdır: her kararın bir maliyeti vardır ve toplam maliyet en aza indirilmek istenir.

13.1.5Güçlü ve zayıf yanlar

Çevrimiçi algoritmaların en büyük gücü beklememeleridir. Girdinin bitmesini beklemezler; dinamik ortamlarda çalışırlar. Karar anında verildiği için gecikme düşüktür. Az bellekle çok büyük, hatta sonsuz akışları işleyebilirler. Rekabet oranı sayesinde en kötü durum için de bir garanti verilebilir: “ne olursa olsun, maliyet en iyi çözümün iki katını geçmez” gibi.

Zayıf yanlar da aynı yerden gelir. İlk adımlarda verilen yanlış bir karar sonraki adımları etkiler. Satrançta tek bir kötü hamle oyunu kaybettirebilir. Çevrimiçi algoritma en iyi küresel çözümü bulmayı garanti etmez. Başlangıçtaki girdiye duyarlıdır: aynı algoritma bir dizide çok iyi, başka bir dizide kötü sonuç verebilir. Tasarımı ve analizi de çevrimdışı algoritmalarınkinden daha zordur. Analiz, algoritmanın davranışını henüz görülmemiş bütün olası geleceklere karşı değerlendirmek zorundadır.

13.1.6Tasarım yaklaşımları

Çevrimiçi algoritmalar birkaç ortak fikir üzerine kurulur. Bu fikirler birbirini dışlamaz; bir algoritma birkaçını birlikte kullanabilir.

• Açgözlü yaklaşım (greedy): gelen isteği o an en iyi görünen biçimde karşılar ve küresel etkiyi düşünmez. Bir istek geldiğinde onu en yakın boş sunucuya atamak bu türdendir.
• Özetleme: geçmişi tümüyle saklamak yerine küçük bir özet tutar. Hareketli ortalama bir toplam ve bir kuyruk, çevrimiçi ortanca iki heap, rezervuar örnekleme sabit boyutlu bir örneklem saklar.
• Uyarlanır yaklaşım (adaptive): geçmişteki isteklerden öğrenir ve davranışını zamanla değiştirir. LRU önbelleği yakın zamanda kullanılan sayfaları tutar. Öne taşı kuralı sık istenen öğeleri listenin başına getirir. Artımlı öğrenme modeli her yeni örnekle günceller.
• Deterministik yaklaşım: aynı girdiye her zaman aynı kararı verir. Bu öngörülebilirlik bir zayıflık da yaratır. Algoritmayı bilen kötü niyetli bir girdi üreticisi, yani düşman, onu kolayca tuzağa düşürebilir.
• Rastgele yaklaşım (randomized): kararlarına rastlantı katar. Düşman algoritmanın ne yapacağını önceden bilemez. Rezervuar örnekleme ve rastgele işaretleme algoritması bu türdendir.

Deterministik ile rastgele yaklaşım arasındaki fark, rekabetçi analizde sayılarla görülür. Kayak kiralamada en iyi deterministik oran 2'ye yakındır, rastgele strateji ise yaklaşık 1,58'e iner. Sayfalamada deterministik oran k'dır, rastgele işaretleme algoritmasınınki ise 2 ln k civarındadır.

13.2Rekabetçi analiz

Çevrimdışı algoritmalar için alışılmış ölçüt zaman karmaşıklığıdır. Çevrimiçi algoritmalar için bu ölçüt yetmez. Önbellek politikası her istekte O(1) iş yapabilir ama çok sayıda gereksiz sayfa hatası üretebilir. Asıl ölçülmesi gereken, kararların kalitesidir. Kaliteyi ölçmek için bir karşılaştırma noktası gerekir. Bu nokta, geleceği bilen en iyi algoritmadır.

13.2.1Rekabet oranı

Bir istek dizisi σ verilsin. Çevrimiçi algoritmanın bu dizideki toplam maliyetine ALG(σ) denir. Dizinin tamamını baştan bilen en iyi çevrimdışı algoritmanın maliyetine de OPT(σ) denir. OPT bir algoritmadan çok bir ölçüttür: her dizi için ulaşılabilecek en küçük maliyeti verir. Çevrimiçi algoritma ne yaparsa yapsın, maliyeti OPT'den küçük olamaz. Soru, ondan ne kadar büyük olabileceğidir.

Tanımın üç yanı ayrıca vurgulanmalıdır. Birincisi, koşul her dizi için sağlanmalıdır. Rekabetçi analiz bir en kötü durum analizidir; ortalama durum ya da olasılık varsayımı içermez. “Gerçek dizilerde genelde iyi çalışıyor” demek bir rekabet oranı vermez. İkincisi, oran ne kadar 1'e yakınsa gelecek bilgisinin eksikliği o kadar az zarar verir. Oranı 1 olan bir çevrimiçi algoritma geleceği bilen algoritma kadar iyidir. Üçüncüsü, toplanan α sabiti başlangıç etkilerini dışarıda bırakır. Örneğin önbellek başlangıçta boşsa ilk birkaç hata her algoritmada olur. Bu hatalar uzun dizilerde önemsizdir ve α onları emer.

Tanım maliyet problemleri içindir: amaç maliyeti en aza indirmektir ve oran her zaman c ≥ 1'dir. Bazı problemlerde ise bir kazanç en büyüklenir. Örneğin reklam yerleştirmede toplam gelir artırılmak istenir. Kazanç problemlerinde oran ters çevrilerek OPT / ALG olarak tanımlanır; böylece oran yine 1'den büyük ya da 1'e eşit olur.

13.2.2Düşman modeli

Bir algoritmanın rekabet oranının en az c olduğunu göstermek için tek bir kötü dizi bulmak yeter. Hiçbir algoritmanın c'den iyi olamayacağını göstermek ise daha zordur. Bunun için her algoritmaya karşı ayrı bir kötü dizi kurulmalıdır. Bu kurguyu düzenli hâle getiren araç düşman (adversary) modelidir. Düşman, algoritmaya karşı oynayan hayalî bir rakiptir. İstek dizisini o üretir ve aynı diziyi OPT ile de çözer. Amacı ALG(σ) / OPT(σ) oranını olabildiğince büyütmektir.

Düşmanın ne bildiği, analiz edilen algoritmanın türüne göre değişir.

• Deterministik algoritmaya karşı düşman algoritmanın kodunu bilir. Algoritma deterministik olduğu için düşman onun her adımda ne yapacağını önceden hesaplayabilir. Her adımda algoritmanın en çok zarar göreceği isteği üretir.
• Habersiz düşman (oblivious adversary) rastgele algoritmaya karşı kullanılır. Algoritmanın kodunu bilir ama yazı-tura sonuçlarını göremez. Bu yüzden diziyi baştan seçer. Algoritmanın beklenen maliyeti ölçülür.
• Uyarlanır düşman (adaptive adversary) algoritmanın rastgele kararlarını görür ve sonraki isteği buna göre seçer. Bu düşmana karşı rastgeleliğin faydası büyük ölçüde kaybolur.

Alt sınır kanıtları hep aynı kalıbı izler. “Hiçbir deterministik algoritma c'den iyi olamaz” demek için keyfî bir ALG ele alınır. Bu ALG'ye karşı ALG(σ) / OPT(σ) ≥ c yapan bir σ dizisi kurulur. ALG keyfî seçildiği için sonuç bütün deterministik algoritmalar için geçerlidir. Kalıbın gücü, düşmanın ALG'yi tanımasından gelir. Deterministik bir algoritma bir sonraki adımda ne yapacağını gizleyemez; düşman da tam o adımın açığını kullanır. Kayak kiralamada düşman, algoritma kayağı satın aldığı gün sezonu bitirir. Sayfalamada ise algoritmanın önbelleğinde bulunmayan sayfayı ister.

13.3Kayak kiralama

Kayak kiralama problemi, çevrimiçi algoritmaların en yalın örneğidir. Tek bir karar vardır: ne zaman satın alınacağı. Buna karşın problem, rekabetçi analizin bütün parçalarını içerir: geleceği bilen OPT, basit bir strateji, stratejinin üst sınırı ve hiçbir stratejinin aşamayacağı alt sınır.

13.3.1Problem

Bir kayakçı sezon boyunca her sabah kayak merkezine gider. Kayak takımı günlüğü 1 TL'ye kiralanabilir ya da B TL'ye satın alınabilir. Satın alınan takım sezonun geri kalanında bedavadır. Kayakçı sezonun kaç gün süreceğini bilmez. Her sabah yalnız “bugün de kayacak mıyım?” sorusunun cevabını öğrenir. Hava bir gün bozarsa sezon o gün biter. Toplam kayak günü sayısına d denir.

Geleceği bilen OPT için problem kolaydır. d biliniyorsa iki seçenek karşılaştırılır. Hep kiralamak d, ilk gün satın almak B tutar. Arada bir gün satın almak hiçbir zaman daha iyi değildir: önce birkaç gün kira ödeyip sonra satın almak, ilk gün satın almaktan pahalıdır. O hâlde

OPT(d) = min(d, B)

olur. d < B ise OPT hep kiralar, d ≥ B ise ilk gün satın alır. Çevrimiçi algoritma ise d'yi bilmez. Hangi günü seçerse seçsin, düşman sezonu ona en kötü gelecek biçimde bitirebilir. Şekil 13.2, B = 10 için OPT'nin maliyetini ve aşağıda incelenen başa baş stratejisinin maliyetini gösterir.

Problemin yapısı yalnız kayakla sınırlı değildir. Bir bulut sunucusu saatlik kiralanabilir ya da yıllık olarak satın alınabilir. Bir TCP bağlantısı açık tutulabilir ya da kapatılıp gerektiğinde yeniden açılabilir. Açık tutmak her saniye küçük bir maliyet doğurur, yeniden açmak ise tek seferlik büyük bir maliyettir. Bir iş parçacığı kilidin açılmasını dönerek bekleyebilir ya da uykuya geçebilir. Dönerek beklemek kira gibidir, uykuya geçip uyanmak satın alma gibidir. Hepsinde soru aynıdır: küçük ve sürekli bir maliyet ne zamana kadar ödenmeli, büyük ve tek seferlik maliyete ne zaman geçilmeli?

13.3.2Üç stratejinin maliyeti

Deterministik bir strateji tek bir sayıyla tanımlanır: satın alma günü k. Strateji k − 1 gün kiralar, k. gün hâlâ kayılıyorsa satın alır. Sezon k. günden önce biterse hiç satın almaz. Bu ailenin üç doğal üyesi vardır.

• Hep kirala (k = ∞): maliyet her zaman d'dir. d büyüdükçe OPT B'de sabit kalır, maliyet ise sınırsız artar. Oran d / B olur ve d → ∞ iken sonsuza gider. Bu strateji rekabetçi değildir.
• İlk gün satın al (k = 1): maliyet her zaman B'dir. Ama sezon tek gün sürerse OPT 1'dir. Oran B olur. B büyükse bu çok kötüdür.
• Başa baş (break-even, k = B): B − 1 gün kiralar, B. gün satın alır. Kiraya ödenen toplam, satın alma bedeline yaklaştığı anda satın alır.

Şekil 13.3 bu üç stratejinin maliyetini OPT ile birlikte, B = 10 için gün sayısının fonksiyonu olarak çizer. Tablo 13.3 aynı değerleri birkaç d için sayılarla verir.

Tablo, stratejilerin zayıf yanlarını açıkça gösterir. Hep kirala kısa sezonlarda kusursuzdur, uzun sezonlarda felakettir. İlk gün satın al uzun sezonlarda kusursuzdur, kısa sezonlarda B kat kötüdür. Başa baş stratejisi hiçbir zaman kusursuz olmaz ama hiçbir zaman da 1,9 kattan kötü olmaz. Rekabetçi analiz tam bu tür bir dengeyi arar: en kötü durumu en iyi yapan stratejiyi.

13.3.3Başa baş stratejisi: kod ve izleme

Başa baş stratejisinin Java kodu aşağıdadır. Metot, sezonun gerçek uzunluğu d'yi bir parametre olarak alır. Bu yalnız benzetim içindir: algoritma d'yi bilmez. Döngü her gün başında yalnız o gün kayılıp kayılmadığını “görür”; d'nin değerine göre bir karar vermez.

int basaBas(int B, int d) {  // d bilinmez
  int maliyet = 0;
  for (int gun = 1; gun <= d; gun++) {
    if (gun < B) {
      maliyet += 1;             // kirala
    } else {
      maliyet += B;             // satın al
      break;                    // ücret biter
    }
  }
  return maliyet;
}

Kod satır satır şöyle çalışır. maliyet sıfırdan başlar. Döngü 1. günden d. güne kadar döner; her tur, kayılan bir günü temsil eder. gun < B ise o gün kiralanır ve maliyet 1 artar. gun ilk kez B'ye eşit olduğunda else dalı çalışır: maliyete B eklenir ve break döngüden çıkar. Kayak artık kayakçınındır; kalan günler bedavadır. Sezon B. günden önce biterse döngü kendiliğinden sona erer ve hiç satın alma yapılmaz.

Metodun zamanı O(min(d, B))'dir: döngü en çok B tur döner. Bellek O(1)'dir. Ama çevrimiçi algoritmalarda asıl ilgilenilen bu süre değil, döndürülen maliyet'in OPT'ye oranıdır. Tablo 13.4, B = 4 ve d = 6 için kodun izlemesini verir. Şekil 13.4 aynı çalışmanın son durumunu gösterir.

Sonuçta ALG = 7'dir. OPT sezonun 6 gün süreceğini bildiği için ilk gün satın alır ve 4 öder. Oran 7/4 = 1,75'tir; bu değer 2 − 1/4'e eşittir. Sezon 4. günde bitseydi de ALG 7, OPT 4 olurdu. Sezon 3. günde bitseydi ALG 3 olurdu; OPT de 3 öderdi. Kodun genel bir sürümü satın alma gününü ayrı bir parametre olarak alır:

int kayakMaliyet(int B, int k, int d) {
  int maliyet = 0;
  for (int gun = 1; gun <= d; gun++) {
    if (gun == k) { maliyet += B; break; }  // satın al
    maliyet += 1;  // kirala
  }
  return maliyet;
}

Bu metot k. gün satın alan stratejinin maliyetini hesaplar. kayakMaliyet(B, B, d), her B ve d için basaBas(B, d) ile aynı değeri verir. İki metot 1 ≤ B ≤ 15 ve 1 ≤ d ≤ 40 için çalıştırılarak karşılaştırıldı; bütün değerler eşit çıktı.

13.3.4Üst sınır: başa baş stratejisinin oranı

İzlemedeki oran rastlantı değildir. Başa baş stratejisinin oranı hiçbir d için 2 − 1/B'yi aşmaz.

Kanıt, başa baş fikrinin neden işe yaradığını da açıklar. Satın alma anına kadar algoritma OPT'nin ödeyeceğinden fazla ödemez. Satın aldığı anda ise toplamda en çok “bir kez kira, bir kez satın alma” kadar öder; bunların her biri en fazla OPT kadardır. Bu yüzden toplam OPT'nin iki katını geçemez. Aynı “iki katı geçmez” fikri birçok çevrimiçi problemde karşımıza çıkar.

13.3.5Alt sınır: daha iyisi neden yok?

Başa baş stratejisi 2 − 1/B oranını sağlar. Daha akıllıca bir deterministik strateji bu oranı düşürebilir mi? Düşman modeli bunun olanaksız olduğunu gösterir.

Tablo 13.5, B = 10 için farklı satın alma günlerine karşı düşmanın elde ettiği oranı verir. Erken satın almak da geç satın almak da kötüdür; en kötü oran tam k = B'de en küçük olur.

Düşmanın d = k seçmesi gerçekten en kötü seçimdir. d < k olursa algoritma hiç satın almaz ve yalnız kira öder; oran en çok 1 olur. d > k olursa algoritmanın maliyeti değişmez ama OPT'nin maliyeti artabilir ya da aynı kalır; oran büyümez. Bu gözlem bir benzetimle de doğrulandı. B = 10 için k = 3, 5, 10, 14 stratejileri d = 1, …, 60 için çalıştırıldı. Her birinde en kötü oran d = k'da çıktı: sırasıyla 4, 2,8, 1,9 ve 2,3.

13.3.6Rastgele strateji

Alt sınır kanıtının gücü, düşmanın satın alma gününü bilmesinden gelir. Algoritma satın alma gününü rastgele seçerse düşman bu bilgiyi kaybeder. Habersiz düşman diziyi, yani d'yi baştan seçmek zorundadır. Algoritmanın beklenen maliyeti ölçülür.

Aynı fikir her B için genelleşir. Karlin, Manasse, McGeoch ve Owicki (1994) en iyi rastgele stratejiyi buldu. Bu stratejide i. gün satın alma olasılığı ((B − 1)/B)^{B − i} ile orantılıdır. Yani geç günlere daha büyük olasılık verilir. Elde edilen beklenen oran

1 / (1 − (1 − 1/B)^B)

olur. B = 2 için bu formül 1/(1 − 1/4) = 4/3 verir ve örnekteki değerle uyuşur. B büyüdükçe (1 − 1/B)^B değeri 1/e'ye yaklaşır. Oran da e/(e − 1) ≈ 1,58'e gider. Tablo 13.6 deterministik ve rastgele oranları karşılaştırır.

B = 10 için olasılıklar 1. gün 0,059'dan 10. gün 0,154'e kadar artar. Bu dağılımla her d için beklenen oran hesaplandı; en kötü değer 1,535 çıktı. Rastgelelik, düşmanın en güçlü silahını, yani algoritmanın ne zaman satın alacağını bilmesini elinden alır. Ama bunun da bir sınırı vardır. Karlin ve arkadaşları, bu oranların rastgele stratejiler için de en iyi değerler olduğunu gösterdi. Büyük B için hiçbir rastgele strateji e/(e − 1)'den belirgin biçimde iyi olamaz.

13.4Sayfalama

Sayfalama, çevrimiçi algoritmaların en çok çalışılmış problemidir. Bilgisayarların bellek düzeninde her yerde karşımıza çıkar: işlemci önbelleğinde, işletim sisteminin sanal belleğinde, veritabanı tamponunda ve web tarayıcısının önbelleğinde. Hepsinde küçük ve hızlı bir bellek, büyük ve yavaş bir belleğin bir kısmını tutar. Hangi kısmın tutulacağına, gelecek istekler bilinmeden karar verilir.

13.4.1Problem

İki düzeyli bir bellek düşünelim. Hızlı bellek, yani önbellek (cache), aynı anda k sayfa tutabilir. Yavaş bellek sınırsızdır ve bütün sayfaları içerir. İşlemci sırayla sayfa ister. İstenen sayfa önbellekteyse bu bir isabettir (hit) ve maliyeti 0'dır. Sayfa önbellekte değilse bir sayfa hatası (page fault) oluşur. Sayfa yavaş bellekten yüklenir ve maliyet 1 olur. Önbellek doluysa yeni sayfaya yer açmak için bir sayfa çıkarılmalıdır. Şekil 13.5 bu anı gösterir.

Bu modelde yalnız hatalar sayılır. Gerçek bir sistemde isabetin de küçük bir maliyeti vardır, ama yavaş bellekten yükleme bundan yüzlerce, hatta milyonlarca kat pahalıdır. Diskten bir sayfa okumak milisaniyeler, bellekten okumak nanosaniyeler sürer. Bu yüzden hata sayısı, başarımı belirleyen asıl etkendir. Ayrıca modelde sayfa yalnız hata olduğunda yüklenir; önceden yükleme yapılmaz. Bu kısıt genelliği bozmaz: önceden yükleme yapan her algoritma, yüklemeyi gerçekten gerektiği ana erteleyen bir algoritmaya çevrilebilir ve hata sayısı artmaz.

Problem tipik bir çevrimiçi problemdir. Hangi sayfanın çıkarılması gerektiği gelecekteki isteklere bağlıdır. Bir sonraki istekte hangi sayfanın isteneceği bilinseydi doğru seçim kolay olurdu. Ama algoritma yalnız geçmişi görür.

13.4.2Sayfa çıkarma politikaları

Çıkarma politikaları geçmişten farklı bilgiler kullanır. Tablo 13.7 başlıcalarını, rekabet oranlarıyla birlikte verir.

FIFO (first in, first out) önbelleği bir kuyruk gibi yönetir. Kuyruğun başındaki, yani en önce yüklenen sayfa çıkar. Bir sayfanın ne kadar sık kullanıldığına bakmaz. LRU her sayfanın son kullanım zamanını izler ve en eskisini çıkarır. Yakın geçmişte kullanılan sayfanın yakında yine kullanılacağını varsayar. FWF kaba bir politikadır. Önbellek doluyken hata olursa bütün sayfaları atar ve baştan başlar. Kaba görünse de rekabet oranı FIFO ve LRU ile aynıdır: k.

LFU ve LIFO ise rekabetçi değildir. LIFO'nun neden kötü olduğu küçük bir dizide görülür. k = 3 için 1 2 3 4 3 4 3 4 … dizisini düşünelim. İlk üç istek önbelleği doldurur. 4 gelince LIFO en son yüklenen 3'ü çıkarır. Ardından 3 istenir; bu kez en son yüklenen 4 çıkar. Dizi böyle sürdükçe her istek bir hatadır. OPT ise 4 geldiğinde bir daha hiç istenmeyecek olan 1'i çıkarır ve sonra hiç hata yapmaz. Dizi uzadıkça LIFO'nun hata sayısı artar, OPT'ninki 4'te kalır. Oran sınırsız büyür. LFU da benzer biçimde tuzağa düşer. 1 ve 2 sayfaları m kez istenip sonra 3 ve 4 dönüşümlü istenirse LFU sayaçları büyük olan 1 ve 2'yi korur. 3 ile 4 ise sayaçları m'ye yaklaşana kadar birbirini çıkarır. m büyüdükçe oran da büyür.

OPT, Belady'nin 1966'da tanımladığı politikadır; MIN ya da “en uzak ileri uzaklık” (longest forward distance) adlarıyla da anılır. Hata olduğunda önbellekteki her sayfanın bir sonraki kullanımına bakar ve en uzak gelecekte kullanılacak olanı çıkarır. Hiç kullanılmayacak sayfa varsa önce o çıkarılır. OPT geleceği bilmeyi gerektirir; bu yüzden gerçek bir sistemde uygulanamaz. Ama karşılaştırma ölçütü olarak vazgeçilmezdir. Her dizi için en az sayfa hatasını verdiği kanıtlanmıştır. Rekabet oranındaki OPT tam olarak budur.

13.4.3FIFO adım adım

Üç politikayı aynı dizide karşılaştırmak için istek dizisi 7 0 1 2 0 3 0 4 2 3 0 3 2 ve k = 3 kullanılır. Bu dizide 0 sayfası sık, öteki sayfalar seyrek istenir. Şekil 13.6 FIFO'nun çerçeve içeriklerini her istekten sonra gösterir; Ç1, Ç2 ve Ç3 önbelleğin üç çerçevesidir. Yeni yüklenen sayfa çıkan sayfanın çerçevesine yazılır. Bu yüzden çerçevedeki konumlar yükleme sırasını göstermez. Yükleme sırası Tablo 13.8'deki kuyruk sütunundadır.

İzlemenin kritik anı 6. istektir. 0 sayfası az önce, 5. istekte kullanılmıştı. FIFO bunu dikkate almaz. 0, kuyruğun başında olduğu için çıkarılır. Hemen ardından 7. istekte 0 yeniden istenir ve gereksiz bir hata oluşur. 11. istekte de aynı durum yaşanır: 0, 10. istekte çıkarılmış ve bir istek sonra geri istenmiştir. FIFO toplam 10 hata yapar.

13.4.4LRU adım adım

LRU her isabette sayfanın son kullanım zamanını günceller. Bu küçük fark, sık kullanılan sayfaların önbellekte kalmasını sağlar. Şekil 13.7 aynı dizinin LRU ile işlenişini, Tablo 13.9 ise her adımdaki kullanım sırasını gösterir.

Fark 5. istekte başlar. 0 isabet aldığında LRU onu sıranın sonuna taşır. 6. istekte çıkarılan sayfa artık 0 değil, en uzun süredir kullanılmayan 1'dir. 7. istekte 0 yine isabet alır. FIFO'nun bu iki istekte yaptığı gereksiz hata LRU'da olmaz. LRU'nun da çaresiz kaldığı anlar vardır. 10. istekte 0 en eski kullanılan sayfadır ve çıkarılır; 11. istekte geri istenir. LRU toplam 9 hata yapar.

13.4.5OPT adım adım

OPT her hatada geleceğe bakar. Önbellekteki her sayfa için bir sonraki isteğin sırası bulunur; en uzak olan çıkarılır. Şekil 13.8 OPT'nin çerçevelerini, Tablo 13.10 ise her çıkarmada hesaplanan sonraki kullanım sıralarını verir.

İlk üç istek zorunlu hatalardır. 4. istekte önbellekte 7, 0 ve 1 vardır. 7 ve 1 bir daha hiç istenmez; ikisi de çıkarılabilir. Şekil 7'yi çıkarır. 1'i çıkarmak da aynı sayıda hata verir: 1, 6. istekte zaten çıkarılacaktır. 8. istekteki karar en öğretici olanıdır. 0 sayfası dizinin en sık istenen sayfasıdır, ama bir sonraki kullanımı en uzaktadır: 11. istek. OPT onu çıkarır. 9. ve 10. isteklerdeki 2 ve 3 isabet alır. LRU aynı anda 2'yi çıkarmıştı ve iki hata yapmıştı. OPT toplam 7 hata yapar.

13.4.6Üç politikanın karşılaştırması

Tablo 13.11 üç politikanın sonuçlarını bir arada verir.

İlk k = 3 hata hiçbir politikada önlenemez. Önbellek başlangıçta boştur ve ilk üç farklı sayfa ne yapılırsa yapılsın yüklenmelidir. Bu hatalara zorunlu hata ya da soğuk hata (compulsory miss, cold miss) denir. OPT bile sıfır hata yapamaz. Rekabet oranı tanımındaki α sabiti tam bu tür başlangıç etkilerini emmek için vardır.

LRU'nun FIFO'dan iyi olmasının nedeni yerelliktir (locality of reference). Programlar belleğe rastgele erişmez. Bir döngü aynı değişkenlere tekrar tekrar erişir; bir dizi ardışık adreslerden okunur. Yakın geçmişte kullanılan sayfa yakında yine kullanılır. LRU bu düzenliliği kullanır, FIFO kullanmaz. Örnek dizide 0 sayfası sık istendiği için FIFO onu iki kez gereksiz yere çıkardı.

Gerçek sistemlerde LRU'nun kendisi de pahalıdır. Her bellek erişiminde zaman damgasını güncellemek donanım için ağır bir yüktür. Bu yüzden işletim sistemleri LRU'ya yakın, ucuz yaklaşımlar kullanır. En bilineni saat algoritmasıdır (clock), diğer adıyla ikinci şans algoritması. Her sayfanın bir “kullanıldı” biti vardır; donanım sayfaya erişildiğinde biti 1 yapar. Sayfalar dairesel bir listede durur ve bir ibre bu listede döner. Çıkarma gerektiğinde ibre biti 1 olan sayfanın bitini 0 yapıp geçer, biti 0 olan ilk sayfayı çıkarır. Yakın zamanda kullanılmış sayfalar böylece bir tur daha şans kazanır.

13.4.7LRU'nun Java kodu ve izlemesi

LRU'nun en doğrudan uygulaması bir bağlı listeyle yapılır. Liste başı en eski, sonu en yeni kullanılan sayfadır. Metot istek dizisini ve önbellek boyutunu alır, toplam sayfa hatası sayısını döndürür.

int lruHata(int[] istekler, int k) {
  var onb = new LinkedList<Integer>();
  int hata = 0;
  for (int sayfa : istekler) {
    if (onb.remove((Integer) sayfa)) {
      onb.addLast(sayfa); // en yeni yap
    } else {
      hata++;
      if (onb.size() == k)
        onb.removeFirst(); // en eskiyi at
      onb.addLast(sayfa);
    }
  }
  return hata;
}

Kodun çekirdeği onb.remove((Integer) sayfa) çağrısıdır. Bu çağrı iki iş birden yapar. Sayfa listedeyse onu listeden çıkarır ve true döndürür; değilse false döndürür. true durumunda sayfa isabet almıştır. addLast onu listenin sonuna, yani “en yeni” konuma geri ekler. false durumunda sayfa hatası vardır. Hata sayacı artar. Önbellek doluysa removeFirst listenin başındaki, en eski kullanılan sayfayı atar. Son olarak yeni sayfa sona eklenir.

Tablo 13.12, kodu 1 2 3 1 4 2 dizisi ve k = 3 ile izler.

Metot 5 döndürür (Şekil 13.9). 4. istekteki isabet önemlidir: 1, listenin başından sonuna taşınır. Bu yüzden 5. istekte 1 değil 2 atılır. FIFO aynı noktada 1'i atardı.

Kodun maliyeti remove çağrısından gelir. LinkedList.remove(Object) listeyi baştan tarar ve en çok k öğeye bakar. Bu yüzden her istek O(k) sürer; n istekli bir dizi O(n · k) zaman alır. Bellek O(k)'dir. Küçük k için bu yeterlidir. Binlerce sayfalık önbelleklerde ise istek başına O(1) gerekir.

13.4.8O(1) LRU önbelleği

İstek başına O(1) için iki yapı birlikte kullanılır. Bir hash tablosu, sayfanın önbellekte olup olmadığını ve listedeki yerini O(1)'de bulur. Çift bağlı bir liste, sayfaları kullanım sırasıyla tutar. Düğümün yeri bilindiği için onu listeden çıkarıp sona taşımak O(1)'dir. Java'nın LinkedHashMap sınıfı tam olarak bu birleşimdir.

class LruOnbellek<A, D>
    extends LinkedHashMap<A, D> {
  private final int k;

  LruOnbellek(int k) {
    super(16, 0.75f, true); // erişim sırası
    this.k = k;
  }

  @Override
  protected boolean removeEldestEntry(
      Map.Entry<A, D> enEski) {
    return size() > k;      // k aşılınca at
  }
}

Yapıcıdaki super(16, 0.75f, true) çağrısının üçüncü parametresi accessOrder'dır. true verildiğinde her get ve put, erişilen öğeyi listenin sonuna taşır. Böylece listenin başı her zaman en eski kullanılan öğe olur. İlk iki parametre başlangıç kapasitesi ve yük faktörüdür; varsayılan değerleridir. removeEldestEntry metodu her ekleme sonrasında çağrılır. true döndürürse sınıf, listenin başındaki öğeyi kendiliğinden siler. Burada boyut k'yı aştığında true döner. Bul, taşı ve sil işlemlerinin hepsi O(1)'dir; bellek O(k)'dir.

Aynı sınıf accessOrder parametresi false verilerek kurulursa FIFO önbelleği olur. Bu durumda liste ekleme sırasını tutar ve erişim sırayı değiştirmez. Tek bir parametre iki politikayı birbirinden ayırır: isabet sırayı güncelliyor mu, güncellemiyor mu?

13.4.9FIFO'nun Java kodu ve Belady dizisi

FIFO'nun Java kodu bir kuyruk ve bir kümeyle yazılır. Kuyruk yükleme sırasını tutar. Küme ise “bu sayfa önbellekte mi?” sorusunu O(1)'de cevaplar.

int fifoHata(int[] istekler, int k) {
  Queue<Integer> kuyruk = new LinkedList<>();
  Set<Integer> kume = new HashSet<>();
  int hata = 0;
  for (int p : istekler) {
    if (kume.contains(p)) continue;   // isabet
    hata++;
    if (kume.size() == k)
      kume.remove(kuyruk.poll()); // en eski
    kuyruk.offer(p); kume.add(p);
  }
  return hata;
}

Döngü her sayfa için önce kümeye bakar. Sayfa kümedeyse isabettir ve continue sonraki isteğe geçer. FIFO'da isabet hiçbir şeyi değiştirmez. Hata durumunda sayaç artar. Önbellek doluysa kuyruk.poll() kuyruğun başındaki en eski sayfayı alır ve kume.remove onu kümeden de siler. Son olarak yeni sayfa hem kuyruğun sonuna hem kümeye eklenir. Her istek O(1)'dir; bellek O(k)'dir.

Kod bu kez 1 2 3 4 1 2 5 1 2 3 4 5 dizisi ve k = 3 ile izlenir (Tablo 13.13). Bu dizi, Belady anomalisinin klasik örneğidir.

Metot 9 döndürür (Şekil 13.10). Aynı kod k = 4 ile çalıştırıldığında 10 döndürür. Önbellek büyüdü, hata sayısı arttı.

13.4.10Belady anomalisi

Önbelleği büyütmek hata sayısını azaltmalıdır. Bu beklenti o kadar doğal görünür ki 1960'lara kadar sorgulanmadı. Belady ve arkadaşları 1969'da FIFO'nun bu beklentiyi bozabildiğini gösterdi. Şekil 13.11 aynı diziyi FIFO ile önce 3, sonra 4 çerçeveyle işler.

Anomalinin nedeni 4 çerçeveli çalışmada görülür. 4 çerçeveyle ilk dört istek önbelleği doldurur ve 1 ile 2 isabet alır. 5 geldiğinde FIFO kuyruğun başındaki 1'i çıkarır. Ama 1 hemen ardından istenir. 1 yüklenirken 2 çıkar, 2 yüklenirken 3 çıkar; zincir böyle sürer. Her sayfa, tam istenmeden hemen önce çıkarılmış olur. 3 çerçeveli çalışmada ise yükleme sırası farklıdır. 5 yüklendiğinde önbellekte 1 ve 2 kalır ve ardından gelen iki istek isabet alır.

LRU ve OPT'de bu anomali hiç görülmez. Aynı dizide LRU 3 çerçeveyle 10, 4 çerçeveyle 8 hata yapar. OPT 7 ve 6 hata yapar. İki politikanın ortak özelliği, birer yığın algoritması (stack algorithm) olmalarıdır. Yığın algoritmasında her an, k çerçeveli önbellekteki sayfalar k + 1 çerçeveli önbellekteki sayfaların alt kümesidir. LRU için bunun nedeni açıktır. k çerçeveli LRU, en son kullanılan k farklı sayfayı tutar. k + 1 çerçeveli LRU ise en son kullanılan k + 1 farklı sayfayı tutar. Birincisi ikincisinin içindedir. Küçük önbellekte isabet alan her istek büyük önbellekte de isabet alır. Bu yüzden çerçeve artınca hata sayısı artamaz.

FIFO bir yığın algoritması değildir. 4 çerçeveli çalışmada 7. istekten sonra önbellek {5, 2, 3, 4}, 3 çerçeveli çalışmada {5, 1, 2}'dir. 1 küçük önbellektedir ama büyük önbellekte yoktur. 8. istek 1'dir; küçük önbellek isabet alır, büyük önbellek hata yapar.

13.4.11Deterministik alt sınır: k

Örnek dizide LRU, OPT'den yalnız 1,29 kat kötüydü. Bu oran her dizide geçerli midir? Hayır. Düşman, herhangi bir deterministik politikayı k kat kötü duruma düşüren bir dizi kurabilir.

Şekil 13.12 bu kanıtın k = 3 ve LRU için somut bir örneğini verir. 4 sayfa ile kurulan 1 2 3 4 1 2 3 4 1 2 3 4 dizisi, LRU'nun her seferinde tam az önce çıkardığı sayfayı ister.

LRU 12 istekte 12 hata yapar. OPT ise 6 hata yapar. İlk üç zorunlu hata dışarıda tutulursa oran 9'a 3'tür, yani tam k = 3. OPT'nin davranışı kanıttaki gibidir. 4. istekte önbellek {1, 2, 3}'tür ve en uzak gelecekte istenecek olan 3 çıkarılır. Ardından 1 ve 2 isabet alır. 7. istekte 3 gelince, önbellekteki 1, 2 ve 4 arasından en uzak gelecekte istenecek olan 2 çıkarılır. Her hatadan sonra iki isabet gelir.

Aynı dizide FIFO da 12 hata yapar. Bu dizide FIFO ile LRU aynı davranır, çünkü hiç isabet yoktur. Dizi uzadıkça oran k'ya yaklaşır. Örneğin 5 sayfa ve k = 4 ile 1 2 3 4 5 dizisi üç kez tekrarlanırsa LRU 15, OPT 7 hata yapar.

13.4.12Üst sınır: LRU k-rekabetçidir

Alt sınır hiçbir deterministik algoritmanın k'dan iyi olamayacağını söyler. LRU ve FIFO bu sınıra ulaşır. Kanıt, istek dizisini evrelere bölmeye dayanır.

Kanıt örnek dizide de denetlenebilir. Şekil 13.13'teki dizide 4 evre vardır. LRU'nun 9 hatası k · m = 3 · 4 = 12'yi aşmaz. OPT'nin hata sayısı en az m − 1 = 3 olmalıdır; 7 hata bu sınırı sağlar. Görüldüğü gibi teori yalnız en kötü durumu sınırlar. Gerçek dizilerde LRU, yerellik sayesinde OPT'ye bu sınırın söylediğinden çok daha yakındır.

13.4.13Rastgele sayfalama: işaretleme

Deterministik alt sınır kanıtının anahtarı, düşmanın algoritmanın önbelleğini bilmesidir. Algoritma çıkaracağı sayfayı rastgele seçerse habersiz düşman hangi sayfanın dışarıda olduğunu bilemez. Bu fikir işaretleme algoritmasına (marking algorithm) götürür.

İşaretli bir sayfa, bu evrede istenmiş bir sayfadır. Algoritma bu evrede istenmiş sayfaları korur ve yalnız işaretsizler arasından seçer. Evre kavramı, LRU kanıtındaki evrelerle aynıdır. Şekil 13.14 örnek dizinin evrelerini ve her evrede istenen sayfa kümelerini gösterir.

Fiat, Karp, Luby, McGeoch, Sleator ve Young (1991), rastgele işaretleme algoritmasının habersiz düşmana karşı 2H_k-rekabetçi olduğunu gösterdi. Burada H_k, k. harmonik sayıdır:

H_k = 1 + 1/2 + 1/3 + … + 1/k ≈ ln k

Aynı çalışma, hiçbir rastgele algoritmanın H_k'dan iyi olamayacağını da gösterir. Tablo 13.14 deterministik ve rastgele oranları karşılaştırır. Fark k büyüdükçe açılır: deterministik oran doğrusal, rastgele oran logaritmik büyür.

Küçük k için 2H_k deterministik orandan büyük olabilir. k = 2'de 2H₂ = 3, deterministik oran ise 2'dir. Ama k = 8'de işaretleme 5,44 ile deterministik orandan iyidir. Gerçek önbellekler binlerce sayfa tuttuğu için fark büyüktür. LRU da bir işaretleme algoritmasıdır. LRU'nun çıkardığı en eski kullanılan sayfa, her zaman işaretsiz bir sayfadır. LRU işaretsizler arasından rastgele değil, en eskisini seçer. Rastgelelik, düşmanın “algoritmanın önbelleğinde olmayan sayfayı iste” stratejisini bozar; düşman hangi sayfanın çıktığını bilemez.

13.4.14İşaretleme algoritmasının kod izlemesi

İşaretleme algoritmasının Java kodu iki küme kullanır: onb önbellekteki sayfaları, isr işaretli sayfaları tutar. zar bir Random nesnesidir.

int isaretleme(int[] istekler, int k) {
  Set<Integer> onb = new HashSet<>();
  Set<Integer> isr = new HashSet<>();   // işaretli
  int hata = 0;
  for (int p : istekler) {
    if (!onb.contains(p)) {
      hata++;
      if (onb.size() == k) {
        if (isr.size() == k) isr.clear(); // yeni evre
        List<Integer> aday = new ArrayList<>(onb);
        aday.removeAll(isr);          // işaretsizler
        int i = zar.nextInt(aday.size());
        onb.remove(aday.get(i));
      }
      onb.add(p);
    }
    isr.add(p);
  }
  return hata;
}

Sayfa önbellekte yoksa hata sayacı artar. Önbellek doluysa önce evre denetlenir: işaretli sayfa sayısı k'ya eşitse önbellekteki her sayfa işaretlidir. Yeni evre başlar ve isr.clear() bütün işaretleri siler. Ardından aday listesi kurulur: önbellekteki sayfalardan işaretli olanlar çıkarılır. zar.nextInt(aday.size()) bu listeden rastgele bir indis seçer ve o sayfa önbellekten çıkarılır. Yeni sayfa önbelleğe eklenir. Son satırdaki isr.add(p) isabet ya da hata fark etmeksizin istenen sayfayı işaretler.

Algoritma rastgele olduğu için bir izleme ancak belli çekilişlerle verilebilir. Tablo 13.15, örnek dizide bir çalışmayı adım adım verir. Kod, çekilişleri bu tablodaki gibi döndüren sabit bir rastgele sayı üreteciyle çalıştırıldı ve 9 döndürdü.

Tablonun bazı satırlarında seçim zorunludur. Aday listesi tek öğeliyse rastgelelik bir şey değiştirmez: 6., 10. ve 13. satırlardaki gibi. Gerçek seçimler yalnız yeni evrenin ilk hatasında yapılır. Bu çekilişlerle algoritma 9 hata yaptı (Şekil 13.15). Aynı dizide LRU 9, FIFO 10, OPT 7 hata yapmıştı. Başka çekilişlerle sonuç değişir. Kod 200 000 farklı tohumla çalıştırıldı. Hata sayısı 7 ile 12 arasında değişti; ortalaması yaklaşık 9,0 çıktı.

13.5Liste güncelleme

Sayfalamada maliyet ikiliydi: isabet ya da hata. Liste güncelleme probleminde ise maliyet, öğenin listedeki konumuna bağlıdır. Problem eski ama hâlâ kullanılan bir fikre dayanır: sık istenen öğeler listenin başına yakın tutulursa aramalar ucuzlar. Hangi öğelerin sık isteneceği önceden bilinmediği için problem çevrimiçidir.

13.5.1Problem ve üç kural

n öğeli bir bağlı liste verilsin. Bir öğeye erişmek için liste baştan taranır. i. konumdaki öğeye erişmenin maliyeti i'dir. Erişilen öğe, erişimden sonra ücretsiz olarak listenin önüne doğru taşınabilir. İki komşu öğenin başka bir biçimde yer değiştirmesi ise 1 birim tutar; bu tür takaslara ücretli takas denir.

Üç doğal kural vardır.

• Öne taşı (move-to-front, MTF): erişilen öğe listenin başına alınır.
• Transpoz (transpose), diğer adıyla yer değiştir: erişilen öğe bir önündeki öğeyle yer değiştirir.
• Sıklık sayacı (frequency count): her öğenin erişim sayısı tutulur ve liste bu sayılara göre azalan sırada tutulur.

Bu kurallara uyan listelere kendini düzenleyen listeler (self-organizing lists) denir. Kullanım alanları geniştir. Zincirleme hash tablosunda her kovanın zinciri kısa bir bağlı listedir; öne taşı kuralı sık aranan anahtarları zincirin başına getirir. Veri sıkıştırmada öne taşı dönüşümü kullanılır: her simge, o anki listedeki konumuyla kodlanır ve sonra öne taşınır. bzip2 sıkıştırıcısı bu dönüşümü kullanır. Ardışık tekrarlar küçük sayılara, çoğunlukla 0'a dönüşür ve sonraki aşamada iyi sıkışır. Örneğin “banana” sözcüğü a, b, n alfabesiyle 1, 1, 2, 1, 1, 1 olarak kodlanır.

Öne taşı kuralının Java kodu bağlı listeyle kısa yazılır:

int mtfMaliyet(LinkedList<Character> liste, char[] istekler) {
  int toplam = 0;
  for (char x : istekler) {
    int konum = liste.indexOf(x) + 1;  // 1 tabanlı
    toplam += konum;
    liste.remove((Character) x);
    liste.addFirst(x);  // öne taşı
  }
  return toplam;
}

indexOf öğenin 0 tabanlı konumunu bulur; 1 eklenerek maliyet elde edilir. remove((Character) x) öğeyi listeden çıkarır, addFirst başa ekler. (Character) dönüşümü burada da remove(int index) yerine remove(Object) sürümünün çağrılmasını sağlar. indexOf ve remove listeyi taradığı için her istek O(n) sürer. Bu süre, problemin kendi maliyet modeliyle uyumludur: erişim zaten konum kadar tutar.

13.5.2Öne taşı adım adım

Başlangıç listesi A B C D E, istekler E D E A D E olsun. Tablo 13.16 öne taşı kuralının her adımını verir.

Aynı dizide öteki kurallar daha çok öder (Tablo 13.17). Hiç taşımayan liste her E için 5, her D için 4 öder. Transpoz ise bu dizide çok kötüdür. E ile D listenin sonunda birbirinin yerini alıp durur: E öne geçince D sona düşer, D öne geçince E sona düşer. İkisi de hep 5. konumdan istenir.

Geleceği bilen bir algoritma daha da az öder. Bütün listeler ve ücretli takaslar denenerek bu küçük örnekte en iyi maliyet hesaplandı: 17. Bu maliyete şöyle ulaşılır: başta 7 ücretli takasla liste E D A B C yapılır. Sonra erişimler 1 + 2 + 1 + 3 + 2 + 1 = 10 tutar.

13.5.3Öne taşı kuralı 2-rekabetçidir

Sleator ve Tarjan 1985'te öne taşı kuralının rekabet oranının 2 olduğunu gösterdi. Aynı makale sayfalamadaki k sonucunu da içerir. İkisi birlikte rekabetçi analizin başlangıç noktası sayılır.

Kanıt amortize analize (amortized analysis) dayanır. Bir işlemin gerçek maliyeti dalgalı olabilir. Pahalı işlemler, ucuz işlemlerin biriktirdiği “krediyle” ödenir. Kredi bir potansiyel fonksiyonu Φ ile ölçülür. Bir işlemin amortize maliyeti, gerçek maliyeti ile potansiyeldeki değişimin toplamıdır: gerçek + ΔΦ. Potansiyel hiç negatif olmaz ve başta 0'sa, amortize maliyetlerin toplamı gerçek maliyetlerin toplamından küçük olamaz.

Kanıttaki eşitsizlik örnek dizide adım adım izlenebilir. Tablo 13.18, A olarak hiç taşımayan A B C D E listesini alır. Her adımda amortize maliyet 2i − 1'i aşmaz. Toplamda 21 ≤ 2 · 24 − 6 = 42 olur. Gerçek OPT ile de sınır sağlanır: 21 ≤ 2 · 17 − 6 = 28.

4. satır kanıtın gücünü gösterir. A'ya erişim MTF'ye 3 birime mal olur, sabit listeye ise yalnız 1 birime. Gerçek maliyetle bakılırsa MTF bu adımda 3 kat kötüdür. Ama A'nın başa taşınması iki ters çifti yok eder ve potansiyel 2 azalır. Amortize maliyet 1'e iner. Önceki adımlarda biriken kredi, bu pahalı adımı öder.

13.5.4Transpoz ve sıklık sayacı neden rekabetçi değil?

Transpoz kuralı öğeyi yalnız bir adım taşıdığı için temkinli görünür. Ama düşman bu temkini kullanır. Listenin son iki öğesi sırayla istenir: x_n, x_n−1, x_n, x_n−1, … Her erişim iki öğenin yerini değiştirir, ama ikisi de hep n. ve (n − 1). konumda kalır. İstenen öğe her seferinde n. konumdadır. İstek başına maliyet n'dir. MTF ise ilk iki erişimden sonra iki öğeyi listenin başında tutar ve istek başına 2 öder. n = 5 ve 20 istekle bu dizi çalıştırıldı: transpoz 100, MTF 46, taşımayan liste 90 ödedi. n büyüdükçe oran n/2'ye gider; sınırsızdır.

Sıklık sayacı da tuzağa düşer. Önce x₁ öğesi n kez, x₂ öğesi n − 1 kez istenir ve bu böyle sürer. Sonra aynı öğeler ters sırada, daha çok sayıda istenir. Sayaçlar eski sırayı uzun süre korur. Yeni sık öğeler sayaçlar yetişene kadar listenin sonunda kalır. A B C D listesinde A dört, B üç, C iki, D bir kez istenip ardından D beş, C altı, B yedi, A dokuz kez istendi. Sıklık sayacı 81, MTF 49 ödedi. Uzun listelerde maliyet Θ(n) kat kötüleşebilir.

13.6Veri akışları

Önceki problemlerde çevrimiçi algoritmanın sorunu yanlış karar vermekti. Veri akışlarında sorun başkadır: girdi o kadar büyüktür ki saklanamaz. Algoritma her öğeye bir kez bakar ve küçük bir özet tutar. Her an bir soru sorulabilir; cevap yalnız özetten verilmelidir.

13.6.1Veri akışı modeli

Tablo 13.19, bu kesimde işlenen problemleri, her biri için saklanan özeti ve maliyetleri verir.

Çevrimiçi ortanca tablonun istisnasıdır: belleği akışla birlikte büyür. Kesin ortanca için bu kaçınılmazdır. Akıştaki her öğe, ileride ortanca olma adayıdır. Çok büyük akışlarda bu yüzden yaklaşık ortanca veren özetler kullanılır.

13.6.2Hareketli ortalama

Hareketli ortalama (moving average), akıştaki son k öğenin ortalamasıdır. Gürültülü algılayıcı verisini yumuşatmak için kullanılır. Borsada 50 günlük ortalama da bir hareketli ortalamadır. Saf yöntem her yeni öğede son k öğeyi baştan toplar: O(k). Daha iyi yöntem kayan penceredir (sliding window). Toplam bir değişkende tutulur. Yeni öğe girerken toplama eklenir, en eski öğe pencereden çıkarken toplamdan çıkarılır:

toplam ← toplam − x_t−k + x_t,   ortalama = toplam / min(t, k)

class HareketliOrtalama {
  private final int k;
  private final Queue<Integer> pencere
      = new LinkedList<>();
  private int toplam = 0;

  HareketliOrtalama(int k) { this.k = k; }

  double sonraki(int deger) {
    if (pencere.size() == k)
      toplam -= pencere.poll();
    pencere.offer(deger);
    toplam += deger;
    return toplam / (double) pencere.size();
  }
}

Pencere bir kuyruktur. sonraki metodu önce pencerenin dolu olup olmadığına bakar. Doluysa poll en eski öğeyi kuyruktan alır ve toplamdan çıkarır. Sonra yeni öğe kuyruğa eklenir ve toplama katılır. Ortalama, toplamın pencere boyuna bölümüdür. Pencere henüz dolmamışsa bölen k değil o anki öğe sayısıdır. (double) dönüşümü tam sayı bölmesini önler. Her çağrı O(1)'dir; bellek O(k)'dir. Tablo 13.20, k = 3 ile 4, 8, 6, 2, 10 akışını izler.

13.6.3Çevrimiçi ortanca

Her yeni öğeden sonra o ana kadarki öğelerin ortancası (median) isteniyor. Her seferinde sıralamak O(n log n), sıralı bir diziye eklemek O(n) sürer. İki heap ile ekleme O(log n)'e, ortanca okuma O(1)'e iner. Bu yönteme çevrimiçi ortanca (running median) denir.

Fikir şudur. Öğeler iki yarıya bölünür. Küçük yarı bir max-heap'te tutulur; buna sol denir. Büyük yarı bir min-heap'te tutulur; buna sag denir. Ortanca, iki yarının sınırındadır. Bu sınırdaki öğeler de tam heap tepeleridir. İki değişmez korunur:

• sol'daki her öğe, sag'daki her öğeden küçük ya da ona eşittir.
• Boyutlar ya eşittir ya da sol bir fazladır: |sol| = |sag| ya da |sol| = |sag| + 1.

Öğe sayısı tekse ortanca sol'un tepesidir. Çiftse iki tepenin ortalamasıdır. Java'da PriorityQueue varsayılan olarak min-heap'tir; max-heap ters karşılaştırıcıyla kurulur:

PriorityQueue<Integer> sol = new PriorityQueue<>((a, b) -> b - a); // max-heap
PriorityQueue<Integer> sag = new PriorityQueue<>();               // min-heap

void ekle(int x) {
  if (sol.isEmpty() || x <= sol.peek())
    sol.offer(x);          // küçük yarı
  else
    sag.offer(x);          // büyük yarı
  if (sol.size() > sag.size() + 1)
    sag.offer(sol.poll());
  else if (sag.size() > sol.size())
    sol.offer(sag.poll());
}
double ortanca() {
  if (sol.size() == sag.size())
    return (sol.peek() + sag.peek()) / 2.0;
  return sol.peek();
}

ekle iki aşamada çalışır. Önce öğe doğru yarıya konur: sol boşsa ya da öğe sol'un tepesinden büyük değilse küçük yarıya, değilse büyük yarıya gider. Bu adım birinci değişmezi korur. Sonra denge düzeltilir. sol iki fazla olduysa tepesi sag'a taşınır. sag büyük olduysa tepesi sol'a taşınır. Taşınan öğe hep bir yarının sınırdaki öğesidir. Bu yüzden taşıma birinci değişmezi bozmaz. Her ekleme en çok üç heap işlemi yapar: O(log n). ortanca yalnız tepelere bakar: O(1). Tablo 13.21, 5, 15, 1, 3, 8, 7 akışını izler.

Dördüncü ve beşinci adımlar dengenin neden gerektiğini gösterir. 3 eklendikten sonra sol 3, sag 1 öğe tutar. Ortanca artık sol'un tepesi değildir. 5'in sag'a taşınmasıyla iki yarı yine eşitlenir. Beşinci adımda bu kez sag büyük kalır ve 5 geri döner. Aynı öğe iki kez taşınmıştır; bu olağandır. Kod çalıştırıldığında ortancalar sırasıyla 5,0, 10,0, 5,0, 4,0, 5,0 ve 6,0 çıktı.

13.6.4Rezervuar örnekleme

Uzunluğu bilinmeyen bir akıştan k öğelik rastgele bir örneklem tutulmak isteniyor. Her öğe örneklemde eşit olasılıkla bulunmalıdır. Akışın uzunluğu n bilinseydi iş kolay olurdu: 1, …, n arasından k indis seçilirdi. Ama n bilinmez ve öğeler saklanamaz. Rezervuar örnekleme (reservoir sampling) bu problemi O(k) bellekle çözer.

Algoritmaya göre i. öğe k / (i + 1) olasılıkla rezervuara girer. Girerse rastgele bir yerdeki öğeyi çıkarır. Geç gelen öğelerin girme olasılığı küçüktür. Ama erken gelen öğelerin de çıkarılma riski uzun süre devam eder. İki etki tam olarak dengelenir.

List<Integer> rezervuar(int[] akis, int k) {
  List<Integer> r = new ArrayList<>();
  for (int i = 0; i < k; i++) r.add(akis[i]);
  for (int i = k; i < akis.length; i++) {
    int j = rastgele.nextInt(i + 1); // 0..i
    if (j < k)
      r.set(j, akis[i]);
  }
  return r;
}

Kod bir listeyle çalışır. İlk döngü ilk k öğeyi rezervuara koyar. İkinci döngü kalan her öğe için rastgele.nextInt(i + 1) çağırır. Bu çağrı 0 … i aralığında, uçlar dahil düzgün bir tam sayı döndürür. j < k ise r.set o yerdeki öğenin üzerine yazar. Öğe başına O(1) iş, toplam O(k) bellek kullanılır. Gerçek bir akışta dizi yerine bir yineleyiciyle çalışılır; algoritma değişmez.

Tablo 13.22 kodu 10, 20, 30, 40, 50, 60 akışı ve k = 3 ile izler. Rastgele sayılar bu izleme için sabitlenmiştir: 1, 4 ve 0.

Başka j değerleriyle başka bir örneklem çıkar. Ama teoreme göre her öğe 3/6 = 1/2 olasılıkla örneklemdedir. Bu iddia bir benzetimle de denetlendi. 1, …, 10 akışı ve k = 3 ile kod 300 000 kez çalıştırıldı. Her öğenin örneklemde bulunma sıklığı 0,299 ile 0,301 arasında çıktı; beklenen değer 3/10 = 0,3'tür.

13.6.5Akışta örüntü arama: kayan hash

Bir ağ izleme programı, geçen paketlerde belli bir imzayı arıyor olsun. Karakterler akış hâlinde gelir. Örüntünün uzunluğu m ise yalnız son m karaktere bakmak yeterlidir. Her yeni karakterde bu pencereyi örüntüyle karşılaştırmak O(m) sürer. Kayan hash (rolling hash) karşılaştırmayı çoğu zaman O(1)'e indirir.

Pencerenin hash değeri, karakterleri B tabanında bir sayının basamakları gibi kullanır. Yeni karakter girdiğinde değer baştan hesaplanmaz. Çıkan karakterin katkısı çıkarılır, kalan değer bir basamak kaydırılır ve giren karakter eklenir:

h_yeni = (h_eski − c_çıkan · B^m−1) · B + c_giren

void ara(String akis, String oruntu) {
  int m = oruntu.length(), B = 101, h = 0, hp = 0;
  int gucu = 1;                         // B^(m-1)
  for (int i = 0; i < m - 1; i++) gucu *= B;
  for (int i = 0; i < m; i++)
    hp = hp * B + oruntu.charAt(i);
  for (int t = 0; t < akis.length(); t++) {
    char c = akis.charAt(t);
    if (t >= m) h -= akis.charAt(t - m) * gucu;
    h = h * B + c;          // giren eklenir
    if (t >= m - 1 && h == hp
        && akis.startsWith(oruntu, t - m + 1))
      System.out.println("eşleşme: " + (t - m + 1));
  }
}

Kod önce gucu değişkenine B^m−1 değerini, hp'ye de örüntünün hash değerini hesaplar. Ana döngü her karakter için çalışır. t >= m ise pencereden bir karakter çıkar ve katkısı akis.charAt(t - m) * gucu olarak çıkarılır. Sonra h bir basamak kaydırılır ve giren karakter eklenir. Pencere dolduktan sonra h == hp ise karakterler de startsWith ile karşılaştırılır. İki farklı dizgi aynı hash değerini verebilir; buna çakışma denir. Bu yüzden hash eşitliği tek başına yetmez. Hash'ler farklıysa karakterlere hiç bakılmaz. Çakışma seyrekse öğe başına iş O(1)'dir; bellek pencere için O(m)'dir.

Tablo 13.23, “AB” örüntüsünü “CABDAB” akışında arar. B = 101, m = 2 ve gucu = 101'dir. Karakter kodları A = 65, B = 66, C = 67, D = 68'dir. Örüntünün hash değeri 65 · 101 + 66 = 6631'dir.

Kod çalıştırıldığında “eşleşme: 1” ve “eşleşme: 4” yazdırdı. Örüntü uzadıkça int taşar. Bu durum doğruluğu bozmaz. Java'da int işlemleri 2³² modunda yapılır ve çıkarma, çarpma, toplama bu modda tutarlıdır. h ve hp aynı modda hesaplandığı için eşit pencereler eşit hash verir. Taşma yalnız çakışmaları artırabilir; karakter karşılaştırması bunları ayıklar. Uygulamada çoğunlukla büyük bir asal sayı modunda çalışılır.

13.7Artımlı öğrenme

Makine öğrenmesinde model çoğunlukla bütün veriyle bir kez eğitilir. Veri sürekli geliyorsa bu yaklaşım pahalıdır. Her yeni veri parçasında modeli baştan eğitmek, o ana kadar gelen bütün veriyi yeniden işlemek demektir. Çevrimiçi bakış burada da işe yarar: model yalnız yeni veriyle güncellenir.

13.7.1Modeli yeni veriyle güncellemek

Şekil 13.24 süreci gösterir. Başlangıçta model özgün veri kümesiyle eğitilir ve MODEL 1 elde edilir. Yeni veri 1 geldiğinde model yalnız bu veriyle güncellenir ve MODEL 2 olur. MODEL 2 iki veri kümesinin bilgisini taşır, ama özgün veri yeniden işlenmemiştir. Yeni veri 2 ile aynı adım tekrarlanır. Model her an günceldir ve bir güncellemenin maliyeti yalnız yeni verinin boyutu kadardır.

Akış algoritmalarıyla benzerlik açıktır. Model, geçmiş verinin bir özetidir; tıpkı hareketli ortalamadaki toplam ya da çevrimiçi ortancadaki iki heap gibi. Fark, özetin daha karmaşık olmasıdır: bir sınıflandırıcının ağırlıkları, bir karar ağacının dalları ya da bir sinir ağının parametreleri.

13.7.2Çalışan ortalama ve çevrimiçi gradyan inişi

Artımlı güncellemenin en basit örneği çalışan ortalamadır. Akıştaki bütün öğelerin ortalaması, geçmişi saklamadan güncellenebilir:

μ_n = μ_n−1 + (x_n − μ_n−1) / n

Formül, yeni öğenin eski ortalamadan farkının 1/n'i kadar düzeltme yapar. Akış 4, 8, 6 için μ₁ = 4, μ₂ = 4 + (8 − 4)/2 = 6, μ₃ = 6 + (6 − 6)/3 = 6 olur. Bu değer (4 + 8 + 6)/3 = 6 ile aynıdır. Saklanan yalnız n ve μ'dür; bellek O(1)'dir. Formül toplamı ayrıca tutmadığı için uzun akışlarda büyük sayılarla da sorun çıkarmaz.

Aynı fikir model eğitimine çevrimiçi gradyan inişi (online gradient descent) olarak taşınır. Model bir ağırlık vektörü w ile tanımlanır. Her örnek (x_t, y_t) geldiğinde ağırlık, kaybın gradyanının tersi yönünde küçük bir adım atar:

w ← w − η · ∇ℓ(w; x_t, y_t)

Burada ℓ kayıp fonksiyonu, η ise öğrenme oranıdır. Her örnek bir kez kullanılır ve atılır.

13.7.3Zorluklar

Artımlı öğrenme ucuz ve güncel bir model verir, ama kendine özgü sorunları vardır.

• Felaket boyutunda unutma (catastrophic forgetting): model yeni veriye uyum sağlarken eski bilgiyi kaybeder. Bir sinir ağı yeni bir görevi öğrenirken eski görevdeki başarısı birden düşebilir.
• Kavram kayması (concept drift): verinin dağılımı zamanla değişir. Geçen yılın alışveriş alışkanlıkları bu yılı iyi temsil etmeyebilir. Eski veri bu durumda yanıltıcı olur.
• Sıra etkisi: aynı veri farklı sırayla gelirse model farklı biçimlenir. Çevrimdışı eğitimde veri karıştırılabilir; akışta sıra veriyle birlikte gelir.
• Gürültü: tek bir aykırı örnek modeli bozabilir. Küçük bir öğrenme oranı ve kayan pencere bu etkiyi azaltır.

Unutma ile kavram kayması birbirine ters yönde çeker. Kavram kayması varsa eski verinin bir ölçüde unutulması istenir. Kayma yoksa unutma bir kayıptır. Hareketli ortalamadaki pencere boyu ya da öğrenme oranı bu dengeyi ayarlayan düğmelerdir.

13.8Problemler ve sonuçlar

Tablo 13.24 bölümdeki problemleri ve sonuçlarını bir arada verir. İlk beş satırdaki sayılar rekabet oranıdır. Alttaki satırlar ise öğe başına zamanı verir.

Tablodaki üç rekabetçi problemin kanıtları aynı iskeleti izler. Üst sınır için algoritmanın maliyeti OPT'nin bir katıyla sınırlanır. Kayak kiralamada bu bir durum ayrımıyla, sayfalamada evrelerle, liste güncellemede potansiyel fonksiyonuyla yapılır. Alt sınır için ise düşman, deterministik algoritmanın bir sonraki kararını bilerek onun en çok zarar göreceği isteği üretir. Rastgelelik üç problemde de oranı düşürür, çünkü düşmanın bu bilgisini elinden alır.

13.9Sık yapılan hatalar

• “Çevrimiçi = internet” sanmak. Çevrimiçi algoritma, girdinin zamanla açığa çıktığı modeldir. Ağ bağlantısıyla ilgisi yoktur.
• Oranı ortalama durumla karıştırmak. Rekabet oranı en kötü girdiye göredir. “Genelde iyi çalışır” bir rekabet oranı değildir.
• FIFO ile LRU'yu karıştırmak. FIFO'da isabet sırayı değiştirmez; LRU'da isabet sayfayı en yeni yapar. İki politikanın tek farkı budur.
• Zorunlu hataları unutmak. İlk k farklı sayfa her politikada hata verir. OPT bile sıfır hata yapamaz.
• OPT'yi “en az kullanılacak sayfa” sanmak. OPT, bir sonraki kullanımı en uzak olan sayfayı çıkarır; kullanım sayısına bakmaz.
• Büyük önbelleğin hep daha iyi olduğunu sanmak. FIFO'da çerçeve artınca hata artabilir: Belady anomalisi. LRU ve OPT'de bu olmaz.
• Rezervuarda yanlış aralık. j, 0 … i aralığından, i dahil seçilmelidir. nextInt(i) yazmak olasılıkları bozar.
• Ortancada dengeyi unutmak. Öğeyi doğru heap'e koymak yetmez. Boyut farkı 1'i aşınca tepe öbür heap'e taşınmalıdır.
• Hash eşitliğini eşleşme saymak. Kayan hash'te eşit değerler çakışmadan da gelebilir. Karakterler ayrıca karşılaştırılmalıdır.

13.10Özet

• Model: girdi bir istek dizisi olarak parça parça gelir. Karar istek geldiği anda verilir ve geri alınamaz. Çevrimdışı algoritma ise girdinin tamamını baştan görür.
• Rekabet oranı: her σ için ALG(σ) ≤ c · OPT(σ) + α sağlanıyorsa algoritma c-rekabetçidir. Analiz en kötü durumu ölçer. Alt sınırlar düşman modeliyle kurulur.
• Kayak kiralama: OPT = min(d, B). Başa baş stratejisi B − 1 gün kiralar ve B. gün satın alır; oranı 2 − 1/B'dir. Hiçbir deterministik strateji daha iyi değildir; rastgele strateji e/(e − 1) ≈ 1,58'e iner.
• Sayfalama: FIFO en önce yükleneni, LRU en uzun süredir kullanılmayanı, OPT bir sonraki kullanımı en uzak olanı çıkarır. Örnek dizide 10, 9 ve 7 hata. LRU ve FIFO k-rekabetçidir ve deterministikte daha iyisi yoktur. Rastgele işaretleme 2H_k'ya iner.
• Belady anomalisi: FIFO'da çerçeve artınca hata artabilir (9 → 10). LRU ve OPT yığın algoritmasıdır; anomali göstermez.
• Uygulama: LRU bağlı listeyle istek başına O(k), LinkedHashMap ile O(1)'dir. FIFO bir kuyruk ve bir kümeyle O(1)'dir.
• Liste güncelleme: maliyet konumdur. Öne taşı kuralı MTF ≤ 2 · OPT − m sağlar; kanıt ters çift sayısını potansiyel alır. Transpoz ve sıklık sayacı rekabetçi değildir.
• Veri akışları: tek geçiş ve az bellek. Hareketli ortalama kayan pencereyle O(1), çevrimiçi ortanca iki heap ile O(log n), rezervuar örnekleme O(1) ve O(k) bellekle çalışır. Rezervuarda her öğe k/n olasılıkla bulunur. Kayan hash, pencereyi O(1)'de günceller.
• Artımlı öğrenme: model yeni veriyle güncellenir. Çalışan ortalama ve çevrimiçi gradyan inişi temel örneklerdir. Unutma ve kavram kayması başlıca zorluklardır.

13.11Kavram listesi

• çevrimiçi algoritma online algorithm
• çevrimdışı algoritma offline algorithm
• rekabetçi analiz competitive analysis
• rekabet oranı competitive ratio
• düşman adversary
• kayak kiralama problemi ski rental problem
• rastgele algoritma randomized algorithm
• sayfalama paging
• önbellek cache
• sayfa hatası page fault
• çıkarma politikası eviction policy
• Belady anomalisi Belady's anomaly
• yığın algoritması stack algorithm
• işaretleme algoritması marking algorithm
• liste güncelleme problemi list update problem
• öne taşı move-to-front (MTF)
• transpoz transpose
• amortize analiz amortized analysis
• ters çift inversion
• veri akışı data stream
• çevrimiçi ortanca running median
• rezervuar örnekleme reservoir sampling
• kayan hash rolling hash
• artımlı öğrenme incremental learning

13.12Kendini Dene

1. Kayak kiralamada B = 8'dir. 6. gün satın alan stratejinin en kötü durum oranı nedir? Bu oran başa baş stratejisininkinden ne kadar farklıdır?

   Cevap

   Düşman sezonu 6. gün bitirir. ALG = 5 + 8 = 13, OPT = min(6, 8) = 6; oran 13/6 ≈ 2,17. Başa baş stratejisinin oranı 2 − 1/8 = 15/8 = 1,875'tir. Erken satın alan strateji daha kötüdür.

2. 1 2 1 3 1 4 1 2 dizisi k = 2 çerçeveyle işleniyor. FIFO ve LRU kaçar sayfa hatası yapar?

   Cevap

   FIFO 6 hata yapar: 3 gelince en önce yüklenen 1 çıkar ve 1 hemen geri istenir. 1 gelince 2, 4 gelince 3, son 2 gelince 1 çıkar. LRU 5 hata yapar. 1 her isabette en yeni olduğu için hiç çıkmaz; 3, 4 ve son 2 gelince sırasıyla 2, 3 ve 4 çıkar. Bu dizide OPT de 5 hata yapar.

3. 1 2 3 1 4 2 dizisi k = 3 ile OPT politikasıyla işleniyor. Kaç hata olur? 4 geldiğinde hangi sayfalar çıkarılabilir?

   Cevap

   4 hata olur: üç zorunlu hata ve 4'ün hatası. 4 geldiğinde önbellek {1, 2, 3}'tür. 1 ve 3 bir daha istenmez, 2 son istekte istenir. 1 ya da 3 çıkarılabilir; ikisi de aynı sonucu verir. Son istekteki 2 isabet alır. Aynı dizide LRU 5 hata yapmıştı.

4. A B C listesinde öne taşı kuralıyla C C B A isteklerinin toplam maliyeti nedir? Hiç taşımayan liste ne öder?

   Cevap

   C 3. konumda: 3, liste C A B. C 1. konumda: 1. B 3. konumda: 3, liste B C A. A 3. konumda: 3, liste A B C. Toplam 3 + 1 + 3 + 3 = 10. Taşımayan liste 3 + 3 + 2 + 1 = 9 öder. Bu kısa dizide öne taşı kuralı biraz daha pahalıdır; 2-rekabetçi olmak her dizide en iyi olmak demek değildir.

5. new HareketliOrtalama(2) nesnesine sırasıyla 3, 5, 9, 1 veriliyor. sonraki hangi değerleri döndürür?

   Cevap

   3,0; (3 + 5)/2 = 4,0; 3 çıkar ve (5 + 9)/2 = 7,0; 5 çıkar ve (9 + 1)/2 = 5,0.

6. Çevrimiçi ortanca yapısına 10, 2, 7, 4 sırasıyla ekleniyor. Her eklemeden sonra ortanca nedir? 7 eklendiğinde heap'ler arasında taşıma olur mu?

   Cevap

   Ortancalar 10, 6, 7, 5,5'tir. 2 eklenince sol'a girer, sol iki öğe tutar ve tepe 10 sag'a taşınır: ortanca (2 + 10)/2 = 6. 7 eklenince 7 > 2 olduğu için sag'a girer. sag iki, sol bir öğe tutar. sag'ın tepesi 7 sol'a taşınır; ortanca 7'dir. 4 sol'a girer; sol üç öğe tutar ve tepesi 7 sag'a taşınır. Boyutlar 2 ve 2 olur: (4 + 7)/2 = 5,5.

7. k = 1 ile rezervuar örneklemede 0 tabanlı 4. öğe hangi olasılıkla rezervuara girer? Akış 8 öğeyle biterse bu öğe sonda hangi olasılıkla seçilmiş olur?

   Cevap

   Girme olasılığı 1/5'tir. Sonraki üç adımda kalma olasılıkları 5/6, 6/7 ve 7/8'dir. Çarpım 1/5 · 5/6 · 6/7 · 7/8 = 1/8 = k/n olur.

8. k = 6 sayfalık bir önbellekte deterministik LRU ile rastgele işaretleme algoritmasının rekabet oranları nedir? Hangisi daha iyi bir garanti verir?

   Cevap

   LRU'nun oranı 6'dır. H₆ = 1 + 1/2 + … + 1/6 = 49/20 = 2,45; işaretleme algoritmasının oranı 2H₆ = 4,9'dur. İşaretleme bu durumda deterministik sınırın altındadır. Rastgele hiçbir algoritma 2,45'ten iyi olamaz.

9. ara("ABA", "BA") çağrısında B = 101 ile hp nedir? t = 2 anında h hangi değeri alır ve ne yazdırılır?

   Cevap

   hp = 66 · 101 + 65 = 6731. t = 1'de pencere “AB” ve h = 6631'dir. t = 2'de A çıkar: (6631 − 65 · 101) · 101 + 65 = 66 · 101 + 65 = 6731. Hash eşittir ve karakterler de tutar; “eşleşme: 1” yazdırılır.

13.13İleri okuma

• A. Borodin ve R. El-Yaniv, Online Computation and Competitive Analysis: alanın temel kitabıdır. Sayfalama, liste güncelleme, düşman modelleri ve rastgele algoritmaları ayrıntılı kanıtlarla işler.
• T. H. Cormen ve arkadaşları, Introduction to Algorithms, 4. baskı, 27. bölüm: çevrimiçi algoritmalara giriş yapar; asansör bekleme (kayak kiralamanın bir türü), liste güncelleme ve önbellek problemlerini ele alır.
• S. Albers, “Online algorithms: a survey” (2003): rekabetçi analizin başlıca sonuçlarını kısa ve okunaklı bir özetle verir.
• J. S. Vitter, “Random Sampling with a Reservoir” (1985): Algoritma R'yi ve onu hızlandıran atlamalı sürümleri tanıtır.

13.14Kaynaklar

1. A. Borodin ve R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998.
2. D. D. Sleator ve R. E. Tarjan, “Amortized Efficiency of List Update and Paging Rules”, Communications of the ACM 28(2), 1985.
3. L. A. Belady, “A Study of Replacement Algorithms for a Virtual-Storage Computer”, IBM Systems Journal 5(2), 1966.
4. L. A. Belady, R. A. Nelson ve G. S. Shedler, “An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine”, Communications of the ACM 12(6), 1969.
5. A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator ve N. E. Young, “Competitive Paging Algorithms”, Journal of Algorithms 12(4), 1991.
6. A. R. Karlin, M. S. Manasse, L. A. McGeoch ve S. Owicki, “Competitive Randomized Algorithms for Nonuniform Problems”, Algorithmica 11(6), 1994.
7. J. S. Vitter, “Random Sampling with a Reservoir”, ACM Transactions on Mathematical Software 11(1), 1985.
8. S. Albers, “Online Algorithms: A Survey”, Mathematical Programming 97(1–2), 2003.
9. T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (27. bölüm: Online Algorithms).