Aralık Birleştirme

Önceki üç kalıp girdiyi olduğu gibi aldı: iki işaretçi sıralı gelmesini bekliyordu, kayan pencere işaretlere bakıyordu, hızlı ve yavaş işaretçi ardıl bağlantısını izliyordu. Bu dersin kalıbı girdiyi önce yeniden düzenler. Örtüşen aralıkları birleştirmek, aralıkları bir ölçüte göre sıralamakla başlar ve sıralama bittikten sonra tek bir geçiş yeter.

Ön koşul artık verinin bir özelliği değildir; seçilen ölçütün kendisidir. Ölçüt yanlış seçildiğinde kalıp yine tek geçişte biter, yine bir aralık listesi döndürür ve yine hiçbir uyarı vermez. Bu ders üç yanlış ölçütü aynı kâhinle karşılaştırıp her birinin kaç girdide yanlış birleştirdiğini sayar.

Problem, Kâhin ve Kalıp

Problem şudur: verilen aralık kümesinde örtüşen aralıkları birleştirip en sade listeyi üretmek. Kâhin hiçbir sıralama yapmaz; örtüşen bir çift buldukça birleştirir ve hiçbir çift kalmayana kadar yineler. Bu, sonucu tanımı gereği doğru kılar ama her birleştirmede taramayı baştan başlatır.

Kalıp bir kez sıralar, sonra listeyi soldan sağa tarar: her aralık ya son birleşik aralığın sağ ucunu uzatır ya da yeni bir birleşik aralık açar.

PK25. Dağarcık 40 kümedir; her küme 12 aralık taşır. Başlangıç 0–60, uzunluk 1–9; tohum 20260218. PK26. Aralıklar kapalıdır: (4, 20) aralığı 4 ile 20 arasındaki bütün noktaları içerir ve (20, 25) ile örtüşür. PK27. Kâhinin ve kalıbın yanıtı, karşılaştırmadan önce sıralanır; ayrılma bir sıra farkından değil, yalnız içerik farkından doğar. PK28. Sıralamanın adımı kalıbın hanesine yazılır. Karşılaştırmalı bir yordam kullanılır ve her karşılaştırma bir adım sayılır; sıralama yordamlarının kendisi Algoritmalar kursunda ölçüldü ve burada tekrarlanmaz.

TOHUM, ARALIK, 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 aralik_dagarcik(tohum=TOHUM, n=DAGARCIK, adet=ARALIK):
    r = uretec(tohum)
    kume = []
    for i in range(n):
        liste = []
        for _ in range(adet):
            bas = r(61)
            liste.append((bas, bas + 1 + r(9)))
        kume.append({"no": i + 1, "aralik": liste})
    return kume


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

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


def kahin_birlestir(araliklar, s):
    """Ortusen bir cift buldukca birlestirir, degisiklik bitene kadar yineler."""
    kalan = [list(a) for a in araliklar]
    degisti = True
    while degisti:
        degisti = False
        for i in range(len(kalan)):
            for j in range(i + 1, len(kalan)):
                s.say()
                if kalan[i][0] <= kalan[j][1] and kalan[j][0] <= kalan[i][1]:
                    kalan[i] = [min(kalan[i][0], kalan[j][0]),
                                max(kalan[i][1], kalan[j][1])]
                    kalan.pop(j)
                    degisti = True
                    break
            if degisti:
                break
    return sorted(tuple(a) for a in kalan)


def sirala_sayarak(liste, anahtar, s):
    a = list(liste)
    for i in range(1, len(a)):
        j = i
        while j > 0:
            s.say()
            if anahtar(a[j - 1]) <= anahtar(a[j]):
                break
            a[j - 1], a[j] = a[j], a[j - 1]
            j -= 1
    return a


