Eşle-İndirge Modeli

Önceki ders kümenin tek makineye sığmadığı noktayı bir satır sayısı olarak yazdı: seçilen kararla 23.173.893 satır. O noktadan sonra hesap bölünmek zorundadır, ama “bölünmek” tek başına bir tarif değildir. Bölünen şey nedir, parçalar arasında ne gider ve kaç kayıt gider.

Bu ders dağıtık hesaplamanın en yalın soyutlamasını kurar ve koşturur. Soyutlama üç işlevdir: eşle bir satırı bir anahtar ile bir ara değere çevirir, karışım geçişi ara değerleri anahtara göre indirgeyicilere taşır, indirge aynı anahtarın ara değerlerini tek bir değere kapatır. Dersin ölçüsü orta adımdadır: karışım geçişinde kaç kayıt taşınıyor. Yanında duran ikinci sayı, o kaydı taşımadan önce indirgemenin ne kadarının yapıldığıdır.

• OA7. Küme K03–K05’ten devralınır ve kurgudur: 3.199 satır, 1.329 abone, üç dönem, beş bölge, tarife basamakları 10/25/40 m³. Tohum 20260218 ve çıktı koşumdan koşuma aynıdır. Modeldir.
• OA8. Hiçbir dağıtık işleme motoru kurulmaz; kaynak sekiz parçaya yayılmış sayılır ve üç işlev standart kitaplıkla yazılır. Modeldir.
• OA9. Karışım geçişinde taşınan kayıt, indirgeyicilere gönderilen (anahtar, ara değer) çiftlerinin sayısıdır. Ham milisaniye ölçülmez.
• OA10. Ara değer bir karardır. Ortalama için ara değer tek bir sayı değil, (toplam, sayı) çiftidir; bu seçim indirge işlevini birleşmeli kılar.
• OA11. Bir hesabın modele girmesi, indirge işlevinin kısmi sonuçlar üzerinde birleşmeli ve değişmeli olmasına bağlıdır. Sınama koşularak yapılır: aynı hesap yedi ayrı parça sayısıyla koşulur ve kaç ayrı sayı çıktığı sayılır.
• OA12. Parça sınırı satır sayısına göre çekilir; parçalar kaynağın verdiği sıradadır.

Üç İşlev

# esle_indirge.py — bolgesel olcum aginin KURGU kumesi ve uc islev: esle,
# karisim gecisi, indirge. MODELDIR: hicbir dagitik motor kurulmaz; kaynak
# PARCA tane parcaya yayilmis sayilir ve karisim gecisinde tasinan kayit sayilir.
import math

TOHUM, HAM, M32, PARCA = 20260218, 1400, 0xFFFFFFFF, 8
BOLGE = [("kuzey", 0.28, 21), ("guney", 0.22, 17), ("dogu", 0.18, 26),
         ("bati", 0.14, 14), ("merkez", 0.18, 23)]


