İki İşaretçi

Önceki konu bir algoritmanın doğruluğunun olasılıkla ifade edilebileceğini gösterdi: beklenen başarım bir dağılımdır, tek koşum bir örnektir. Bu konu farklı bir belirsizlik kaynağıyla açılıyor ve bu kaynak olasılıksal değil yapısaldır. Bir problem çözme kalıbı seçmek bir hızlanma satın almak değil, bir ön koşulu kabul etmektir.

Ön koşul sağlandığı sürece kalıp hem doğru hem ucuzdur. Sağlanmadığında kalıp durmaz, uyarmaz, yavaşlamaz — yanlış yanıt verir, ve yanlışlığı çıktısına bakarak anlaşılmaz. Bu yüzden konunun sekiz dersinin sekizi de aynı çerçeveyi kurar: bir kâhin (kaba kuvvet, her zaman doğru, her zaman pahalı), bir kalıp, ve ikisinin ayrıldığı girdi sayısı. İlk kalıp iki işaretçidir; ön koşulu tek cümledir: dizi sıralı olmalı.

Problem, Kâhin ve Kalıp

Problem şudur: bir dizide toplamı hedefe eşit iki ayrı konum var mı. Kâhin bütün çiftleri dener; n değerli dizide $n(n-1)/2$ çift vardır ve kâhin gerektiğinde hepsine bakar. Kalıp iki işaretçiyi dizinin iki ucuna koyar, toplam hedeften küçükse soldakini sağa, büyükse sağdakini sola kaydırır.

PK1. Ölçü adımdır, süre değildir. Sayaç her karşılaştırmayı bir adım sayar ve gerçek zaman hiçbir yerde ölçülmez. PK2. Dağarcık belirlenimci bir üreteçten gelir; tohum 20260218. Aynı tohum aynı 40 diziyi verir. PK3. Her dizi 12 değer taşır, değerler −9 ile 20 arasındadır. PK4. Kâhin kaba kuvvettir ve her zaman doğru sayılır. Kalıbın doğruluğu ancak kâhinle karşılaştırılarak iddia edilir. PK5. Ön koşulu sağlayan öbek, aynı 40 dizinin sıralanmış biçimidir; başka bir üreteçten gelmez. İki öbeğin tek farkı sıradır.

TOHUM, UZUNLUK, DAGARCIK = 20260218, 12, 40


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=DAGARCIK, uzunluk=UZUNLUK):
    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, n=1):
        self.adim += n


def kahin_ciftler(dizi, hedef, s):
    """Butun ciftleri dener. Her zaman dogru, her zaman pahali."""
    for i in range(len(dizi)):
        for j in range(i + 1, len(dizi)):
            s.say()
            if dizi[i] + dizi[j] == hedef:
                return True
    return False


def kalip_iki_isaretci(dizi, hedef, s):
    """ONKOSUL: dizi sirali olmali."""
    sol, sag = 0, len(dizi) - 1
    while sol < sag:
        s.say()
        t = dizi[sol] + dizi[sag]
        if t == hedef:
            return True
        if t < hedef:
            sol += 1
        else:
            sag -= 1
    return False


