İkili Arama ile Hata Avı

Önceki ders yeniden yazmanın ardından geriye ne kaldığını saydı: kaybolan işlemeler referans günlüğünde bir süre daha erişilebilir kalıyor, çöp toplama çalışınca o pencere kapanıyordu. Buraya kadar tarihçe değiştirilen bir nesneydi ve her değişikliğin bedeli dokunulan nesneyle ölçüldü.

Bu ders yönü çeviriyor. Tarihçeye dokunmuyoruz, ona soru soruyoruz: bu kusur hangi işlemede girdi? Bedelin birimi de değişiyor. Burada sayılan şey dokunulan nesne değil, adım — yani kâhine kaç kez başvurulduğu. Sorunun yanıtı tarihçenin içinde duruyor; mesele onu kaç denemede çıkarabildiğimiz.

Aramanın Dayandığı Tek Varsayım

Tarihçe boyunca her işleme için tek bir soru sorulabilir: kusur burada var mı? Yanıt bir noktaya kadar “yok”, o noktadan sonra hep “var” ise, tarihçe bu soru açısından tekdüzedir. Aranan şey, yanıtın döndüğü ilk işlemedir.

Bu tekdüzelik bir armağan değil, bir varsayımdır ve bozulabilir. Kusur girmiş, sonra bir başka işlemede yanlışlıkla örtülmüş, sonra yeniden açığa çıkmışsa yanıt iki kez döner ve arama yanlış işlemeyi gösterir. Aramayı kurmadan önce sorulacak soru budur: bu koşul tarihçe boyunca bir kez mi değişiyor?

Tekdüze bir yüklem üzerinde aralığı yarılayan algoritmanın kendisi Algoritmalar kursunun Arama ve Sıralama konusunda kuruldu; orada ölçülen şey algoritmanın karmaşıklığıydı. Burada ölçülen şey başka: aynı yöntem bir işleme dizisine uygulandığında tarihçe üzerinde kaç adım harcandığı. Aracın alt komutu bu yöntemi tarihçeye bağlar ve her adımda çalışma alanını o işlemeye taşır.

Aracın Yürüttüğü Döngü

Arama üç bildirimle kurulur: aramanın başlatılması, kusurun görüldüğü bir işleme ve kusurun görülmediği bir işleme. Bundan sonrasını araç yürütür; her adımda aralığın ortasındaki işlemeye geçer ve yanıtı bekler.

# öğretilen komutlar ve örnek döküm — çalıştırılmamıştır

git bisect start
git bisect bad HEAD
git bisect good v-onceki-surum

# araç aralığın ortasına geçer ve kalan aday sayısını bildirir:
Bisecting: <kalan aday> revisions left to test after this
[a1b2c3d] olcum: esik degerini ayardan oku

# her adımda yanıt verilir
git bisect good        # ya da: git bisect bad

# arama bittiğinde aracın çalışma alanı geri alınır
git bisect reset

İki ucun seçimi aramanın tek serbest parametresidir ve iki yönde de yanlış seçilebilir. Kusursuz uç gereğinden geriye konursa aday kümesi büyür ve her fazladan iki katı bir adım daha ödetir. Gereğinden ileriye konursa daha kötüsü olur: kusur o ucun gerisinde kalır, arama tekdüzelik varsayımını sağlamayan bir küme üzerinde yürür ve yine bir işleme gösterir. Yanlış uç seçiminin belirtisi yoktur; aramanın sonunda dönen işleme her iki durumda da aynı biçimde bildirilir.

Yanıtı elle vermek zorunlu değildir. Kusuru sınayan bir betik varsa arama tümüyle araca bırakılabilir; betiğin çıkış kodu kâhin yerine geçer, sıfır “kusur yok”, sıfırdan farklı “kusur var” demektir. Bu ayrım pratikte belirleyicidir: kâhin otomatikleştirilemiyorsa adım sayısı doğrudan insan emeğine dönüşür.

