Kayan Pencere

Önceki ders iki işaretçiyi dizinin iki ucuna koyuyor ve ortada buluşturuyordu; ön koşulu sıraydı. Bu dersin kalıbı işaretçileri aynı yönde tutar. Aralarındaki bölge bir penceredir: sağ işaretçi ilerledikçe pencere büyür, bir koşul sağlandığında sol işaretçi ilerleyerek pencereyi küçültür.

Kazanç, pencere her kaydığında toplamın sıfırdan hesaplanmamasından gelir; giren değer eklenir, çıkan değer düşülür. Ön koşulu ise sıraya hiç bakmaz: hiçbir değer negatif olmamalıdır. Bu ders o ön koşulun bozulduğu girdileri kâhinle sayar ve ön koşulun aslında pencerenin değil küçültme kuralının ön koşulu olduğunu gösterir.

Problem, Kâhin ve Kalıp

Problem şudur: toplamı hedeften küçük olmayan en kısa bitişik alt dizinin uzunluğu nedir. Kâhin her başlangıç konumundan başlayıp sağa doğru genişler ve hedefi ilk aştığı yerde durur; bütün başlangıçları dener. Kalıp tek geçişte ilerler: sağ uç değeri toplama katar, toplam hedefi aştığı sürece sol uçtan değer düşerek pencereyi daraltır.

PK10. Dağarcık, önceki dersin dağarcığıdır: tohum 20260218, 40 dizi, her biri 12 değer, değerler −9 ile 20 arasında. Kırk dizinin kırkı negatif değer içerir. PK11. Ön koşulu sağlayan öbek, aynı dizilerin değerlerinin mutlak değeridir. İki öbeğin tek farkı işarettir; uzunluk, konum ve üreteç aynıdır. PK12. Hedef 25’tir ve bir alt dizi hedefi tam olarak tutturmak zorunda değildir; “hedeften küçük olmamak” yeterlidir. PK13. Kâhin kaba kuvvettir ve her zaman doğru sayılır. Yanıt bir uzunluktur; hiçbir alt dizi hedefi tutturamıyorsa yanıt tanımsızdır.

TOHUM = 20260218


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def dagarcik(tohum=TOHUM, n=40, uzunluk=12):
    r = uretec(tohum)
    return [{"no": i + 1, "dizi": [r(30) - 9 for _ in range(uzunluk)]}
            for i in range(n)]


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def kahin_en_kisa(dizi, hedef, s):
    """Butun bitisik alt dizileri dener. Her zaman dogru."""
    en_iyi = None
    for i in range(len(dizi)):
        toplam = 0
        for j in range(i, len(dizi)):
            s.say()
            toplam += dizi[j]
            if toplam >= hedef and (en_iyi is None or j - i + 1 < en_iyi):
                en_iyi = j - i + 1
                break
    return en_iyi


def kalip_kayan_pencere(dizi, hedef, s):
    """ONKOSUL: butun degerler negatif olmamali."""
    sol, toplam, en_iyi = 0, 0, None
    for sag in range(len(dizi)):
        s.say()
        toplam += dizi[sag]
        while toplam >= hedef:
            if en_iyi is None or sag - sol + 1 < en_iyi:
                en_iyi = sag - sol + 1
            toplam -= dizi[sol]
            sol += 1
            s.say()
    return en_iyi


def olc(kume, hedef):
    ayrilan, ak, ah = [], 0, 0
    for k in kume:
        s1, s2 = Sayac(), Sayac()
        a = kalip_kayan_pencere(k["dizi"], hedef, s1)
        b = kahin_en_kisa(k["dizi"], hedef, s2)
        ak, ah = ak + s1.adim, ah + s2.adim
        if a != b:
            ayrilan.append(k["no"])
    return {"ayrilan": len(ayrilan), "ilk_ayrilan": ayrilan[:6],
            "kalip_adim": ak, "kahin_adim": ah, "oran": round(ah / ak, 2)}