def olc(kume, hedef):
    ayrilan, ak, ah = [], 0, 0
    for k in kume:
        s1, s2 = Sayac(), Sayac()
        a = kalip_iki_isaretci(k["dizi"], hedef, s1)
        b = kahin_ciftler(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()
S = [dict(k, dizi=sorted(k["dizi"])) for k in K]
print("dagarcik:", len(K), "dizi x", UZUNLUK, "deger | kendiliginden sirali:",
      sum(1 for k in K if k["dizi"] == sorted(k["dizi"])))
for ad, kume in (("on_kosul saglaniyor", S), ("on_kosul bozuk    ", K)):
    print(f"  {ad}", olc(kume, 11))

dagarcik: 40 dizi x 12 deger | kendiliginden sirali: 0
  on_kosul saglaniyor {'ayrilan': 0, 'ilk_ayrilan': [], 'kalip_adim': 154, 'kahin_adim': 972, 'oran': 6.31}
  on_kosul bozuk     {'ayrilan': 25, 'ilk_ayrilan': [1, 2, 3, 6, 8, 9], 'kalip_adim': 372, 'kahin_adim': 866, 'oran': 2.33}

Üç sayı yan yana duruyor. Ön koşul sağlandığında kalıp 40 girdinin 40’ında kâhinle aynı yanıtı veriyor ve 154 adım harcıyor; kâhin 972 adım harcıyor, oran 6,31. Ön koşul bozulduğunda ayrılan girdi 25 oluyor ve oran 2,33’e düşüyor.

İkinci satırın en önemli tarafı ayrılan girdi sayısı değil, ikisinin birlikte olmasıdır. Yanlışlık ucuz da değildir: kalıbın adımı 154’ten 372’ye çıkıyor, çünkü sırasız dizide işaretçiler doğru çifti bulamadan uçlarda buluşuyor ve kalıp erken çıkamıyor. Hızlanma 6,31 kattan 2,33 kata düşerken doğruluk da gidiyor.

Ayrılan Girdide Ne Oluyor

Ayrılmanın nedeni tek bir yerdedir. Kalıp, “toplam küçükse soldakini büyüt” kuralını uygularken soldaki değerin sağa doğru büyüdüğünü varsayar. Sıralı olmayan dizide bu varsayım yanlıştır; işaretçi bir kez yanlış yöne kaydırıldığında atlanan konumlara bir daha dönülmez.

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_ciftler(dizi, hedef):
    for i in range(len(dizi)):
        for j in range(i + 1, len(dizi)):
            if dizi[i] + dizi[j] == hedef:
                return True, (dizi[i], dizi[j])
    return False, None


def kalip_iki_isaretci(dizi, hedef):
    sol, sag = 0, len(dizi) - 1
    while sol < sag:
        t = dizi[sol] + dizi[sag]
        if t == hedef:
            return True
        if t < hedef:
            sol += 1
        else:
            sag -= 1
    return False


ilk = dagarcik(20260218)[0]
print("girdi 1  :", ilk)
print("  kalip  :", kalip_iki_isaretci(ilk, 11))
print("  kahin  :", kahin_ciftler(ilk, 11))
print("  sirali :", sorted(ilk), "-> kalip", kalip_iki_isaretci(sorted(ilk), 11))
print()
print("tohum      hedef  on_kosul     ayrilan/40")
for tohum in (20260218, 20260219):
    for hedef in (11, 25):
        K = dagarcik(tohum)
        for ad, kume in (("saglaniyor", [sorted(d) for d in K]), ("bozuk     ", K)):
            ayrilan = sum(1 for d in kume
                          if kalip_iki_isaretci(d, hedef) != kahin_ciftler(d, hedef)[0])
            print(f"{tohum}  {hedef:5d}  {ad}  {ayrilan:8d}"
                  f"    oran {ayrilan / 40:.4f}")

girdi 1  : [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1]
  kalip  : False
  kahin  : (True, (-5, 16))
  sirali : [-8, -5, -1, -1, 1, 2, 2, 4, 5, 6, 16, 17] -> kalip True

tohum      hedef  on_kosul     ayrilan/40
20260218     11  saglaniyor         0    oran 0.0000
20260218     11  bozuk             25    oran 0.6250
20260218     25  saglaniyor         0    oran 0.0000
20260218     25  bozuk             22    oran 0.5500
20260219     11  saglaniyor         0    oran 0.0000
20260219     11  bozuk             24    oran 0.6000
20260219     25  saglaniyor         0    oran 0.0000
20260219     25  bozuk             16    oran 0.4000

Birinci girdide kâhin (-5, 16) çiftini buluyor; kalıp False döndürüyor. Aynı dizi sıralandığında kalıp da True döndürüyor. Girdi değişmedi, yalnız sırası değişti — kalıbın yanıtını değiştiren şey verinin içeriği değil, ön koşulun sağlanıp sağlanmadığıdır.

PK6. Ayrılan girdi sayısı 40 üzerindendir. 40 girdide 1 ayrılma 0,0250’dir; 1 girdilik fark ölçülmemiş sayılır, 3 ve üzeri anlamlıdır. PK7. İkinci dağarcık 20260219 tohumundan gelir ve yalnız oranın büyüklük düzenini sınamak için kullanılır.

İkinci dağarcıkta hedef 11 için ayrılan girdi 24, birincide 25. Hedef 25 için 16 ve 22. Dört ölçümün dördünde de oran 0,40 ile 0,63 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 ve bu da dağarcıktan bağımsızdır.

Ön koşulu Sağlamanın Bedeli

Buraya kadarki ölçüm bir soruyu açıkta bırakıyor: dizi sıralı değilse sıralanabilir. O hâlde kalıp yine kullanılabilir. Ama sıralamanın kendisi bir adım harcar ve bu adım kalıbın hanesine yazılmalıdır.

PK8. Ön koşulu sağlamanın bedeli ölçülürken sıralama karşılaştırmalı bir yordamla yapılır ve karşılaştırmaları adım olarak sayılır. Sıralama yordamlarının kendisi Algoritmalar kursunda ölçüldü; burada tekrarlanmaz, yalnız adımı sayılı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_ciftler(dizi, hedef, s):
    for i in range(len(dizi)):
        for j in range(i + 1, len(dizi)):
            s.say()
            if dizi[i] + dizi[j] == hedef:
                return True
    return False


def kalip_iki_isaretci(dizi, hedef, s):
    sol, sag = 0, len(dizi) - 1
    while sol < sag:
        s.say()
        t = dizi[sol] + dizi[sag]
        if t == hedef:
            return True
        if t < hedef:
            sol += 1
        else:
            sag -= 1
    return False


def sirala_sayarak(dizi, s):
    """Onkosulu saglamanin bedeli. Karsilastirmalar adim olarak sayilir."""
    a = list(dizi)
    for i in range(1, len(a)):
        j = i
        while j > 0:
            s.say()
            if a[j - 1] <= a[j]:
                break
            a[j - 1], a[j] = a[j], a[j - 1]
            j -= 1
    return a


print("hedef  dogru  yalniz kalip  siralama dahil  kahin   oran")
for hedef in (11, 25):
    yalniz, dahil, kahin, dogru = 0, 0, 0, 0
    for dizi in dagarcik():
        sa, sk, sh = Sayac(), Sayac(), Sayac()
        y = kalip_iki_isaretci(sirala_sayarak(dizi, sa), hedef, sk)
        h = kahin_ciftler(dizi, hedef, sh)
        yalniz += sk.adim
        dahil += sa.adim + sk.adim
        kahin += sh.adim
        dogru += (y == h)
    print(f"{hedef:5d}  {dogru:2d}/40  {yalniz:12d}  {dahil:14d}  {kahin:5d}"
          f"  {kahin / dahil:5.2f}")

hedef  dogru  yalniz kalip  siralama dahil  kahin   oran
   11  40/40           154            1737    866   0.50
   25  40/40           352            1935   1564   0.81

Doğruluk geri geldi: 40/40. Ama oran 1’in altına düştü. Hedef 11 için sıralama dahil toplam 1737 adım, kâhin 866 adım; kalıp kâhinin iki katı iş yapıyor. Hedef 25 için 1935’e karşı 1564, oran 0,81.

Bu, konunun ikinci iddiasının ilk ödemesidir: hızlandırma bazen hızlandırmaz. Bu büyüklükte bir girdide iki işaretçi, ön koşulu kendisi sağlamak zorunda kaldığında kaba kuvvetten pahalıdır. Kalıbın kazandığı yer, sıralamanın bir kez yapılıp çok kez sorgulandığı ya da verinin zaten sıralı geldiği durumdur. Dizi uzadıkça denge değişir — sıralama $n \log n$, kâhin $n^2$ büyür — ama bu dağarcıkta 12 değer, dengeyi kaba kuvvetin lehine bırakacak kadar küçüktür.

Adım Sayısı Doğruluk Hakkında Bir Şey Söylemez

Yukarıdaki iki ölçümde ayrılma, adımda bir değişiklikle birlikte geldi: 154’ten 372’ye. Bu bir kural değildir ve buna güvenmek tehlikelidir. Aynı kalıbın sayan biçimi bunu gösterir. Problem şimdi “toplamı hedeften küçük kaç çift var” sorusudur; kalıp, sağ uçta bir çift sayıldığında aradaki bütün çiftlerin de sayılacağını kullanır.

PK9. Sayan biçimde kalıp erken çıkamaz; her koşumda işaretçiler tam olarak n−1 adım atar. Adım sayısı bu yüzden girdinin içeriğinden bağımsızdı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_kucuk_cift(dizi, hedef, s):
    """Toplami hedeften kucuk cift sayisi. Butun ciftler denenir."""
    say = 0
    for i in range(len(dizi)):
        for j in range(i + 1, len(dizi)):
            s.say()
            if dizi[i] + dizi[j] < hedef:
                say += 1
    return say


def kalip_kucuk_cift(dizi, hedef, s):
    """ONKOSUL: dizi sirali olmali. Sag ucta bir cift sayilirsa aradakiler de sayilir."""
    sol, sag, say = 0, len(dizi) - 1, 0
    while sol < sag:
        s.say()
        if dizi[sol] + dizi[sag] < hedef:
            say += sag - sol
            sol += 1
        else:
            sag -= 1
    return say


print("on_kosul     ayrilan/40  kalip  kahin   oran")
for ad, hazirla in (("saglaniyor", sorted), ("bozuk     ", list)):
    ayrilan, ak, ah = 0, 0, 0
    for dizi in dagarcik():
        d = hazirla(dizi)
        s1, s2 = Sayac(), Sayac()
        a = kalip_kucuk_cift(d, 6, s1)
        b = kahin_kucuk_cift(d, 6, s2)
        ak, ah = ak + s1.adim, ah + s2.adim
        ayrilan += (a != b)
    print(f"{ad}  {ayrilan:8d}  {ak:5d}  {ah:5d}  {ah / ak:5.2f}")

on_kosul     ayrilan/40  kalip  kahin   oran
saglaniyor         0    440   2640   6.00
bozuk             39    440   2640   6.00

İki satırın adım sütunları birebir aynı: kalıp 440, kâhin 2640, oran 6,00. Ayrılan girdi sütunu ise 0’dan 39’a çıkıyor — 40 girdinin 39’unda kalıp yanlış bir sayı döndürüyor. Kalıp yine bir tam sayı veriyor, yine altı kat hızlı, yine hiçbir uyarı üretmiyor.

Bu, konunun üçüncü iddiasının neden gerekli olduğunu gösteriyor. Adım sayısı bir başarım ölçüsüdür ve doğruluk hakkında hiçbir şey söylemez. Kaba kuvvet burada bir “yavaş seçenek” değil, 39 yanlış yanıtı görünür kılan tek araçtır. Kâhin olmasaydı bu tablonun iki satırı ayırt edilemezdi.

Üç Sayı

Ölçüt	Kâhin	Kalıp	Ayrılan girdi
Ön koşul sağlanıyor (hedef 11)	972 adım	154 adım	0/40
Ön koşul bozuk (hedef 11)	866 adım	372 adım	25/40
Ön koşulu sağlayarak (hedef 11)	866 adım	1737 adım	0/40
Sayan biçim, ön koşul bozuk	2640 adım	440 adım	39/40

Üç satır üç ayrı karar noktasıdır. Birinci satır kalıbın vaadidir. İkinci satır ön koşul denetlenmediğinde ne olduğunu gösterir: yanıtların yüzde altmış ikisi bozuk ve hızlanma üçte iki oranında erimiş. Üçüncü satır ön koşulu kendi elinle sağlamanın faturasıdır.

Kalıbın bir denetim eklenerek güvenli kılınabileceği düşünülebilir: dizinin sıralı olup olmadığına bakılır, değilse kâhine dönülür. Bu denetim n−1 karşılaştırmadır, yani 40 dizi için 440 adım. Denetim doğruluğu kurtarır ama hızlanmayı kurtarmaz: sırasız girdide iş yine kâhine kalır. Ölçülmesi gereken şey denetimin maliyeti değil, girdilerin kaçının ön koşulu sağladığıdır. Bu dağarcıkta o sayı sıfırdır.

Özet

• Bir kalıp seçmek bir ön koşulu kabul etmektir; iki işaretçinin ön koşulu dizinin sıralı olmasıdır.
• Ön koşul sağlandığında kalıp 40 girdinin 40’ında kâhinle aynı yanıtı veriyor ve 972 yerine 154 adım harcıyor; oran 6,31.
• Ön koşul bozulduğunda kalıp 25 girdide kâhinden ayrılıyor ve hızlanma 2,33 kata düşüyor; yanlışlık ucuz değildir.
• İkinci dağarcıkta ayrılan girdi 24; oran aynı büyüklük düzeninde kaldığı için sonuç dağarcığa bağlı değildir.
• Ön koşulu sıralayarak sağlamak doğruluğu geri getiriyor ama toplam adımı 1737’ye çıkarıyor ve kalıbı kâhinden pahalı kılıyor.

Sonraki Adım

İki işaretçi diziyi iki uçtan sıkıştırıyordu ve ön koşulu sıraydı. Sonraki kalıp işaretçileri aynı yönde tutar ve aralarındaki bölgeyi bir pencere gibi büyütüp küçültür; kazancı, pencere kaydıkça toplamı sıfırdan hesaplamak yerine artımlı güncellemesinden gelir. Ön koşulu da farklıdır ve sıraya hiç bakmaz: hiçbir değer negatif olmamalıdır. Sonraki ders bu ön koşulun bozulduğu 10 girdiyi kâhinle sayacak.