def kalip_birlestir(araliklar, anahtar, s):
    """ONKOSUL: siralama olcutu BASLANGIC olmali. Tek gecis yeter."""
    sonuc = []
    for bas, son in sirala_sayarak(araliklar, anahtar, s):
        s.say()
        if sonuc and bas <= sonuc[-1][1]:
            sonuc[-1] = (sonuc[-1][0], max(sonuc[-1][1], son))
        else:
            sonuc.append((bas, son))
    return sorted(sonuc)


OLCUT = (("baslangica gore", lambda a: a[0]),
         ("bitise gore    ", lambda a: a[1]),
         ("uzunluga gore  ", lambda a: a[1] - a[0]),
         ("siralamasiz    ", lambda a: 0))

K = aralik_dagarcik()
print("dagarcik:", len(K), "kume x", ARALIK, "aralik")
print("olcut            ayrilan/40  kalip  kahin   oran   ilk ayrilanlar")
for ad, anahtar in OLCUT:
    ayrilan, ak, ah = [], 0, 0
    for k in K:
        s1, s2 = Sayac(), Sayac()
        a = kalip_birlestir(k["aralik"], anahtar, s1)
        b = kahin_birlestir(k["aralik"], s2)
        ak, ah = ak + s1.adim, ah + s2.adim
        if a != b:
            ayrilan.append(k["no"])
    print(f"{ad}  {len(ayrilan):8d}  {ak:5d}  {ah:5d}  {ah / ak:5.2f}"
          f"   {ayrilan[:5]}")

dagarcik: 40 kume x 12 aralik
olcut            ayrilan/40  kalip  kahin   oran   ilk ayrilanlar
baslangica gore         0   2154   2974   1.38   []
bitise gore            29   2145   2974   1.39   [2, 3, 4, 6, 7]
uzunluga gore          40   2041   2974   1.46   [1, 2, 3, 4, 5]
siralamasiz            40    920   2974   3.23   [1, 2, 3, 4, 5]

Dört satır dört ayrı ölçüt, aynı kâhin, aynı dağarcık. Yalnız birinci satır doğrudur: başlangıca göre sıralayan kalıp 40 girdinin 40’ında kâhinle aynı listeyi üretiyor.

Son satır dersin en keskin sayısıdır. Sıralamasız kalıp en hızlısıdır — 920 adım, oran 3,23 — ve 40 girdinin 40’ında yanlıştır. Sıralamayı atlamak kalıbı üç kat hızlandırıyor ve tümüyle bozuyor. Sıralamanın adımı doğrudan ölçülebilir: 2154 ile 920 arasındaki 1234 adım, ön koşulu sağlamanın bedelidir ve kalıbın kazancının büyük bölümünü yiyor.

Kâhinin 2974 adımı da açıklama ister. Kâhin her birleştirmeden sonra taramayı baştan başlatır, çünkü yeni oluşan geniş aralık daha önce bakılmış bir çiftle örtüşebilir. Bu, kâhini bilerek pahalı kılan bir seçimdir ve amacı hızlanmak değil, hiçbir örtüşmeyi kaçırmamaktır. Kalıbın tek geçişte aynı sonucu vermesi, sıralamanın bu geriye dönüşü gereksiz kılmasından gelir: başlangıca göre sıralı bir listede, kapanmış bir birleşik aralığa sonradan dokunacak bir aralık kalmaz.

Ortadaki iki satır arasındaki fark da öğreticidir. Uzunluğa göre sıralamak 40 girdinin 40’ında yanlış; bitişe göre sıralamak 29’unda. İkisi de yanlış ölçüttür, ama biri girdilerin dörtte birinde doğru yanıt üretir — ve o dörtte bir, ölçütün doğru sanılmasına yeter.

Bitişe Göre Sıralamak Neden Bozuyor

Kalıbın tek karar kuralı bas <= sonuc[-1][1] karşılaştırmasıdır: yeni aralığın başlangıcı, açık duran birleşik aralığın sağ ucunu geçmiyorsa birleştir. Bu kural, sonraki her aralığın başlangıcının öncekinden küçük olmadığını varsayar. Başlangıca göre sıralamak tam olarak bunu güvenceye alır.