Aramanın bir de eksik yanıtı vardır. Aralığın ortasındaki işleme kurulmuyorsa ya da o noktada sınama anlamlı değilse, o işleme yanıt veremez ve arama onu atlamak zorunda kalır. Atlanan işleme aralığı yarılamaz; yalnızca komşusuna kayar. Kurulmayan bir pencere tarihçenin ortasındaysa, arama o pencerenin genişliği kadar adımı yarılama olmadan harcar.

Ölçümün varsayımları:

• TA1 — Tarihçe ortak kurgudan üretilir: dört ölçekte doğrusal bir işleme dizisi, her işleme beş dosyadan birine dokunuyor.
• TA2 — Kâhin kurguyu biz ürettiğimiz için bilinir ve kusurun tarihçenin dörtte üçünde girdiğini söyler. Kâhin her ölçekte aynı kuraldır ve ölçüm boyunca değiştirilmez.
• TA3 — Tekdüzelik varsayılır: kusur girdiği işlemeden sonra hiç kapanmaz. Ölçüm tekdüzeliğin bozulduğu durumu saymaz.
• TA4 — Bir adım, kâhine yapılan bir başvurudur. Kurulum, sınama ve çalışma alanının taşınması bir adımın içinde sayılır; adımlar birbirinden ayırt edilmez.
• TA5 — Doğrusal tarama tarihçeyi baştan sona yürür ve kusuru gördüğü ilk işlemede durur. Bu, aramanın en iyi durumda değil, kurgunun verdiği durumda ölçülmesidir.
• TA6 — İkinci bölümde tek değişen şey işlemelerin toplanma oranıdır: aynı değişiklikler, her biri daha az sayıda işlemede kayıtlı. Kurgu ve kâhin aynı kalır.
• TA7 — Kurgu doğrusaldır: aday kümesi iki sayı arasındaki aralıktır. Çatallanmış tarihçede aday kümesinin nasıl kurulduğu ölçümün dışında, ölçümün ardındaki bölümde tartışılır.

Ölçüm

"""Tarihcede kusurlu islemeyi bulmanin bedeli: adim sayisi.

Bolum 1 - iki tarama bicimi dort olcekte.
Bolum 2 - aramanin ucuzlamasi ile yanitin kabalasmasi.
"""
TOHUM = 20260814
DOSYALAR = ("olcum.py", "rapor.py", "kimlik.py", "ayar.py", "belge.md")


def uretec(tohum):
    d = tohum % 2147483646 + 1

    def r(n):
        nonlocal d
        d = (d * 48271) % 2147483647
        return d % n
    return r


def tarihce(n, tohum=TOHUM):
    """n islemelik dogrusal tarihce; her isleme bir dosyaya dokunuyor."""
    r, liste = uretec(tohum), []
    for i in range(n):
        dosya = DOSYALAR[r(5)]
        ikili = r(11) == 0
        liste.append({"no": i + 1, "dosya": dosya, "ikili": ikili,
                      "nesne": 2 + (40 if ikili else 0)})
    return liste


def kusurlu_isleme(t):
    """Kahin: kusuru getiren isleme, kurguyu biz yazdigimiz icin bilinir."""
    return len(t) * 3 // 4


def dogrusal_arama(t):
    hedef, adim = kusurlu_isleme(t), 0
    for x in t:
        adim += 1
        if x["no"] >= hedef:
            return adim
    return adim


def ikili_arama(t):
    hedef, alt, ust, adim = kusurlu_isleme(t), 1, len(t), 0
    while alt < ust:
        orta = (alt + ust) // 2
        adim += 1
        if orta >= hedef:
            ust = orta
        else:
            alt = orta + 1
    return adim


def aday_izi(t):
    """Her adimdan sonra geriye kalan aday isleme sayisi."""
    hedef, alt, ust, iz = kusurlu_isleme(t), 1, len(t), []
    while alt < ust:
        orta = (alt + ust) // 2
        if orta >= hedef:
            ust = orta
        else:
            alt = orta + 1
        iz.append(ust - alt + 1)
    return iz