def uretec(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def sonraki():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return sonraki


def ayrik(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


def basamak(v):
    return "0-10" if v <= 10 else "10-25" if v <= 25 else "25-40" if v <= 40 else "40 ustu"


KUME = []
for i in range(HAM):
    r = uretec(TOHUM + i)
    b = BOLGE[ayrik(r(), [x[1] for x in BOLGE])]
    hane = 1 + ayrik(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05])
    memnun = 1 + ayrik(r(), [0.08, 0.14, 0.27, 0.34, 0.17])
    if r() < 0.046:                      # kayda girememis sayac
        continue
    no, q = 10001 + i, uretec(TOHUM + 7000 + 10001 + i)
    for d in range(ayrik(q(), [0.05, 0.12, 0.21, 0.62])):
        v = 0.0 if q() < 0.038 else math.floor(
            b[2] * math.exp((q() + q() + q() - 1.5) * 0.62)
            * (1 - d * 0.05) * 100 + 0.5) / 100
        KUME.append((no, b[0], d + 1, hane, memnun, v, basamak(v)))
        q()


def parcala(kume, p):
    n = len(kume)
    return [kume[i * n // p:(i + 1) * n // p] for i in range(p)]


def esle(satir, anahtar):
    return (anahtar(satir), (satir[5], 1))        # ara deger: (toplam, sayi)


def birlestir(a, b):
    return (a[0] + b[0], a[1] + b[1])


def kos(parcalar, anahtar, birlestirici):
    """Esle -> (varsa yerel indirge) -> karisim gecisi -> indirge.
    Donen ikinci sayi karisim gecisinde tasinan kayit sayisidir."""
    tasinan = []
    for p in parcalar:
        ciftler = [esle(s, anahtar) for s in p]
        if birlestirici:
            yerel = {}
            for k, v in ciftler:
                yerel[k] = birlestir(yerel[k], v) if k in yerel else v
            ciftler = sorted(yerel.items(), key=lambda x: str(x[0]))
        tasinan += ciftler
    kova = {}
    for k, v in tasinan:
        kova[k] = birlestir(kova[k], v) if k in kova else v
    return {k: (v[0] / v[1], v[1]) for k, v in kova.items()}, len(tasinan)


P = parcala(KUME, PARCA)
sonuc, tasinan = kos(P, lambda s: s[1], False)
print(f"tohum {TOHUM}; {len(KUME)} satir, {PARCA} kaynak parcasi "
      f"{[len(x) for x in P]}")
print(f"{'bolge':<10}{'satir':>7}{'ortalama m3':>14}")
for b in sorted(sonuc):
    print(f"{b:<10}{sonuc[b][1]:>7}{sonuc[b][0]:>14.3f}")
print(f"dogu - kuzey = {sonuc['dogu'][0] - sonuc['kuzey'][0]:.3f} m3; "
      f"karisim gecisinde tasinan kayit {tasinan}")

tohum 20260218; 3199 satir, 8 kaynak parcasi [399, 400, 400, 400, 400, 400, 400, 400]
bolge       satir   ortalama m3
bati          476        13.778
dogu          557        24.674
guney         645        16.602
kuzey         921        20.210
merkez        600        22.396
dogu - kuzey = 4.463 m3; karisim gecisinde tasinan kayit 3199

Küme sekiz parçaya yayıldı ve hiçbir yerde bütünüyle bir araya gelmedi, ama kursun çıpası değişmedi: doğu ortalaması 24,674 m³, kuzey 20,210 m³, fark 4,463 m³. Model doğru kurulduğunda bölünme cevabı oynatmaz; oynattığı şey cevabı üretmek için taşınan kayıttır.

Bu ilk koşumda taşınan kayıt 3.199, yani kümenin tamamı. Eşle her satır için bir çift üretti ve çiftlerin hepsi indirgeyicilere gitti. İndirge sonra çalıştı ve beş sayı verdi. Beş sayı için 3.199 kayıt taşındı.

Ara değerin ne olduğu bu noktada görünmez bir karardır. Eşle işlevi okumayı tek başına göndermiyor, yanına 1 sayısını koyup (toplam, sayı) çifti gönderiyor. Tek bir sayı gönderilse indirge işlevi ortalamaların ortalamasını almak zorunda kalırdı ve parça boyutları eşit olmadığı anda sonuç kayardı. Çift göndermek taşınan kaydı iki katına çıkarmaz — kayıt sayısı aynıdır, kaydın içi genişler — ama indirge işlevini birleşmeli kılar. Dersin üçüncü bölümü bu özelliğin olmadığı durumu ölçer.

Karışım Geçişinde Taşınan Kayıt

# tasima.py — ayni toplulastirma iki sirada kosulur: once karistirip sonra
# indirgeyen sira ve once yerel indirgeyip sonra karistiran sira. Olcu,
# karisim gecisinde tasinan kayit sayisidir.
ANAHTAR = (("bolge", lambda s: s[1]), ("bolge + donem", lambda s: (s[1], s[2])),
           ("bolge + basamak", lambda s: (s[1], s[6])),
           ("abone_no", lambda s: s[0]))
print(f"{'gruplama anahtari':<18}{'anahtar':>9}{'once karistir':>15}"
      f"{'once indirge':>14}{'kazanc':>9}{'sonuc ayni':>12}")
for ad, f in ANAHTAR:
    a, ta = kos(P, f, False)
    b, tb = kos(P, f, True)
    esit = all(abs(a[k][0] - b[k][0]) < 1e-9 for k in a)
    print(f"{ad:<18}{len(a):>9}{ta:>15}{tb:>14}{ta / tb:>8.2f}x"
          f"{('evet' if esit else 'hayir'):>12}")
print(f"birlestiricinin gonderdigi kayit, parca basina ayri anahtar sayisidir; "
      f"{PARCA} parca ve 5 bolge {PARCA * 5} kayit eder")

gruplama anahtari   anahtar  once karistir  once indirge   kazanc  sonuc ayni
bolge                     5           3199            40   79.97x        evet
bolge + donem            15           3199           120   26.66x        evet
bolge + basamak          18           3199           137   23.35x        evet
abone_no               1260           3199          1265    2.53x        evet
birlestiricinin gonderdigi kayit, parca basina ayri anahtar sayisidir; 8 parca ve 5 bolge 40 kayit eder

Sıra kararı sonucu oynatmıyor, taşımayı oynatıyor. Dört satırın hepsinde son sütun “evet” diyor: önce karıştırıp sonra indirgemekle önce yerel indirgeyip sonra karıştırmak aynı beş sayıyı veriyor. Değişen şey karışım geçişinden geçen kayıttır ve bölge anahtarında 3.199’dan 40’a iniyor — 79,97 kat.

Kırkın nereden geldiği tek satırlık bir çarpımdır: sekiz parça, her parçada beş bölge. Yerel indirgeme bir parçadaki bütün satırları o parçanın anahtar sayısına indirir; taşınan kayıt artık küme boyundan değil, parça sayısı ile parça içindeki ayrı anahtar sayısından gelir. Küme bin kat büyüse de bölge anahtarında taşınan kayıt kırk kalır.

Son satır sınırı çiziyor. Abone anahtarında 1.260 ayrı anahtar var ve satır sayısı 3.199; bir abonenin satırları en çok üç tane. Yerel indirgeme parça başına ortalama iki buçuk satırı bire indiriyor ve kazanç 2,53 kata düşüyor. Birleştiricinin kazancı anahtar sayısının satır sayısına oranından gelir; anahtar sayısı satır sayısına yaklaştıkça birleştirici taşıyacak bir şey bulamaz.

Ortadaki iki satır bu oranın nasıl işlediğini gösteriyor. Bölgeye dönem eklendiğinde anahtar sayısı beşten on beşe çıkıyor ve taşınan kayıt tam olarak sekiz çarpı on beş, yani 120 oluyor: on beş anahtarın hepsi sekiz parçanın hepsinde var. Basamak eklendiğinde anahtar sayısı on sekiz, ama taşınan kayıt 144 değil 137. Aradaki yedi kayıt eksikliği bir kazanç değil bir seyrekliktir: bölge ile basamağın on sekiz bileşiminden ikisi kümenin tamamında yalnız birkaç satır tutuyor ve sekiz parçanın yedisinde hiç görünmüyor. Taşınan kayıt, anahtar sayısının değil parça başına gerçekten görülen anahtar sayısının toplamıdır ve bu sayı ancak koşularak bilinir.

İki Geçiş ve Modele Girmeyen Hesap

# gecis.py — bazi hesap tek karisim gecisine sigmaz, bazisi hic sigmaz.
# Once iki gecisli hesap, sonra indirge islevinin birlesmeli olup olmadigi
# sinanir: ayni hesap yedi ayri parca sayisiyla kosulur.
import statistics

abone, t1 = kos(P, lambda s: s[0], True)                  # 1. gecis: anahtar abone
BOLGESI = {s[0]: s[1] for s in KUME}
ikinci = [(BOLGESI[k], (v[0], 1)) for k, v in abone.items()]
P2 = parcala(ikinci, PARCA)                               # 2. gecis: anahtar bolge
t2 = sum(len({k for k, _ in p}) for p in P2)
ort2 = {}
for p in P2:
    for k, v in p:
        ort2[k] = birlestir(ort2[k], v) if k in ort2 else v
tek, tt = kos(P, lambda s: s[1], True)
print(f"{'bolge':<10}{'tek gecis: satir agirlikli':>28}"
      f"{'iki gecis: abone ortalamasi':>29}{'fark':>8}")
for b in sorted(tek):
    a2 = ort2[b][0] / ort2[b][1]
    print(f"{b:<10}{tek[b][0]:>28.3f}{a2:>29.3f}{a2 - tek[b][0]:>8.3f}")
print(f"tek gecis {tt} kayit tasir; iki gecis {t1} + {t2} = {t1 + t2} kayit tasir")

ortancalar = []
print(f"{'parca':<8}{'toplam m3':>12}{'en buyuk':>10}"
      f"{'parca ortancalarinin ortancasi':>32}")
for p in (2, 3, 4, 5, 8, 16, 32):
    par = parcala(KUME, p)
    o = statistics.median([statistics.median([x[5] for x in y]) for y in par])
    ortancalar.append(o)
    print(f"{p:<8}{sum(sum(x[5] for x in y) for y in par):>12.2f}"
          f"{max(max(x[5] for x in y) for y in par):>10}{o:>32.4f}")
kova = sum(len({x[5] for x in p}) for p in P)
print(f"gercek ortanca {statistics.median([s[5] for s in KUME])} m3; yedi parca "
      f"sayisi {len(set(ortancalar))} ayri deger verir, acikligi "
      f"{max(ortancalar) - min(ortancalar):.4f} m3")
print(f"okumalar iki ondalikli: {len({s[5] for s in KUME})} ayri deger; sayim "
      f"birlestiricisi {kova} kayit tasir, kazanc {len(KUME) / kova:.2f}x")

bolge       tek gecis: satir agirlikli  iki gecis: abone ortalamasi    fark
bati                            13.778                       13.935   0.158
dogu                            24.674                       24.814   0.140
guney                           16.602                       16.728   0.127
kuzey                           20.210                       20.351   0.141
merkez                          22.396                       22.483   0.087
tek gecis 40 kayit tasir; iki gecis 1265 + 40 = 1305 kayit tasir
parca      toplam m3  en buyuk  parca ortancalarinin ortancasi
2           63060.63     52.47                         18.9900
3           63060.63     52.47                         18.9700
4           63060.63     52.47                         18.9250
5           63060.63     52.47                         18.8400
8           63060.63     52.47                         18.9725
16          63060.63     52.47                         18.8900
32          63060.63     52.47                         19.0575
gercek ortanca 18.98 m3; yedi parca sayisi 7 ayri deger verir, acikligi 0.2175 m3
okumalar iki ondalikli: 1788 ayri deger; sayim birlestiricisi 2839 kayit tasir, kazanc 1.13x

İlk tablo bu dersin gizlenen kararıdır. “Bölge ortalaması” tek bir soru gibi durur, oysa iki ayrı hesaptır. Tek geçişte anahtar bölgedir ve her satır eşit ağırlık taşır: doğu 24,674 m³. İki geçişte önce abone anahtarıyla indirgenir, sonra abone sonuçları bölge anahtarıyla indirgenir ve her abone eşit ağırlık taşır: doğu 24,814 m³. Fark 0,140 m³ ve beş bölgenin hepsinde aynı yönde. İkisi de savunulabilir; hangisinin seçildiği yazılmadığında rapordaki sayı bir bulgu değil bir seçimdir.

Bedel de tabloda. Tek geçiş 40 kayıt taşır, iki geçiş 1.265 artı 40, toplam 1.305 kayıt — otuz iki kat. Geçiş sayısı arttıkça taşınan kayıt katlanır, çünkü ara geçişin çıktısı bir sonraki geçişin girdisi olur ve o çıktı anahtar sayısı kadar büyüktür.

İkinci tablo modele girmenin sınırını çiziyor. Toplam ve en büyük yedi ayrı parça sayısında da kılını kıpırdatmıyor: 63.060,63 m³ ve 52,47 m³. İndirge işlevleri kısmi sonuçlar üzerinde birleşmeli ve değişmelidir, dolayısıyla parçalama görünmez kalır. Ortanca ise yedi parça sayısında yedi ayrı değer veriyor; açıklık 0,2175 m³ ve hiçbiri gerçek ortancaya, 18,98 m³’e eşit değil. Parça ortancalarının ortancası bir yaklaşıklık bile değildir; parça sayısına bağlı bir sayıdır.

Son satır çıkış yolunun bedelini veriyor. Ortanca ara değeri ortanca yerine bir sayım olduğunda modele girer, ama bu kümede kurtarmaz: okumalar iki ondalıkla yazıldığı için 1.788 ayrı değer var ve sayım birleştiricisi 2.839 kayıt taşıyor, yani kazanç 1,13 kat. Ondalık sayısı bir gösterim kararıdır ve burada karışım geçişinin boyunu belirliyor: bir ondalıkla yazılan aynı okumalar birleştiriciyi çalışır kılardı.

Özet

• Üç işlev koştu ve küme sekiz parçaya yayıldığı halde çıpa değişmedi: doğu 24,674 m³, kuzey 20,210 m³, fark 4,463 m³.
• Sıra kararı sonucu değil taşımayı oynatır: bölge anahtarında önce karıştırmak 3.199, önce yerel indirgemek 40 kayıt taşır ve kazanç 79,97 kattır.
• Birleştiricinin taşıdığı kayıt parça sayısı ile parça içindeki ayrı anahtar sayısının çarpımıdır; abone anahtarında 1.260 anahtar kazancı 2,53 kata indirir.
• Aynı soru iki anahtarla iki değer verir: doğu ortalaması satır ağırlıklı 24,674 m³, abone ortalamalarının ortalaması olarak 24,814 m³’tür ve iki geçiş 40 yerine 1.305 kayıt taşır.
• Bir hesap indirge işlevi birleşmeli değilse modele girmez: toplam ve en büyük yedi parça sayısında da aynı çıkar, parça ortancalarının ortancası yedi ayrı değer verir ve açıklığı 0,2175 m³’tür.
• Ortanca ara değeri sayıma çevrildiğinde modele girer ama iki ondalıklı okumalarda 1.788 ayrı değer bulunur ve kazanç 1,13 kata düşer.

Sonraki Adım

Bu ders taşınan kaydı saydı ve taşımanın sıraya bağlı olduğunu gösterdi, ama üç işlevi kimin koşturduğunu hiç sormadı. Gerçek bir işte parçalar bir yerde tanımlanır, görevler dağıtılır, başarısız görev yeniden denenir ve sonuçlar toplanır; bunların hiçbiri satır işlemez ve hepsi iş başına eklenir. Sonraki ders küme üzerinde veri çerçevesi işlemenin eşgüdüm kalemini sayar: bir işlem zinciri kaç aşamaya bölünüyor, aşama başına kaç kalem ekleniyor, yeniden deneme bu sayıyı kaça çıkarıyor ve hangi iş boyutunda kalem sayısı işlenen satır sayısını geçiyor.