Bitişe göre sıralandığında geç başlayan ama erken biten bir aralık öne geçebilir; onun arkasından gelen, daha erken başlayan bir aralık artık birleşme koşulunu sağlamaz ve yeni bir birleşik aralık açar. Sonuç listesinde birbirini kapsayan iki kayıt kalır.

def uretec(tohum):
    d = tohum

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


def aralik_dagarcik(tohum, n=40, adet=12):
    r = uretec(tohum)
    kume = []
    for i in range(n):
        liste = []
        for _ in range(adet):
            bas = r(61)
            liste.append((bas, bas + 1 + r(9)))
        kume.append({"no": i + 1, "aralik": liste})
    return kume


def kahin_birlestir(araliklar):
    kalan = [list(a) for a in araliklar]
    degisti = True
    while degisti:
        degisti = False
        for i in range(len(kalan)):
            for j in range(i + 1, len(kalan)):
                if kalan[i][0] <= kalan[j][1] and kalan[j][0] <= kalan[i][1]:
                    kalan[i] = [min(kalan[i][0], kalan[j][0]),
                                max(kalan[i][1], kalan[j][1])]
                    kalan.pop(j)
                    degisti = True
                    break
            if degisti:
                break
    return sorted(tuple(a) for a in kalan)


def kalip_birlestir(araliklar, anahtar):
    sonuc = []
    for bas, son in sorted(araliklar, key=anahtar):
        if sonuc and bas <= sonuc[-1][1]:
            sonuc[-1] = (sonuc[-1][0], max(sonuc[-1][1], son))
        else:
            sonuc.append((bas, son))
    return sorted(sonuc)


kucuk = [(4, 20), (6, 8), (10, 12)]
print("kucuk ornek        :", kucuk)
print("  kahin            :", kahin_birlestir(kucuk))
print("  baslangica gore  :", kalip_birlestir(kucuk, lambda a: a[0]))
print("  bitise gore      :", kalip_birlestir(kucuk, lambda a: a[1]),
      "  <- bitise gore siralama:", sorted(kucuk, key=lambda a: a[1]))
print()
print("tohum      olcut            ayrilan/40   oran")
for tohum in (20260218, 20260219):
    K = aralik_dagarcik(tohum)
    for ad, anahtar in (("baslangica gore", lambda a: a[0]),
                        ("bitise gore    ", lambda a: a[1]),
                        ("uzunluga gore  ", lambda a: a[1] - a[0]),
                        ("siralamasiz    ", lambda a: 0)):
        ayrilan = sum(1 for k in K
                      if kalip_birlestir(k["aralik"], anahtar)
                      != kahin_birlestir(k["aralik"]))
        print(f"{tohum}  {ad}  {ayrilan:8d}   {ayrilan / 40:.4f}")

kucuk ornek        : [(4, 20), (6, 8), (10, 12)]
  kahin            : [(4, 20)]
  baslangica gore  : [(4, 20)]
  bitise gore      : [(6, 8), (10, 20)]   <- bitise gore siralama: [(6, 8), (10, 12), (4, 20)]

tohum      olcut            ayrilan/40   oran
20260218  baslangica gore         0   0.0000
20260218  bitise gore            29   0.7250
20260218  uzunluga gore          40   1.0000
20260218  siralamasiz            40   1.0000
20260219  baslangica gore         0   0.0000
20260219  bitise gore            32   0.8000
20260219  uzunluga gore          40   1.0000
20260219  siralamasiz            40   1.0000