K = dagarcik()
P = [dict(k, dizi=[abs(x) for x in k["dizi"]]) for k in K]
print("dagarcik:", len(K), "dizi | negatif iceren:",
      sum(1 for k in K if any(x < 0 for x in k["dizi"])))
for ad, kume in (("on_kosul saglaniyor", P), ("on_kosul bozuk    ", K)):
    print(f"  {ad}", olc(kume, 25))

dagarcik: 40 dizi | negatif iceren: 40
  on_kosul saglaniyor {'ayrilan': 0, 'ilk_ayrilan': [], 'kalip_adim': 867, 'kahin_adim': 2396, 'oran': 2.76}
  on_kosul bozuk     {'ayrilan': 10, 'ilk_ayrilan': [2, 12, 13, 15, 24, 26], 'kalip_adim': 761, 'kahin_adim': 2462, 'oran': 3.24}

Ön koşul sağlandığında kalıp 867 adımda 40 girdinin 40’ında kâhinle aynı yanıtı veriyor; kâhin 2396 adım harcıyor, oran 2,76. Negatif değer içeren dağarcıkta ayrılan girdi 10 oluyor.

Buradaki sayı, önceki dersin 25’inden düşük ve bu düşüklük dersin en tehlikeli tarafıdır. Kalıp girdilerin dörtte üçünde hâlâ doğru yanıt veriyor. Bir sınama kümesi rastgele seçilseydi temiz sonuç verme olasılığı yüksekti; kusur, gözlemle değil kâhinle ortaya çıkar.

İkinci satırın oranı da dikkat çekicidir: 3,24, yani ön koşul sağlandığındaki 2,76’dan yüksek. Kalıp bozuk girdide daha az adım harcıyor (761’e karşı 867), çünkü negatif değerler toplamı düşürüyor ve küçültme döngüsü daha seyrek çalışıyor. Daha az adım daha iyi yanıt demek değildir.

Küçültme Kuralı Neye Dayanıyor

Kalıbın tek riskli satırı while toplam >= hedef döngüsüdür. Bu döngü, soldan bir değer düşüldüğünde toplamın azalacağını varsayar. Negatif olmayan değerlerde bu doğrudur; toplam, sol uç ilerledikçe tekdüze azalır ve döngü ilk kez koşulu bozduğunda o başlangıç için en kısa pencere bulunmuş olur.

Negatif bir değer düşüldüğünde toplam artar. O anda pencere daralmış ama toplam büyümüştür; kalıp bunu bir ilerleme sayar ve sol ucu bir daha geri almaz. Atlanan başlangıçlar arasında daha kısa bir çözüm varsa görülmez.

PK14. Kalıp sol ucu geri almaz; her konum en çok bir kez sol uçtan çıkar. Kalıbın doğrusal adım sayısı bu geri almama kuralından gelir, dolayısıyla kural gevşetilemez.

def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def dagarcik(tohum):
    r = uretec(tohum)
    return [[r(30) - 9 for _ in range(12)] for _ in range(40)]


def kahin_en_kisa(dizi, hedef):
    en_iyi = None
    for i in range(len(dizi)):
        toplam = 0
        for j in range(i, len(dizi)):
            toplam += dizi[j]
            if toplam >= hedef and (en_iyi is None or j - i + 1 < en_iyi):
                en_iyi = j - i + 1
                break
    return en_iyi


def kalip_kayan_pencere(dizi, hedef):
    sol, toplam, en_iyi = 0, 0, None
    for sag in range(len(dizi)):
        toplam += dizi[sag]
        while toplam >= hedef:
            if en_iyi is None or sag - sol + 1 < en_iyi:
                en_iyi = sag - sol + 1
            toplam -= dizi[sol]
            sol += 1
    return en_iyi


ikinci = dagarcik(20260218)[1]
print("girdi 2:", ikinci)
print("  kalip:", kalip_kayan_pencere(ikinci, 25),
      "| kahin:", kahin_en_kisa(ikinci, 25))