def toplanmis(t, k):
    """Ayni degisiklikler, k tanesi tek islemede kayitli."""
    return [{"no": i + 1, "nesne": sum(x["nesne"] for x in t[i * k:(i + 1) * k])}
            for i in range(len(t) // k)]


OLCEKLER = (50, 200, 1000, 4000)
print(f"{'işleme':>7s} {'kusurlu':>8s} {'doğrusal adım':>14s} {'ikili adım':>11s}")
for n in OLCEKLER:
    t = tarihce(n)
    print(f"{n:7d} {kusurlu_isleme(t):8d} {dogrusal_arama(t):14d} "
          f"{ikili_arama(t):11d}")

buyuk = tarihce(4000)
print()
print("4000 işlemede adım adım kalan aday:", aday_izi(buyuk))

print()
print(f"{'işleme':>7s} {'toplama':>8s} {'ikili adım':>11s} {'yanıtın kapsamı':>16s}")
for k in (1, 2, 5, 10, 40):
    g = toplanmis(buyuk, k)
    print(f"{len(g):7d} {k:8d} {ikili_arama(g):11d} {k:16d}")

 işleme  kusurlu  doğrusal adım  ikili adım
     50       37             37           6
    200      150            150           7
   1000      750            750           9
   4000     3000           3000          11

4000 işlemede adım adım kalan aday: [2000, 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1]

 işleme  toplama  ikili adım  yanıtın kapsamı
   4000        1          11                1
   2000        2          10                2
    800        5           9                5
    400       10           8               10
    100       40           6               40

İki Bedelin Ayrıştığı Yer

Üst tablo aynı tarihçeyi iki biçimde tarıyor. Tarihçe 50’den 4000’e, yani seksen kat büyürken doğrusal tarama 37 adımdan 3000 adıma çıkıyor; ikili arama 6 adımdan 11’e. Seksen kat büyüyen bir tarihçede ikili arama iki kat bile artmıyor.

Doğrusal taramanın sütunu ikinci sütunla birebir aynı ve bu bir tesadüf değil: doğrusal tarama kusuru gördüğü ilk işlemede durduğu için harcadığı adım, kusurun tarihçedeki yeridir. Yani doğrusal taramanın bedeli tarihçenin uzunluğuna değil, kusurun nereye düştüğüne bağlıdır; kusur başlarda olsaydı ucuz, sonlarda olsaydı pahalı olurdu. Ölçüm bunu bir avantaj olarak da okumuyor, çünkü kusurun nerede olduğu aramadan önce bilinmiyor. Bilinseydi arama zaten gerekmezdi; ölçüm de bu yüzden kusuru sabit bir yere koyar ve iki biçimi aynı koşulda karşılaştırır.

İkili aramanın sütununda böyle bir bağımlılık yok. Ortadaki iz satırı nedenini gösteriyor: aday sayısı 2000’den başlayıp her adımda yarılanarak 1’e iniyor. Her yanıt aralığın yarısını eliyor, ve elenen yarı bir daha hiç sınanmıyor. Dört bin işlemelik tarihçede on bir yanıt, aday kümesini 1/4000 çözünürlüğüne indirmeye yetiyor. Dört ölçekte ulaşılan çözünürlük sırasıyla 1/50, 1/200, 1/1000 ve 1/4000’dir; ölçüm bundan küçük bir ayrımı gösteremez, çünkü tarihçenin kendi çözünürlüğü bir işlemedir.

Bu ayrım kursun ölçü ekseninin arama tarafındaki karşılığıdır: bedel tarihçenin uzunluğundan değil, bir adımın hangi kümeye dokunduğundan çıkıyor. Doğrusal tarama bir adımda bir işlemeye dokunuyor, ikili arama bir adımda kalan adayların yarısına.

Çatallanmış Tarihçede Aday Kümesi

Ölçümün kurgusu doğrusaldır: işlemeler bir dizi hâlindedir ve aralık iki sayı arasındadır. Gerçek bir tarihçe çoğu zaman doğrusal değildir; Dallanma ve İşbirliği kursunda kurulan birleştirme işlemesi tarihçeyi bir çizgi olmaktan çıkarır.

Arama bu durumda da çalışır ama aralığın anlamı değişir. Aday kümesi artık iki sayı arasındaki işlemeler değil, kusurlu bildirilen işlemeden erişilebilen ve kusursuz bildirilen işlemeden erişilemeyen işlemelerdir. Araç her adımda bu kümeyi en dengeli bölen işlemeye geçer. Yarılama fikri korunur; değişen tek şey neyin yarıldığıdır.

Bunun iki pratik sonucu var. Birincisi, bir yan dalda girmiş kusur o dal birleştirilene kadar ana çizgide görünmez, ama arama kusuru birleştirme işlemesinde değil yan daldaki gerçek işlemesinde bulur — çünkü o işleme de aday kümesinin içindedir. İkincisi, adım sayısını belirleyen şey iki uç arasındaki mesafe değil, erişilebilir kümenin büyüklüğüdür. İki uç birbirine yakın görünürken araya birleşmiş dallar geniş bir küme getiriyorsa adım sayısı o kümeye göre çıkar.

Bir Adımın Gerçek Bedeli

Adım sayısı tek başına bir emek ölçüsü değil. Her adım çalışma alanının o işlemeye taşınmasını, gerekiyorsa yeniden kurulmasını ve sınanmasını içerir. Kurulumu uzun süren bir bileşende on bir adım, kurulumu anlık olan bir bileşendeki üç bin adımdan pahalıya gelebilir.

Bu yüzden aramanın pratikteki ölçüsü şudur: adım sayısı × bir adımın süresi. İkili arama ilk çarpanı düşürür; ikinci çarpanı düşüren şey ise aramanın kendisi değil, kusuru sınayan betiğin hızıdır. Sınama betiği kurulmuş bir ortamda saniyeler içinde yanıt veriyorsa arama tümüyle araca bırakılabilir ve on bir adım tek bir komutun içinde geçer. Sınama elle yapılıyorsa on bir adım on bir kez insan dikkati demektir.

Atlanan işlemeler bu çarpımı bozan tek durumdur. Kurulmayan bir işleme yanıt üretmez; arama komşusuna kayar ve o kaymanın maliyeti yarılama olmadan ödenir. Kurulamayan pencereler geniş bir tarihçede aramayı doğrusala yaklaştırabilir. Bunun çaresi arama tarafında değil: tarihçenin her noktasında kurulabilir kalması, arama aracının değil tümleştirme disiplininin sonucudur.

Aramanın Kaydı ve Yanıtın Doğrulanması

Arama bir dizi karardan oluşur ve kararlar yanlış verilebilir. Bir adımda kusur gözden kaçırılıp “kusursuz” denmişse arama o yanıtın açtığı yönde ilerler ve sonunda yanlış bir işleme gösterir. Araç bunu fark edemez, çünkü elindeki tek bilgi verilen yanıtlardır.

Buna karşı iki alışkanlık vardır. Birincisi aramanın kaydının tutulmasıdır: verilen yanıtların dizisi bir günlüğe yazılır ve gerektiğinde yeniden oynatılabilir. Yanlış verildiğinden şüphelenilen adım günlükten çıkarılıp arama o noktadan yeniden yürütülebilir; tümüyle başa dönmek gerekmez.

# öğretilen komutlar ve örnek döküm — çalıştırılmamıştır

git bisect log > arama-kaydi.txt
git bisect reset
git bisect replay arama-kaydi.txt

git bisect skip                 # sınanamayan işlemede
git bisect run ./sinama.sh      # kâhin betiğin çıkış kodudur

İkincisi, bulunan işlemenin bir yanıt değil bir sav olmasıdır. Arama bittiğinde elde tek bir işleme vardır ve o işlemenin gerçekten kusuru getirdiği ayrıca sınanmalıdır: değişiklik geri alındığında kusur kayboluyor mu? Bu doğrulama on bir adımın üstüne on ikinciyi ekler. Ölçümde saymadığımız bu adım pratikte atlanmaz, çünkü aramanın bütün güvencesi kâhinin verdiği yanıtların doğruluğuna dayanır.

Kâhinin kesinliği de aynı yere bağlanır. “Yavaş çalışıyor” gibi bir ölçüt eşiği belirsiz bırakır ve aynı işleme iki denemede iki farklı yanıt alabilir. Kâhin ikili bir karara indirgenemiyorsa tekdüzelik varsayımı sınanamaz hâle gelir ve arama dayandığı zemini kaybeder. Aramanın kurulmasındaki asıl iş bu yüzden komutlarda değil, kusuru bir çıkış koduna indiren betiği yazmaktadır.

Yanıtın Çözünürlüğü

Alt tablo aynı değişiklikleri farklı büyüklükte işlemelere toplayarak aynı aramayı yeniden yapıyor. Dört bin değişiklik kırklı gruplara toplandığında tarihçe 100 işlemeye iniyor ve arama 11 yerine 6 adımda bitiyor. Beş adım kazanç.

Bedeli sağdaki sütunda: yanıtın kapsamı 1’den 40’a çıkıyor. Arama artık “bu işlemede girdi” demiyor, “bu kırk değişiklikten birinde girdi” diyor. Kalan iş aramanın dışında, işlemenin içinde, elle yapılacak. Takas eşit değildir — adım sayısı logaritmik düşerken yanıtın kabalığı doğrusal artıyor. On altı kat daha kaba bir yanıt için beş adım kazanılıyor.

Bu, Dallanma ve İşbirliği kursunun sıkıştırma ölçümüyle aynı biçimin başka bir birimdeki görüntüsüdür: orada temizlenen tarihçenin yanıtlayabildiği soru azalıyordu, burada aranan tarihçenin verebildiği yanıt kabalaşıyor. İkisinin ortak sonucu şudur: aramanın çözünürlüğü arama anında değil, işleme anında belirlenir. Atomik işleme alışkanlığı bir üslup tercihi değil, ileride sorulacak sorunun çözünürlüğünü belirleyen bir karardır.

Özet

• Arama tek bir varsayıma dayanır: kusurun varlığı tarihçe boyunca bir kez değişir. Tekdüzelik bozulursa arama yanlış işlemeyi gösterir ve bunu haber vermez.
• Tarihçe seksen kat büyürken doğrusal tarama 37 adımdan 3000 adıma çıkar, ikili arama 6’dan 11’e; bedel tarihçenin uzunluğundan değil, bir adımın dokunduğu kümeden gelir.
• Doğrusal taramanın adımı kusurun tarihçedeki yerine eşittir; ikili aramanınki yere değil yalnızca uzunluğa bağlıdır ve aday kümesini 1/4000 çözünürlüğüne indirir.
• Adım sayısı emeğin yarısıdır; diğer yarısı bir adımın süresidir ve onu belirleyen şey kâhinin otomatikleştirilebilmesidir.
• Çatallanmış tarihçede aday kümesi bir sayı aralığı değil, iki uçtan erişilebilirlikle tanımlanan kümedir; adım sayısını o kümenin büyüklüğü belirler.
• Değişiklikler kırklı gruplara toplandığında adım 11’den 6’ya iner ama yanıtın kapsamı 1’den 40’a çıkar; aramanın çözünürlüğü işleme anında belirlenir.

Sonraki Adım

İkili arama tarihçeye tek bir soru sorar ve yanıtı bir işleme olarak alır: kusur şurada girdi. Ama çoğu zaman sorulan soru bu değildir. Elde bir işleme yoktur, elde tek bir satır vardır ve sorulan şey o satırın oraya neden yazıldığıdır. Sonraki ders bu soruya bakar: bir satırın son yazarını bulmanın bedeli aynı tarihçede kaç adımdır, neden ikili aramanın adımıyla aynı biçimde büyümez, ve son yazarın gerçekten aranan kişi olmadığı durumda yanıt nereye kayar.