Üç aralıklı küçük örnek mekanizmayı bütünüyle gösteriyor. Doğru yanıt tek aralıktır: (6, 8) ve (10, 12) tümüyle (4, 20) içindedir. Bitişe göre sıralanınca (4, 20) listenin sonuna düşüyor; kalıp önce (6, 8) ile başlıyor, (10, 12) birleşmiyor ve yeni bir kayıt açılıyor, sonra (4, 20) gelip onu (10, 20) yapıyor. Geriye (6, 8) kaydı kapsanmış olduğu hâlde ayrı duruyor.

PK29. İkinci dağarcık 20260219 tohumundan gelir. Bitişe göre sıralamada ayrılan girdi 32/40, birincide 29/40; oran 0,7250 ile 0,8000, aynı büyüklük düzeninde. Sonuç dağarcığa bağlı değildir. Uzunluğa göre ve sıralamasız ölçütler iki dağarcıkta da 40/40’tır.

Ölçüt Yalnız Anahtar Değil, Eşitlik Kuralıdır

Sıralama ölçütü seçildikten sonra bir soru daha kalır ve çoğu zaman sorulmaz: aynı değere sahip iki kayıt hangi sırayla gelecek. Aralıklarla çalışan ikinci bir problem bu soruyu ölçülebilir kılar: bir noktada en çok kaç aralık aynı anda açık.

Kalıp aralıkları olaylara çevirir — her başlangıç bir açılış, her bitiş bir kapanış — ve olayları koordinata göre sıralayıp tek geçişte sayar. Bir aralığın bittiği koordinatta başka bir aralık başlıyorsa, kapanışın açılıştan önce işlenmesi gerekir; kapalı sayılan bir uç iki kez sayılırsa açık aralık sayısı şişer.

PK30. Bu ölçümde aralıklar yarı açıktır: bir aralık başlangıcını içerir, bitişini içermez. Kâhin her başlangıç noktasında kaç aralığın açık olduğunu tek tek sayar. PK31. Dağarcığın 32 kümesinde bir aralığın bitişi başka bir aralığın başlangıcıyla çakışır; eşitlik kuralının etkisi ancak bu kümelerde görülebilir.

def uretec(tohum):
    d = tohum

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


def aralik_dagarcik(tohum=20260218, n=40, adet=12):
    r = uretec(tohum)
    kume = []
    for i in range(n):
        liste = []
        for _ in range(adet):
            bas = r(61)
            liste.append((bas, bas + 1 + r(9)))
        kume.append({"no": i + 1, "aralik": liste})
    return kume


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

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


def kahin_ortusme(araliklar, s):
    """Her baslangic noktasinda kac aralik acik. Butun ciftler denenir."""
    en_cok = 0
    for bas, _ in araliklar:
        acik = 0
        for b, y in araliklar:
            s.say()
            if b <= bas < y:
                acik += 1
        en_cok = max(en_cok, acik)
    return en_cok


def kalip_ortusme(araliklar, once_bitis, s):
    """ONKOSUL: ayni koordinatta BITIS olayi baslangictan once islenmeli."""
    olay = []
    for bas, son in araliklar:
        olay.append((bas, 1 if once_bitis else 0, +1))
        olay.append((son, 0 if once_bitis else 1, -1))
    en_cok = acik = 0
    for _, _, delta in sorted(olay):
        s.say()
        acik += delta
        en_cok = max(en_cok, acik)
    return en_cok


K = aralik_dagarcik()
carpisan = sum(1 for k in K
               if {b for b, _ in k["aralik"]} & {y for _, y in k["aralik"]})
print("dagarcik: 40 kume x 12 aralik | bir bitisi bir baslangicla cakisan kume:",
      carpisan)
print("olay sirasi     ayrilan/40  kalip  kahin   oran   ilk ayrilanlar")
for ad, once_bitis in (("bitis once    ", True), ("baslangic once", False)):
    ayrilan, ak, ah = [], 0, 0
    for k in K:
        s1, s2 = Sayac(), Sayac()
        a = kalip_ortusme(k["aralik"], once_bitis, s1)
        b = kahin_ortusme(k["aralik"], s2)
        ak, ah = ak + s1.adim, ah + s2.adim
        if a != b:
            ayrilan.append(k["no"])
    print(f"{ad}  {len(ayrilan):10d}  {ak:5d}  {ah:5d}  {ah / ak:5.2f}"
          f"   {ayrilan[:5]}")