print("  mutlak degerle:", [abs(x) for x in ikinci])
print("  kalip:", kalip_kayan_pencere([abs(x) for x in ikinci], 25),
      "| kahin:", kahin_en_kisa([abs(x) for x in ikinci], 25))
print()
print("tohum      hedef  on_kosul     ayrilan/40   oran")
for tohum in (20260218, 20260219):
    for hedef in (25, 15):
        K = dagarcik(tohum)
        obek = (("saglaniyor", [[abs(x) for x in d] for d in K]), ("bozuk     ", K))
        for ad, kume in obek:
            ayrilan = sum(1 for d in kume
                          if kalip_kayan_pencere(d, hedef) != kahin_en_kisa(d, hedef))
            print(f"{tohum}  {hedef:5d}  {ad}  {ayrilan:8d}   {ayrilan / 40:.4f}")

girdi 2: [-6, 15, 10, 11, 6, -5, -4, 3, 2, 17, -8, 5]
  kalip: 3 | kahin: 2
  mutlak degerle: [6, 15, 10, 11, 6, 5, 4, 3, 2, 17, 8, 5]
  kalip: 2 | kahin: 2

tohum      hedef  on_kosul     ayrilan/40   oran
20260218     25  saglaniyor         0   0.0000
20260218     25  bozuk             10   0.2500
20260218     15  saglaniyor         0   0.0000
20260218     15  bozuk              6   0.1500
20260219     25  saglaniyor         0   0.0000
20260219     25  bozuk              8   0.2000
20260219     15  saglaniyor         0   0.0000
20260219     15  bozuk              6   0.1500

İkinci girdide kâhin 2 diyor, kalıp 3. Doğru yanıt 15 + 10 çiftidir; kalıp bu çifti göremiyor, çünkü sol uç -6 değerini düşürdüğünde toplam artmış ve pencere yanlış yerde sabitlenmiş. Kalıbın çıktısı yine bir uzunluk, yine akla yatkın, yine yanlış.

PK15. İkinci dağarcık 20260219 tohumundan gelir. Ayrılan girdi oranı aynı büyüklük düzeninde kalmazsa sonuç dağarcığa bağlıdır ve öyle yazılır.

İkinci dağarcıkta hedef 25 için ayrılan girdi 8, birincide 10; hedef 15 için ikisi de 6. Dört ölçümün dördü de 0,15 ile 0,25 arasında, yani aynı büyüklük düzeninde. Sonuç dağarcığa bağlı değildir. Ön koşulun sağlandığı dört satırda ayrılan girdi sıfırdır.

Ön koşul Pencerenin Değil, Kuralın

Kayan pencere adı iki ayrı kalıbı birden anar ve ikisinin ön koşulu aynı değildir. Yukarıdaki biçim değişken boyutludur: pencere bir koşul sağlanana kadar büyür, sağlandığında küçülür. Bir de sabit boyutlu biçim vardır: pencere hep k geniştir, sağdan bir değer girer, soldan bir değer çıkar.

Sabit boyutlu biçimde küçültme kuralı yoktur; pencere bir koşula bakarak daralmaz, yalnızca kayar. O hâlde toplamın tekdüze azalması da gerekmez.

PK16. Sabit boyutlu pencere yalnız artımlı toplam kullanır: bir toplama, bir çıkarma. Kalıbın adımı k’dan bağımsızdır; kâhinin adımı k ile büyür.

def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def dagarcik(tohum=20260218):
    r = uretec(tohum)
    return [[r(30) - 9 for _ in range(12)] for _ in range(40)]


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def kahin_sabit(dizi, k, s):
    """Her pencerenin toplamini sifirdan hesaplar."""
    en_iyi = None
    for i in range(len(dizi) - k + 1):
        toplam = 0
        for j in range(i, i + k):
            s.say()
            toplam += dizi[j]
        if en_iyi is None or toplam > en_iyi:
            en_iyi = toplam
    return en_iyi


