Ders 12 / 23
İki Yığın
Akan veride ortanca izleme; denge adımı kaldırıldığında 480 ortancanın 295'inin bozulması ve kalıbın kazancının akış uzadıkça büyümesi.
İçindekiler
Önceki beş kalıp girdinin tamamını elinde tuttu: dizi baştan sona görülebiliyor, istenen konuma dönülebiliyordu. Bu dersin kalıbı o olanağı kaybeder. Değerler tek tek akar ve her yeni değerden sonra bir soru yanıtlanmalıdır: o ana kadar görülenlerin ortancası nedir.
Ortancayı bulmanın doğrudan yolu sıralı bir liste tutmaktır; her yeni değer doğru yere sokulur ve ortadaki okunur. Kalıp bunun yerine iki yığın tutar: küçük yarı bir en büyük yığında, büyük yarı bir en küçük yığında. Ortanca, iki yığının tepesinden okunur. Yığın koşulu, süzme işlemleri ve dizi gösterimi Veri Yapıları kursunun Yığınlar dersinde kuruldu; burada tekrarlanmaz, doğrudan kullanılır.
Kalıbın ön koşulu iki yığının dengede kalmasıdır. Bu ders dengeyi bozup kaç ortancanın yanlış çıktığını sayar.
Kalıp ve Denge Ön koşulu
Her yeni değer önce yerine konur: küçük yarının tepesinden büyük değilse en büyük yığına, değilse en küçük yığına. Bu tek başına yetmez, çünkü değerler bir yana yığılabilir. İkinci adım denge adımıdır: yığınların boyu birden fazla ayrıldığında büyük olanın tepesi öbürüne aktarılır.
Ortanca ancak iki yığının boyu doğruyken okunabilir. Toplam tek sayıdaysa büyük olan yığının tepesi ortancadır; çift sayıdaysa iki tepenin ortalaması. Denge bozuksa bu iki kural da yanlış yeri gösterir — kalıp yine bir sayı döndürür.
PK40. Dağarcık 40 akıştır; her akış 12 değer taşır ve değerler −9 ile 20 arasındadır.
Tohum 20260218. Her akışta her değerden sonra bir ortanca sorulur; toplam 480 soru.
PK41. Kâhin her değeri doğrusal tarama ile sıralı listeye sokar ve ortadakini okur.
Her karşılaştırma bir adım sayılır.
PK42. Kalıbın adımı, yığın işlemlerinin yaptığı gerçek karşılaştırmalardır; değerler
karşılaştırmayı sayan bir sarmalayıcıya konur, adım tahmin edilmez.
PK43. Ön koşulu bozan tek şey denge adımının kaldırılmasıdır. Değer yerleştirme
kuralı, ortanca okuma kuralı, dağarcık ve tohum aynıdır.
import heapq 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 akis_dagarcik(tohum=TOHUM, n=DAGARCIK, uzunluk=UZUNLUK): r = uretec(tohum) return [{"no": i + 1, "akis": [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 class Olcu: """Yiginin her karsilastirmasini sayan sarmalayici. yon=-1 en buyuk yigin verir.""" __slots__ = ("d", "yon", "s") def __init__(self, d, yon, s): self.d, self.yon, self.s = d, yon, s def __lt__(self, o): self.s.say() return self.d * self.yon < o.d * o.yon def kahin_ortanca(akis, s): """Her degeri dogrusal tarama ile sirali listeye sokar, ortadakini okur.""" sirali, yanit = [], [] for x in akis: i = 0 while i < len(sirali): s.say() if sirali[i] >= x: break i += 1 sirali.insert(i, x) n = len(sirali) yanit.append(sirali[n // 2] if n % 2 else (sirali[n // 2 - 1] + sirali[n // 2]) / 2) return yanit def kalip_iki_yigin(akis, dengele, s): """ONKOSUL: iki yigin dengede kalmali. alt en buyuk yigin, ust en kucuk yigin.""" alt, ust, yanit = [], [], [] en_buyuk_fark = 0 for x in akis: if not alt or x <= alt[0].d: heapq.heappush(alt, Olcu(x, -1, s)) else: heapq.heappush(ust, Olcu(x, 1, s)) if dengele: if len(alt) > len(ust) + 1: heapq.heappush(ust, Olcu(heapq.heappop(alt).d, 1, s)) elif len(ust) > len(alt): heapq.heappush(alt, Olcu(heapq.heappop(ust).d, -1, s)) en_buyuk_fark = max(en_buyuk_fark, abs(len(alt) - len(ust))) if not alt: yanit.append(ust[0].d) elif not ust or len(alt) > len(ust): yanit.append(alt[0].d) elif len(ust) > len(alt): yanit.append(ust[0].d) else: yanit.append((alt[0].d + ust[0].d) / 2) return yanit, en_buyuk_fark K = akis_dagarcik() print("dagarcik:", len(K), "akis x", UZUNLUK, "deger =", len(K) * UZUNLUK, "ortanca") print("kurulum yanlis ortanca ayrilan akis/40 kalip kahin oran en buyuk fark") for ad, dengele in (("dengeli ", True), ("dengesiz ", False)): yanlis, ayrilan, ak, ah, fark = 0, 0, 0, 0, 0 for k in K: s1, s2 = Sayac(), Sayac() a, f = kalip_iki_yigin(k["akis"], dengele, s1) b = kahin_ortanca(k["akis"], s2) ak, ah = ak + s1.adim, ah + s2.adim fark = max(fark, f) bozuk = sum(1 for x, y in zip(a, b) if x != y) yanlis += bozuk ayrilan += bozuk > 0 print(f"{ad} {yanlis:14d} {ayrilan:15d} {ak:5d} {ah:5d} {ah / ak:5.2f}" f" {fark:13d}")
dagarcik: 40 akis x 12 deger = 480 ortanca kurulum yanlis ortanca ayrilan akis/40 kalip kahin oran en buyuk fark dengeli 0 0 1261 1693 1.34 1 dengesiz 295 39 550 1693 3.08 12
Dengeli kurulumda 480 ortancanın 480’i kâhinle aynı; en büyük boy farkı 1, yani denge hiç bozulmuyor. Denge adımı kaldırıldığında 295 ortanca yanlış çıkıyor ve 40 akışın 39’u bozuluyor.
İkinci satırın adım sütunu dersin ana çelişkisini taşıyor: dengesiz kalıp 550 adım harcıyor, dengelinin yarısından az. Denge adımı, kalıbın toplam işinin büyük bölümünü oluşturuyor; onu kaldırmak kalıbı kâhine göre 1,34 kattan 3,08 kata hızlandırıyor. En hızlı kurulum yine en bozuk kurulumdur. En büyük boy farkı da 1’den 12’ye çıkıyor: bütün değerler tek bir yığında birikiyor.
Dengesizlik Nasıl Yanlış Ortanca Üretiyor
Denge adımı olmadan yerleştirme kuralı kendi kendini besler. Küçük bir değer geldiğinde küçük yarıya konur; küçük yarının tepesi daha da küçülmez, ama yarı büyür. Bir sonraki değer o büyümüş yarının tepesiyle karşılaştırılır ve çoğunlukla yine oraya düşer. Bir yığın şişerken öbürü boş kalır ve ortanca okuma kuralı sürekli aynı tepeye bakar.
import heapq def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def akis_dagarcik(tohum, n=40, uzunluk=12): r = uretec(tohum) return [[r(30) - 9 for _ in range(uzunluk)] for _ in range(n)] def kahin_ortanca(akis): sirali, yanit = [], [] for x in akis: i = 0 while i < len(sirali) and sirali[i] < x: i += 1 sirali.insert(i, x) n = len(sirali) yanit.append(sirali[n // 2] if n % 2 else (sirali[n // 2 - 1] + sirali[n // 2]) / 2) return yanit def kalip_iki_yigin(akis, dengele): """alt en buyuk yigin (isaret ters cevrilerek), ust en kucuk yigin.""" alt, ust, yanit = [], [], [] for x in akis: if not alt or x <= -alt[0]: heapq.heappush(alt, -x) else: heapq.heappush(ust, x) if dengele: if len(alt) > len(ust) + 1: heapq.heappush(ust, -heapq.heappop(alt)) elif len(ust) > len(alt): heapq.heappush(alt, -heapq.heappop(ust)) if not alt: yanit.append(ust[0]) elif not ust or len(alt) > len(ust): yanit.append(-alt[0]) elif len(ust) > len(alt): yanit.append(ust[0]) else: yanit.append((-alt[0] + ust[0]) / 2) return yanit ilk = akis_dagarcik(20260218)[0] print("akis 1 :", ilk) print(" kahin :", kahin_ortanca(ilk)) print(" dengeli :", kalip_iki_yigin(ilk, True)) print(" dengesiz :", kalip_iki_yigin(ilk, False)) print() print("tohum kurulum yanlis ortanca/480 ayrilan akis/40 ilk yanlis konum") for tohum in (20260218, 20260219): K = akis_dagarcik(tohum) for ad, dengele in (("dengeli ", True), ("dengesiz", False)): yanlis, ayrilan, ilk_konum = 0, 0, [] for akis in K: a, b = kalip_iki_yigin(akis, dengele), kahin_ortanca(akis) bozuk = [i + 1 for i, (x, y) in enumerate(zip(a, b)) if x != y] yanlis += len(bozuk) ayrilan += bool(bozuk) if bozuk: ilk_konum.append(bozuk[0]) ortalama = round(sum(ilk_konum) / len(ilk_konum), 2) if ilk_konum else 0 print(f"{tohum} {ad} {yanlis:18d} {ayrilan:15d} {ortalama:16}")
akis 1 : [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1] kahin : [-8, -6.5, -5, -3.0, -1, 0.5, 2, 1.5, 2, 2.0, 2, 2.0] dengeli : [-8, -6.5, -5, -3.0, -1, 0.5, 2, 1.5, 2, 2.0, 2, 2.0] dengesiz : [-8, -6.5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5] tohum kurulum yanlis ortanca/480 ayrilan akis/40 ilk yanlis konum 20260218 dengeli 0 0 0 20260218 dengesiz 295 39 3.44 20260219 dengeli 0 0 0 20260219 dengesiz 268 38 3.89
Birinci akışın izi, mekanizmayı tek satırda gösteriyor. Dengeli kurulum kâhinin bütün yanıtlarını üretiyor. Dengesiz kurulum ilk üç ortancayı doğru veriyor, sonra −5’te kilitleniyor ve akışın sonuna kadar aynı sayıyı yazıyor. Değerler 16 ve 17’ye çıksa bile yanıt değişmiyor, çünkü bütün büyük değerler tek bir yığında birikmiş ve okunan tepe hep aynı kalmış.
PK44. İkinci dağarcık 20260219 tohumundan gelir. Yanlış ortanca 268/480,
birincide 295/480; ayrılan akış 38/40 ve 39/40. Oranlar 0,56 ile 0,61
arasında, aynı büyüklük düzeninde — sonuç dağarcığa bağlı değildir.
PK45. İlk yanlış ortanca ortalama 3,44’üncü değerde çıkıyor. Denge en geç dördüncü
değerde bozuluyor, yani kusur akışın sonunda değil başında oluşuyor.
Bu son sayı, kusurun neden gözden kaçmadığından çok neden kaçtığını açıklar. İlk üç yanıt doğrudur; kısa bir sınama akışı bu üç yanıta bakıp geçerse hiçbir şey görmez. Kusur yalnız akış uzadıkça birikir ve tek bir yanlış ortanca da çıktıya bakarak seçilemez — dengesiz kalıp yine akla yatkın bir sayı döndürüyor.
Kalıbın Kazancı Akış Uzadıkça Büyüyor
On iki değerlik akışta dengeli kalıbın oranı 1,34. Bu, kalıbı kurmaya değmeyecek kadar küçük bir kazançtır ve bir soru doğurur: iki yığın niçin var. Yanıt akış uzunluğundadır. Kâhinin her eklemesi listenin yarısını tarar, yani maliyeti o ana kadarki değer sayısıyla doğru orantılıdır; yığın eklemesi ise yığının derinliği kadar karşılaştırma yapar.
PK46. Bu ölçümde akış sayısı 10’a indirilir ve akış uzunluğu 12’den 200’e çıkarılır. Dağarcık aynı üreteçten, aynı tohumla gelir; değişen tek şey uzunluktur.
import heapq def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def akis_dagarcik(tohum, n, uzunluk): r = uretec(tohum) return [[r(30) - 9 for _ in range(uzunluk)] for _ in range(n)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 class Olcu: """Yiginin her karsilastirmasini sayar. yon=-1 en buyuk yigin verir.""" __slots__ = ("d", "yon", "s") def __init__(self, d, yon, s): self.d, self.yon, self.s = d, yon, s def __lt__(self, o): self.s.say() return self.d * self.yon < o.d * o.yon def kahin_ortanca(akis, s): sirali, yanit = [], [] for x in akis: i = 0 while i < len(sirali): s.say() if sirali[i] >= x: break i += 1 sirali.insert(i, x) n = len(sirali) yanit.append(sirali[n // 2] if n % 2 else (sirali[n // 2 - 1] + sirali[n // 2]) / 2) return yanit def kalip_iki_yigin(akis, s): alt, ust, yanit = [], [], [] for x in akis: if not alt or x <= alt[0].d: heapq.heappush(alt, Olcu(x, -1, s)) else: heapq.heappush(ust, Olcu(x, 1, s)) if len(alt) > len(ust) + 1: heapq.heappush(ust, Olcu(heapq.heappop(alt).d, 1, s)) elif len(ust) > len(alt): heapq.heappush(alt, Olcu(heapq.heappop(ust).d, -1, s)) yanit.append(alt[0].d if len(alt) > len(ust) else (alt[0].d + ust[0].d) / 2) return yanit print("akis uzunlugu ayrilan akis/10 kalip kahin oran") for uzunluk in (12, 25, 50, 100, 200): K = akis_dagarcik(20260218, 10, uzunluk) ayrilan, ak, ah = 0, 0, 0 for akis in K: s1, s2 = Sayac(), Sayac() a = kalip_iki_yigin(akis, s1) b = kahin_ortanca(akis, s2) ak, ah = ak + s1.adim, ah + s2.adim ayrilan += (a != b) print(f"{uzunluk:13d} {ayrilan:15d} {ak:5d} {ah:6d} {ah / ak:6.2f}")
akis uzunlugu ayrilan akis/10 kalip kahin oran
12 0 303 431 1.42
25 0 949 1602 1.69
50 0 2471 6440 2.61
100 0 5971 25292 4.24
200 0 13686 98651 7.21
Ayrılan akış beş uzunlukta da sıfır: denge korunduğu sürece kalıp uzunluktan bağımsız olarak doğrudur. Oran ise 1,42’den 7,21’e çıkıyor. Kâhinin adımı 431’den 98.651’e, yani 229 kat artarken kalıbın adımı 303’ten 13.686’ya, 45 kat artıyor.
Kalıbı kurmanın gerekçesi bu sütundur. On iki değerlik bir akışta iki yığın tutmak gereksizdir; iki yüz değerlik bir akışta yedi kat, daha uzun akışlarda daha çok kazandırır. Bir kalıbın kazancı bir sayı değil, bir eğilimdir ve tek bir girdi büyüklüğünde ölçülürse yanlış okunur.
Üç Sayı
| Ölçüt | Kâhin | Kalıp | Ayrılan girdi |
|---|---|---|---|
| Dengeli, 12 değerlik akış | 1693 adım | 1261 adım | 0/480 ortanca |
| Dengesiz, 12 değerlik akış | 1693 adım | 550 adım | 295/480 ortanca |
| Dengeli, 200 değerlik akış | 98.651 adım | 13.686 adım | 0/10 akış |
Birinci ve ikinci satır arasındaki tek fark iki satırlık bir denge adımıdır; o iki satır kalıbın adımının yarısından fazlasını harcar ve 295 yanlış yanıtı önler. Üçüncü satır, o bedelin neden ödendiğini gösterir.
Tablonun ayrılan girdi sütununda iki ayrı birim durduğuna dikkat edilmelidir. İlk iki satırda birim ortancadır, çünkü akan veride her değer bir soru üretir ve ölçülmesi gereken şey kaç sorunun yanlış yanıtlandığıdır. Üçüncü satırda birim akıştır, çünkü orada sorulan şey kalıbın uzunlukla bozulup bozulmadığıdır. İki birimi karıştırmak oranları karşılaştırılamaz kılar: 295/480 ile 0/10 aynı ölçekte okunamaz. Akan veri ölçen her kalıpta bu ayrım açıkça yazılmalıdır.
Özet
- İki yığın kalıbı akan veride ortancayı, küçük yarıyı en büyük yığında ve büyük yarıyı en küçük yığında tutarak iki tepe okumasıyla verir.
- Ön koşul iki yığının dengede kalmasıdır; denge adımı kaldırıldığında 480 ortancanın 295’i yanlış çıkıyor ve 40 akışın 39’u bozuluyor.
- Denge adımı kalıbın adımının yarısından fazlasını harcar: onsuz kalıp 1261 yerine 550 adım harcıyor ve oran 1,34’ten 3,08’e çıkıyor.
- İlk yanlış ortanca ortalama 3,44’üncü değerde çıkıyor; kusur akışın başında oluşur ama ilk birkaç yanıt doğru olduğu için kısa bir sınamada görünmez.
- Kalıbın kazancı akış uzunluğuyla büyür: oran 12 değerde 1,42, 200 değerde 7,21 ve ayrılan akış her uzunlukta sıfırdır.
Sonraki Adım
İki yığın, ortancayı yani sıralı düzende ortadaki değeri verdi. Ortanca özel bir durumdur; genel soru, sıralı düzende k’ıncı değerin ne olduğudur. Sonraki ders bu soruyu iki ayrı kalıpla yanıtlar — k boyutlu bir yığınla ve bölümlemeyle — ve ikisini de aynı kâhinle sınar. Orada ön koşul veriye değil sorunun kendisine dokunur: tekrarlı değerlerde “k’ıncı eleman” ile “k’ıncı ayrı değer” aynı şey değildir ve aradaki fark sayılacaktır.
İlerlemeni kaydetmek ve not almak için Giriş yap
Notlarım
Not almak için giriş yapmalısın.