dagarcik: 40 kume x 12 aralik | bir bitisi bir baslangicla cakisan kume: 32
olay sirasi     ayrilan/40  kalip  kahin   oran   ilk ayrilanlar
bitis once               0    960   5760   6.00   []
baslangic once           8    960   5760   6.00   [5, 7, 8, 15, 31]

İki satırın adım sütunları birebir aynı: kalıp 960, kâhin 5760, oran 6,00. Değişen tek şey aynı koordinattaki iki olayın hangisinin önce işlendiğidir ve bu tek karar 8 girdide yanıtı değiştiriyor.

Sekiz sayısı 32’nin çeyreğinden azdır ve bu, ölçütün neden gözden kaçtığını açıklar. Çakışmanın olmadığı 8 kümede eşitlik kuralının hiçbir etkisi yoktur; çakışmanın olduğu 32 kümenin çoğunda da en çok örtüşme başka bir yerde oluştuğu için sonuç değişmez. Kural yalnız 8 girdide görünür — ama o 8 girdide yanlıştır, ve hangi 8 girdi olduğu ancak kâhinle bilinir.

Üç Sayı

Ölçüt	Kâhin	Kalıp	Ayrılan girdi
Başlangıca göre sıralı	2974 adım	2154 adım	0/40
Bitişe göre sıralı	2974 adım	2145 adım	29/40
Sıralamasız	2974 adım	920 adım	40/40
Örtüşme sayımı, bitiş önce	5760 adım	960 adım	0/40
Örtüşme sayımı, başlangıç önce	5760 adım	960 adım	8/40

Beş satırın hiçbirinde adım sütunu doğruluk hakkında bilgi taşımıyor; üçüncü satırda en düşük adımla en yüksek yanlış sayısı bir arada duruyor. Kalıbın ön koşulu tek bir cümleyle söylenebilir: sıralama anahtarı, kalıbın tek karar kuralının varsaydığı şeyi güvenceye almalıdır — ne fazlası ne eksiği. Ölçütü “doğal görünen” bir alana bakarak seçmek, karar kuralına bakmadan seçmektir.

Özet

• Aralık birleştirme, girdiyi önce sıralayan ilk kalıptır; ön koşulu verinin değil seçilen ölçütün bir özelliğidir.
• Başlangıca göre sıralamak 40 girdinin 40’ında doğru; bitişe göre sıralamak 29, uzunluğa göre sıralamak ve sıralamamak 40 girdide kâhinden ayrılıyor.
• Sıralamayı atlamak kalıbı 2154 adımdan 920 adıma indiriyor ve bütün girdilerde yanlış yapıyor; en hızlı satır en bozuk satırdır.
• İkinci dağarcıkta bitişe göre ayrılan girdi 32; oran aynı büyüklük düzeninde kaldığı için sonuç dağarcığa bağlı değildir.
• Örtüşme sayımında aynı koordinattaki olay sırası tek başına 8 girdide yanıtı değiştiriyor; adım sayısı iki durumda da birebir aynı kalıyor.

Sonraki Adım

Bu kalıp sıralamanın bedelini ödeyip karşılığında tek geçiş aldı. Sonraki kalıp sıralamayı bütünüyle atlar: değerlerin kendi konumlarını bildiği bir aralıkta, her değer doğrudan gideceği yere yerleştirilir ve karşılaştırma hiç yapılmaz. Ön koşulu ağırdır — değerler 1 ile n arasında ve tekrarsız olmalıdır — ve bozulduğunda kalıp yalnız yanlış yanıt vermez, dönüp durur. Sonraki ders bu iki kusuru ayrı ayrı sayacak.