def kalip_sabit(dizi, k, s):
    """Pencere sabit boyutlu: bir deger girer, bir deger cikar. Isaret on_kosulu yok."""
    toplam, en_iyi = 0, None
    for sag in range(len(dizi)):
        s.say()
        toplam += dizi[sag]
        if sag >= k:
            toplam -= dizi[sag - k]
        if sag >= k - 1 and (en_iyi is None or toplam > en_iyi):
            en_iyi = toplam
    return en_iyi


print("k  girdi           ayrilan/40  kalip  kahin   oran")
for k in (3, 4, 6):
    for ad, hazirla in (("negatifsiz", lambda d: [abs(x) for x in d]),
                        ("negatifli ", list)):
        ayrilan, ak, ah = 0, 0, 0
        for dizi in dagarcik():
            d = hazirla(dizi)
            s1, s2 = Sayac(), Sayac()
            ayrilan += (kalip_sabit(d, k, s1) != kahin_sabit(d, k, s2))
            ak, ah = ak + s1.adim, ah + s2.adim
        print(f"{k}  {ad}  {ayrilan:12d}  {ak:5d}  {ah:5d}  {ah / ak:5.2f}")

k  girdi           ayrilan/40  kalip  kahin   oran
3  negatifsiz             0    480   1200   2.50
3  negatifli              0    480   1200   2.50
4  negatifsiz             0    480   1440   3.00
4  negatifli              0    480   1440   3.00
6  negatifsiz             0    480   1680   3.50
6  negatifli              0    480   1680   3.50

Altı satırın altısında ayrılan girdi sıfır. Negatif değerler sabit boyutlu pencereyi hiç etkilemiyor; kalıbın adımı üç k değerinde de 480, kâhinin adımı k ile büyüyor ve oran 2,50’den 3,50’ye çıkıyor.

Bu, dersin yapısal sonucudur: ön koşul kalıbın adına değil, kalıbın içindeki tek bir kurala aittir. “Kayan pencere negatif değerle çalışmaz” cümlesi yanlıştır; doğru cümle, “toplamın tekdüze azaldığı varsayımına dayanan küçültme kuralı negatif değerle çalışmaz” cümlesidir. Bir kalıbı ön koşuluyla birlikte öğrenmek, kalıbın adını değil o kuralı bilmek demektir.

Üç Sayı

Ölçüt	Kâhin	Kalıp	Ayrılan girdi
Değişken pencere, ön koşul sağlanıyor	2396 adım	867 adım	0/40
Değişken pencere, ön koşul bozuk	2462 adım	761 adım	10/40
Sabit pencere (k=4), negatifli girdi	1440 adım	480 adım	0/40

İkinci satır kalıbın en az adımı harcadığı satırdır ve tek bozuk satırdır. Üçüncü satır aynı girdiyle sıfır ayrılma veriyor, çünkü kalıp değişti.

Denetim Doğruluğu Geri Alır, Hızlanmayı Almaz

Ön koşulu denetlemek ucuzdur: bir dizide negatif değer aramak en çok n karşılaştırmadır ve ilk negatifte durur. Denetim başarısızsa iş kâhine bırakılır. Bu düzenlemenin doğruluğu tamdır; sorulması gereken, geriye ne kadar hızlanma kaldığıdır.

PK17. Denetimli kalıp, denetimin adımlarını da kendi hanesine yazar; kâhine devredildiğinde kâhinin adımı da kalıbın adımına eklenir.

def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def dagarcik(tohum=20260218):
    r = uretec(tohum)
    return [[r(30) - 9 for _ in range(12)] for _ in range(40)]


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def kahin_en_kisa(dizi, hedef, s):
    en_iyi = None
    for i in range(len(dizi)):
        toplam = 0
        for j in range(i, len(dizi)):
            s.say()
            toplam += dizi[j]
            if toplam >= hedef and (en_iyi is None or j - i + 1 < en_iyi):
                en_iyi = j - i + 1
                break
    return en_iyi


def kalip_kayan_pencere(dizi, hedef, s):
    sol, toplam, en_iyi = 0, 0, None
    for sag in range(len(dizi)):
        s.say()
        toplam += dizi[sag]
        while toplam >= hedef:
            if en_iyi is None or sag - sol + 1 < en_iyi:
                en_iyi = sag - sol + 1
            toplam -= dizi[sol]
            sol += 1
            s.say()
    return en_iyi


def denetimli(dizi, hedef, s):
    """Onkosulu sinar; saglanmiyorsa kahine birakir."""
    for x in dizi:
        s.say()
        if x < 0:
            return kahin_en_kisa(dizi, hedef, s)
    return kalip_kayan_pencere(dizi, hedef, s)


for ad, hazirla in (("negatifsiz", lambda d: [abs(x) for x in d]),
                    ("negatifli ", list)):
    ayrilan, ad_denetimli, ad_kahin = 0, 0, 0
    for dizi in dagarcik():
        d = hazirla(dizi)
        s1, s2 = Sayac(), Sayac()
        ayrilan += (denetimli(d, 25, s1) != kahin_en_kisa(d, 25, s2))
        ad_denetimli += s1.adim
        ad_kahin += s2.adim
    print(f"{ad}  ayrilan {ayrilan}/40  denetimli kalip {ad_denetimli:5d}"
          f"  kahin {ad_kahin:5d}  oran {ad_kahin / ad_denetimli:.2f}")

negatifsiz  ayrilan 0/40  denetimli kalip  1347  kahin  2396  oran 1.78
negatifli   ayrilan 0/40  denetimli kalip  2568  kahin  2462  oran 0.96

Ayrılan girdi iki satırda da sıfır. Ama ikinci satırın oranı 0,96: negatifli dağarcıkta denetimli kalıp, kâhinden daha çok adım harcıyor. Bunun nedeni açıktır — kırk dizinin kırkı denetimden geçemiyor, iş kırk kez kâhine düşüyor ve denetimin 106 adımı üstüne biniyor. Ön koşulun sağlandığı dağarcıkta oran 1,78’de kalıyor, yani denetim orada bile 2,76’dan 1,78’e bir kayıp yazdırıyor.

Buradan çıkan okuma şudur: ön koşul denetimi bir doğruluk aracıdır, bir başarım aracı değildir. Girdilerin hangi oranda ön koşulu sağladığı bilinmeden denetimli kalıbın kazandıracağı söylenemez; bu dağarcıkta o oran sıfırdır ve kalıp bütünüyle kâhine dönüşmüştür.

Özet

• Kayan pencere iki işaretçiyi aynı yönde tutar ve toplamı sıfırdan hesaplamak yerine artımlı günceller.
• Değişken boyutlu biçimde küçültme kuralı, soldan değer düşüldüğünde toplamın azalacağını varsayar; bu varsayım yalnız negatif olmayan değerlerde doğrudur.
• Negatif içeren dağarcıkta kalıp 10 girdide kâhinden ayrılıyor ve bunu daha az adımla yapıyor; az adım doğruluk göstergesi değildir.
• İkinci dağarcıkta ayrılan girdi 8; oran aynı büyüklük düzeninde kaldığı için sonuç dağarcığa bağlı değildir.
• Sabit boyutlu pencere küçültme kuralı taşımadığı için negatif değerden etkilenmez: altı ölçümün altısında ayrılan girdi sıfırdır.

Sonraki Adım

İki kalıp da tek bir dizide, konum sayısı bilinerek çalıştı. Sonraki kalıp işaretçileri yine aynı yönde ilerletir ama farklı hızlarda ve uzunluğun bilinmediği bir yapıda: her düğümün bir ardılı vardır, sonu olup olmadığı bilinmez. Sonraki ders bu yapıda döngü tespitini ve orta elemanı ölçer; ön koşulu, ilerlemenin gerçekten tek yönlü olmasıdır ve o ön koşul bozulduğunda kalıp yalnız yanlış yanıt vermez, hiç durmayabilir.