MIT Açık Ders malzemeleri

http://ocw.mit.edu

6.046J Algoritmalara Giriş, Güz 2005

Bu materyallerden alıntı yapmak veya kullanım şartları hakkında bilgi almak için:

Erik Demaine ve Charles Leiserson, 6.046J IntroductiontoAlgorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi: 08, 01, 2010). Lisans: Creative CommonsAttribution-Noncommercial-ShareAlike.

Not: Lütfen atıf taparken bilgilere eriştiğiniz gerçek tarihi kullanınız.

Atıflar ve Kullanım Koşulları konusunda daha fazla bilgi için:

http://ocw.mit.edu/terms ve http://www.acikders.org.tr sitesini ziyaret ediniz.

DERS 25

6.046 kodlu son dersimiz. Bugün burada, önbelleği dikkate almayan algoritmalar hakkında biraz daha konuşmak için bir arada bulunuyoruz. Son derste, hiçbiri fazla zor olmayan, önbelleği göz ardı eden birkaç algoritma görmüştük. Bugün ise, önbelleği göz ardı eden, ama daha ileri düzeyde, iki tane daha zor algoritma göreceğiz. Heyecan verici bir hava yaratmak için, son dersimizde ileri seviyede bir şeyler yapmayı tasarladım Daha fazla dağıtmadan, konumuza başlayalım. Son olarak, ikili arama problemini görmüştük.

Daha doğrusu görmedik, ikili aramayı seyrettik. İkili arama, önbelleği dikkate almadığımız durumda iyi netice vermedi. Dersten sonra bazılarınız “ikili aramanın, önbelleği dikkate almayan şeklinin kurulması mümkün değil mi”, diye sordular. Gerçekten, statik arama ağaçları ile bu mümkündür. Bu da gerçekten ikili arama oluyor. Soyut açıdan, bu problemi şu şekilde ifade etmek mümkün: size, önceden sıralanmış N sayıda öğe veriyorum, bu N öğenin arasında hızlı arama yapabilmeniz için, belli bir statik veri yapısı oluşturuyorum.

Çabuk olmanın, B tabanında log (N) olduğunu ileri sürüyorum. B ağaçları ile hedefimizin, B tabanında log (N) elde etmek olduğunu biliyoruz. B’ yi bildiğimizde, B ağaçları ile bunu başarabileceğimizi de biliyoruz. Şimdi aynı şeyi, B’yi bilmeden de yapmak istiyoruz. İşte önbelleği dikkate almayan statik arama ağaçları bunu başarıyor. Özetle, yapacağımız şu: tahmin ettiğiniz gibi bir ağaç kullanacağız. Yani N elemanımızı, bir ikili ağacın bütününe depolayacağız. B’yi bilmediğimiz için, B ağaçlarını kullanamayız. Böylece onun yerine ikili ağaç kullanacağız. Buradaki anahtar nokta, ikili bir ağacı nasıl düzenleyeceğimiz. İkili ağacın N sayıda düğümü olacak Ya da, verileri yaprakların içine de koyabilirsiniz. Fark etmez.

İşte ağacımız burada. N düğümü var. Ve bunları depoluyoruz, fark ettiğiniz gibi sırasıyla dememişim, normalde bir ikili ağaçta, sırayla depolanırlarsa o ağaç ikili bir arama ağacı olur. Şimdi, bu şeyin içinde bir arama yapacaktık. Arama kökte başlayacak ve bir kök -yaprak yolundan devam edecek. Böylece her şey düzen içinde olduğundan, her noktada sağa mı, sola mı gideceğinizi biliyorsunuz. Yani başka bir deyimle, anahtarların sıralı evrenine sahip olduğumuzu varsayıyoruz.

Öyleyse kolay. Log N zaman süreceğini biliyoruz. Soru, ne kadar bellek transferi gerekeceği.. Çok sayıda düğümün, köke ve birbirlerine yakın olmalarını ve bir de blok bulunmasını istiyoruz. Fakat bu bloğun boyutunun ne olduğunu bilmiyoruz. Yapacağımız, ağacı orta düzeyinde oymak. Ağaç yerleşim planında ve düğümleri bellekte düzenlemede ‘böl-ve-fethet’ i kullanacağız. ‘ Böl-ve-fethet’, ortadan keserek ikiye bölmek esasına dayanıyor ki, biraz acayip.

Bildiğimiz klasik ‘böl-ve-fethet’ değil. Olmadığını bugün birkaç kere göreceğiz. Böylece, orta düzeyde kestiğiniz zaman, eğer en başlangıçtaki ağacınızın yüksekliği, log N, belki de kabaca log N artı bir veya bu ölçeklerde ise, yaklaşık olarak log N ‘dir, bu takdirde ağacın yukarı yarısı, log N bölü iki olacaktır. Aynı şekilde, alt yarımın yüksekliği de, log N bölü iki demektir. Üst ağaçta kaç tane düğüm var? N bölü iki mi ? Pek değil. İki üzeri log N/2, N’nin karekökü. Demek ki, burada karekök N düğüm var. Bu nedenle burada altta da, her yaprak veya bir çift yaprak için, karekök N tane alt ağaç olacak.

Yani, karekök N tane bu alt ağaçlardan var ve bunlar yaklaşık olarak karekök N sayıda. Pekiyi bu şekilde oyuyoruz. Şimdi, her bir parça üzerinde özyineleme yapacağız. Bunun bazı yerlerini yeniden çizmek istiyorum; af edersiniz, sadece biraz daha belirgin kılmak için. Bu üçgenler, gerçek ağaçlar ve kenarlardan hepsi bu yukarıdaki ağaca bağlılar. Böylece asıl yaptığımız ağacın içinde kenarların orta düzeyini oymaktan ibaret. Ve eğer N, ikinin tam bir kuvveti değil ise, taban veya tavanı alarak bulunduğunuz düzeyi yuvarlamalısınız. Ancak, kenarların kabaca orta düzeyinde kesiyorsunuz. Burada pek çok kenar var. Burasını, planınıza göre kesiyorsunuz. Bu size, her biri yaklaşık olarak karekök N boyutunda olan, bir tane üst ve birkaç tane alt-ağaç veriyor.

Pekala, bundan sonra her biri karekök N artı 1 boyutunda olan bu alt-ağaçları, özyinelemeli şekilde düzenliyor, sonra da ardı ardına birbirine bağlıyoruz. Bu özyinelemeli yerleşim düzeni fikridir. Son derste matrislerde özyinelemeli düzeni araştırmıştık. Burada aynı şeyi bir ağaç için yapıyoruz. Böylece, önce ağacın en üst kısmını özyinelemeli olarak düzenlemek istiyorum. İşte üst ağaç ve bunun doğrusal bir dizilim içine özyinelemeli olarak sıkıştırılmış olduğunu hayal ediyorum. Sonra, aynı şeyi ağacın alt kısmındaki parçaların her biri için yapıyorum. İşte, alttaki ağaçlar. Bunların herbirini belli bir doğrusal düzenin içine sıkıştırdım. Ve sonra bu doğrusal düzenleri ardı ardına bağlıyorum. Bu ağacın doğrusal düzeni budur.

Ve bir taban durumuna ihtiyacınız var. Tek bir düğümden oluşan bu taban durumu, tek düğüm düzeyinin olduğu yerde depolu. Pekala, bu özyinelemeli bir ikili arama ağacının yerleşim düzenidir . Bu gerçekten iyi çalışır. Bu düzenimin ne olduğunu tamamen anlaşılır kılmak için, şimdi hemen küçük bir örnek yapalım, çünkü ilk defa görüyorsanız biraz alışılmışın dışındadır. Her zamanki favori resmimi çizeyim.

Şimdi, burada, ne şekilde saydığınıza bağlı, dört veya üç yüksekliğinde bir ağaç var. Orta seviyesinden ikiye bölüyoruz, tamam, işte buna üst ağaç diyoruz.Bunlar da alt-ağaçlar. Böylece, dört tane alt-ağaç var. Yani, ağacın kökünden sarkan dört çocuk var. Bu örnekte her biri aynı boyutta. Hepsinin aşağı yukarı aynı boyutta olmaları gerekir. Burada önce orta seviyede ikiye böldüğümüz en yukarıdaki parçayı düzenliyoruz. Pekiyi önce bu geliyor. Ve sonra alttaki alt-ağaçlar, iki ve üç. Böylece bir dizilimde depolanmış düğümlerin düzenini yazıyorum. Ve sonra bu ağacı ziyaret ediyoruz, böylece dört, beş, altıyı elde ediyoruz. Sonra bunu ziyaret ediyoruz ve böylece yedi,sekiz, dokuzu elde ediyoruz.

Ondan sonra bu alt-ağaç 10,11,12 ve sonra da en sondaki alt-ağaç. Bu15 düğümü içinde depolayacağınız düzene karşılık geliyor. Ve bunu özyinelemeli olarak kurabilirsiniz. Böylece, gördüğünüz gibi yapı oldukça basit; bildiğimiz ve sevdiğimiz bir ikili yapı ama öğeler bu komik biçimde depolanmış. Bu, derinliğine arama düzeni veya düzey düzeni değil; pek çok şey deneyebilirsiniz, ama önbelleği dikkate almadığınız takdirde bunların hiçbirisi çalışmaz.

Bu, çalışan tek yoldur. Aynı husus sezgi için de geçerli, aslında sezgiyle her çeşit B ağacını taklide çalışıyoruz. Yani eğer ikili ağaç isterseniz orijinal ağaç budur. Elinizdeki şeyleri nasıl depolayacağınızın önemi yok. Dallanma faktörü dört olan bir ağaç isterseniz, işte burada. Bu bloklar size dallanma faktörü dördü verir. Aşağıda daha fazla yaprağımız olsa idi, o düğümden sarkan dört çocuk daha olurdu. Bunların hepsi bellek içinde birbiri peşine gruplanmış durumdalar. Ve blok boyutunuz üç olursa, bu yapı blok boyutu üç için eldeki şeyleri depolamak bakımından kusursuz olacaktır.

Eğer blok boyutunuz 7, yada daha fazla,15 olursa -- eğer sağdaki sayıları sayarsak buradaki düğümlerin sayısı 15-- eğer blok boyutunuz 15 olursa bu özyineleme,15 cinsinden size mükemmel bir bloklama olanağı verecektir. Genelde olay, aslında , bloğu taklitten ibaret. İkinin ikinci kuvvetinin kuvveti gibi düşünün. Tamam, bu sezgiydi. Daha açık kılmak için size resmi çözümlemeyi vereyim. Özetle, B tabanında log (N) düzeyinde bellek transferi olduğunu iddia ediyoruz. B’nin herhangi bir değerinde bu iddianın doğru olduğunu ispatlamak istiyoruz. Şimdi yapacağımız şu. Böl-ve-fethet algoritmasını en son çözümlediğimizde, özyinelemeyi yazmıştık ve taban durumu işin anahtarıydı.

Gerçekten, burada da, belli bir anlamda, taban durumu üzerinde düşüneceğiz. Aslında, algoritmamızda özyineleme yok. Algoritma, belli bir kök-yaprak yolu üzerinde zaten çözülüyor. Sadece, yerleşimin tanımında bir yinelememiz var. O halde, biraz daha esnek olabiliriz. Yinelemeye bakmamız gerekmiyor. Sadece taban şıkkı üzerinde düşüneceğiz. Büyük üçgenle başladığınızı hayal etmenizi istiyorum. Ortadan kesiyor, daha küçük üçgenler elde ediyorsunuz. Özyinelemeli olarak kesmeye devam ettiğiniz noktayı hayal edin.

Şimdi, bu işlemi hayal edin. Büyük üçgenler her defasında,yükseklikleri bağlamında yarıya iniyorlar. Küçüldükçe küçülüyorlar. Bir üçgenin bir bloğa sığdığı noktada, kesme işlemini durdurun ve o andaki duruma bakın. Aslında özyineleme sonuna kadar devam ediyor, ancak analizinde, parçanın bu üçgenlerden birinin içindeki bloklardan birine, daha doğrusu, bloklardan birinin içine sığan bu kutulardan birine sığmış olduğu noktayı düşünelim. İşte bu noktanın bulunduğu düzeyi bir özyineleme düzeyi olarak adlandırıyorum.

Böylece, özyinelemelerin hepsinin birbirlerine paralel şekilde genişlediğini hayal ediyorum. Ağaçları biraz daha detayladık böylece -- baktığınız ağacın, bu ağaç içinde üçgenler olduğunu ve bunların boyutu B’ye küçük – eşit .. Pekala, şimdi bir resim çizeyim. Şöyle bir resim çizmek istiyorum. Bu resimde düğümler yerine, küçük üçgenler var ve bu üçgenlerin boyutu en fazla B. Böylece resim, aşağı yukarı bu görünümde birşey. En çok B boyutunda bir küçük üçgenimiz var. Bunun azami B boyutunda alt-ağaçlardan oluşan bazı çocukları yani ardılları var ve aynı boyutta. Bunlar bir parçanın içinde. Ve özyinelemede potansiyel olarak buna benzeyen başka parçalar var.

Tamam, ama her şeyi çizmedim. Daha, B ve arasındaki boyutta bir miktar alt-ağaç ile, bu boyutta başka karelerin de olması lazım. O nedenle, bu ağacın tamamını, baştan aşağı, daha düzenli hale soktum. Sonra bu düzeylerde, burada, burada bulunan alt-ağaçların her birinin düzen kalitesini arttırdım. Bu iki özyineleme düzeyinden sonra, her şeyin bir blok’a sığdığı ortaya çıktı. Her şey aynı boyutta olduğu için, belli bir noktada, zorunlu olarak hepsi bir bloka sığacak.Hatta aslında, bir bloktan daha da küçük olabilirler. Ne kadar küçük?

Bunun için, düzeylerin hepsini, aynı noktada kesiyorum ve bu ağaçlardan birinin yüksekliği, esas itibariyle en fazla log B olduğunda, kesmeyi durduruyorum, çünkü düğümlerin sayısının yaklaşık B olacakları nokta bu. Öyleyse, yükseklik ne kadar küçük olabilir? Orta seviyede kesmeye devam ediyor ve en fazla log B olduğunda aynı şekilde duruyorum. Log B bölü iki. Öyleyse, en fazla log B, en az da log B’ nin yarısı oluyor. Bu nedenle, düğümlerin sayısı da, burada B’nin karekökü ve B arasında olabilir. O takdirde bu, daha küçük ve bir blokun sabit faktöründen daha az olabilir; önemi olmayan bir iddia. Pekala bu, --B’nin karekökü küçüklüğünde bir şey olduğunu yazmayacağım bile, çünkü çözümlemede bir rolü yok. Bir kaygıdan ibaret ama bir zararı yok, çünkü sınırımız sadece log B yi içeriyor. B yi içermiyor.

Şimdi yapacağımız şey şu.. Bu üçgenlerin her birinin yüksekliğinin en fazla B, en az da logB’nin yarısı olduğunu biliyoruz. Ve bu sebepten, eğer bir arama yoluna bakarsanız –yani bu ağaçta bir arama yaparsanız yukarıdan başlayacağız; şimdi diyagramı karışık hale getireceğim. Bir yol izleyeceğiz, belki buradan aşağı doğru gider şekilde çizmem daha iyi olurdu. Bu üçgenlerin bazılarını ziyaret ediyoruz ama bir kök – düğüm yolunda .. Öyleyse, üçgenlerden kaç tanesini ziyaret edebiliriz? Cevabı ağacın yüksekliği bölü, bu üçgenlerden birinin yüksekliği. Öyleyse bu, en fazla log N bölü yarım log B.

Bu, N’nin log tabanı B, dikkatinizi çekerim, ikinin faktörü. Şimdi merak ettiğimiz, bir üçgenin kaç blok işgal ettiği. Bu üçgenlerden bir tanesinin bir bloka sığması lazım. Ama--özyineleme yerleşiminden bunun bellek içinde birbirini takip eden bölgelerden birinde depolandığını biliyoruz. Öyleyse, kaç blok işgal edebilir? Yanıt: İki, çünkü “alignment” yani hizalamadan ötürü, bir blokun sınırından diğerine taşabilir ve bir üst bloğa da sarkabilir. Yani, bir üçgen iki blok işgal edebilir; bunun anlamı, bir üçgen bir bloğa sığar ama hizalamaya bağlı olarak, B boyutunda en fazla iki blok yani iki bellek bloku içinde olabilir. Öyle ise bellek transfer sayısı, başka bir deyimle okuduğumuz blok sayısı, çünkü burada yaptığımız tek şey arama sırasında okuma -- üçgen başına en fazla iki bloktan ibarettir.

Burada bu kadar üçgen var; öyleyse en fazla, B tabanında log( N ); bu da B tabanında log(N )düzeyindedir. Bu 4 sabitini daha karmaşık veri yapılarıyla değiştirme konusunda yazılmış makaleler var. Sanıyorum ikiden biraz daha az bir değere indirebilirsiniz.

Gördüğünüz gibi sabit açısından B ağaçları kadar iyi değil, ama gene de iyi. Bunun iyi yanı, bu veri yapısının tüm B’ler için aynı zamanda çalışması.

Bu çözümleme bütün B için geçerli. Böylece, karşımızda “multi level memory hierarchy” yani çok katmanlı bellek hiyerarşisi var, ama bu sorun değil. Bu veri yapısı hakkında herhangi bir soru var mı? Bu oldukça karmaşık bir örnek, ama daha da karmaşık hale getireceğiz. İyi, soru yok. Bu, anlattıklarımın ya kusursuz derede açık olduğunu, ya biraz güç geldiğini veya ikisinin birlikte olduğu bir durumu gösteriyor. Bundan sonra, hangi konuda konuşmam iyi olur diye kendimle tartıştım. Doğal olarak bahsedeceğim iki konu var, bunların ikisi de karışık. Belleği dikkate almayan ortamdaki ilk sonucum, bu veri yapısını ‘dinamik’ kılmak. Yani, önümüzde bir dinamik B ağacı var; bu belleği dikkate almıyor ve B’ nin her değerinde çalışıyor ve log B tabanında N veriyor, Araya yerleştir, sil ve ara. Bu ise sadece B tabanında log (N) düzeyinde arama yapar. Bu veri yapısı ilk makalemizde çok zordu, sonradan kolaylaştı.

Artık çok zor değil, ama ileri algoritmalar sınıfında öğretilmesi dahi birkaç ders alıyor. Ben böyle yapmayacağım. Bilmeniz gereken, mevcut olduğu. Ancak onun yerine, şimdi belleği dikkate almayan, sevdiğimiz “sıralama” sorununu inceleyeceğiz. Bu da çok karmaşık, beklediğinizden de fazla. Genelde, doğru yanıtı elde etmek “multithreaded setting” yani çok izlekli ayarlamada olduğundan çok daha güç.

Belki, çok izlekli ayarlamalarda en iyi yanıtı almak da zor bir şey. Ama geçen hafta gördüğümüz versiyonu çok kolaydı. Fakat, önbelleği dikkate almayan sıralamaya geçmeden önce, ön belleği önemseyen çeşidi üzerinde konuşmak istiyorum., Çünkü sınır olarak neyi amaçladığımızı bilmemiz lazım. Bu arada ikaz edeyim, önbelleği dikkate almayan çeşidin çözümlemesinin tamamını yapamayabilirim, Ancak içine neyin girdiği konusunda bir fikir vermek istiyorum . Çünkü çok güzel fikirlerle dolu...

Pekala, nasıl sıralayabilirsiniz? Belleği önemseyen algoritmada herşeyi yapabileceğimizi varsayıyoruz. Anlamı, temelinde B ağaçları var. Bildiğimiz, tek yapı, o. Sahip olduğunuz tek veri yapısının o olduğunu bilerek, N adet sayıyı nasıl sıralarsınız? Doğru, önce B ağacının içine ekleyin, iç sıralı gezinmeyi uygulayın. Sıralamanın bu yolu oldukça uygun. Buna bir B ağacının içine yinelenen araya yerleştirme diyeceğiz. Kırmızı-siyah ağaçlar gibi dengeli ikili arama ağaçları kullandığınız kurulumda, BST sıralamada N log N zaman aldığını; işlem başına sürenin log N olduğunu ve bunun, kıyaslama modelindeki en iyi sıralama algoritması olduğunu biliyoruz.

Öyleyse bu veri yapısı kaç bellek transferi sürüyor? Afedersiniz, bu sıralama algoritması demek istiyorum . Hatırlayacağınız gibi bellek transferlerinin sayısı, N nin bir fonksiyonudur ve MT(N)’dir, değil mi? Bu kolay. Burada “in order traversal” ı yani iç-sıralı gezinmeyi düşünmeniz gerekiyor. Bunun için de geriye giderek, B ağaçlarının çözümlemesini hatırlamanız lazım. Bu da fazla zor bir şey değil. Araya yerleştirme ne kadar zaman alır? N sayıda araya yerleştirme? N log B tabanında (N) kadar. “Traversal” yani gezinme ne kadar süre alır? Daha az zaman. Eğer üzerinde düşünürsek, N bölü B bellek transferinden kurtulabilirsiniz, böylece bundan epeyce az olur. Bu, N den daha büyük ve aslında oldukça kötü. N sayıda bellek transferi demek, gelişi güzel erişim yapıyorsunuz, yani her elemanı gelişi güzel bir düzende ziyaret ediyorsunuz demektir. Bu ise daha da kötü. Şimdi log faktörü, bu log B faktörü ile azalıyor. Yani gerçekten kötü bir sıralama sınırı.

Demek ki, sıralama için bir arama ağacını kullanmanın iyi bir yol olduğu normal algoritmaların aksine, önbelleği dikkate almayan veya önemseyen sıralamalarda gerçekten çok, çok kötü. Öyle ise sıralamanın ne olduğunu bilerek kullanabileceğiniz normal başka algoritma ne olabilir? Hatta ön belleği dikkate almayanlarda bile -- şimdiye kadar gördüğümüz bütün algoritmalar önbelleği dikkate almıyordu. Öyleyse hangisi denemek için iyi olabilir? Birleştirme sıralaması ? Evet, çokizlekli algoritmaları birleştirme sıralamasında kullanmıştık; şu iyi böl-ve-fethet’ le birleştirme sıralamasını bir deneyelim. Bundan böyle, ismine ikili birleştirme sıralaması yani “binary merge sort” diyeceğim, çünkü hem dizilimi ikiye bölüyor, hem de her iki parça üzerinde de özyineleme yapıyor. Böylece karşımıza bir ikili özyineleme ağacı çıkıyor. Öyleyse bunu çözümleyelim.. N sayıda eleman üzerinde bellek transfer sayısı: N elemanın oldukça iyi bir özyineleme yerleşimi var, değil mi? Dizilimimizi böldükten sonra elde etmiş olduğumuz iki alt-dizilim, ardı ardına dizilmiş. Bunun üzerinde ve bunun üzerinde özyineleme yapıyoruz.

Önbelleği dikkate almayan, güzel bir önbelleği dikkate almayan yerleşim. Bu yerleşim önbelleği önemseyen bir algoritma için bile iyi. Bu çok iyi bir algoritma, göreceğimiz gibi, bundan çok daha iyi. Ama elde ettiğimiz yineleme ne? Bunun için, önbelleği dikkate almayan özyinelemeli algoritmaları görürken, özyinelemeler hakkında düşündüğümüz son derse geri dönmemiz gerekiyor. İlk kısım oldukça kolay demek istiyorum. Bir büyük O mu var?. Tamam O ile böl-ve-fethet i en sonA alalım. Özyineleme, N bölü ikinin 2MT si, iyi.

Bu tıpkı birleştirme sıralaması özyinelemesinde olduğu gibi. Düşündüğünüz şey de toplanır terimler. Normal olarak, buraya doğrusal bir toplanır terim ödeyecektik çünkü birleştirme N düzeyinde zaman alır . Şimdi iki girdi ve bir çıkıştan oluşan üç paralel tarama’yı birleştiriyoruz. Doğru, tam paralel değiller, aralarında serpiştirmeler var. Biraz komik bir şekilde serpiştirilmişler ama, önbelleğiniz en az üç bloku depo ettiği sürece, bu ayarlamada bu da doğrusal zamanlı-- ve her bloğu ziyaretiniz aynı sayıda olur demektir.

Bu, özyineleme. Şimdi, şüphesiz bir de taban durumuna ihtiyacımız var. İki taban durumu gördük: biri B nin MT si idi, diğeri önbelleğe sığan her ne ise onu ifade eden MT. Şimdi ona bakalım, çünkü o daha iyi. Böylece bir C sabiti için, eğer M boyutunda bir dizilimim var ve önbelleğe sığıyor ise, aslında C burada muhtemelen birdir ama, ben gene de dikkatli olacağım. Belli bir sabit -- bu önbelleğe sığıyor.Bu boyuttaki bir problem önbelleğe sığıyor ve o durumda bellek transfer sayısı -- kimse hatırlıyor mu? Bu taban durumunu birden fazla kez kullanmıştık. Hatırlıyor musunuz?

Afedersiniz? CM bölü B. Burada büyük O var, öyleyse M bölü B. M bölü B düzeyinde, çünkü bu verilerin boyutu. Yani, sadece içindekilerin hepsini okumanız M bölü B alıyor. Bir kere de önbelleğin içinde olduktan sonra, burada doğru sabit için doğrusal mekan kullandığım sürece, ne yaptığım fazla bir önem taşımaz. Başka bir deyimle, o algoritmada doğrusal mekan kullandığım sürece önbelleğin içinde kalacağımdan, en sonuna kadar hiçbir şeyi dışarı yazmama ihtiyaç olmayacak ve ancak bu sonuncu halde, tamamını yazmak için, M bölü B’yi kullanacağım.

Yani, doğrusal mekan kullandığı sürece, hangi algoritmayı kullandığım önem taşımıyor ve M bölü B’den fazla bir harcama yapmam gerçekten söz konusu olmuyor. Böylece bu aşağı yukarı her algoritmada faydalı bir taban durumu oluşturuyor. Tamam özyineleme bu. Şimdi çözmemiz gerekiyor. Önce, ikili birleştirme sıralamasının ne kadar iyi olduğunu görelim. Bu özyinelemenin ardındaki yanıt için gerekli sezgiyi vereceğim ve ispatı için “substitution” yani yerine koyma metodunu kullanmayacağım. Fakat bu gerçekten oldukça basit. Böylece, en yukarıda – aslında buraya yazacağım, aksi takdirde ben göremeyeceğim. Özyinelemenin en yukarısında, N bölü B maliyeti var diyorduk. Sabitleri dikkate almıyorum. Bir olasılıkla, toplanır sabitler de var. Burada onları da hesaba katmıyorum. Sonra bunu yarı boyutta iki probleme dönüştürüyoruz ve yarım N bölü B ile, yarım N bölü B elde ediyoruz.

Ve aslında bu N, yarım N ve yarım N idi. Bunun eminim birinci dersten hatırlıyorsunuzdur. Böylece bu düzeydeki genel toplam, N bölü B’dir. Bu düzeydeki toplam da N bölü B’dir. Bunun her düzeyde aynı, yani N bölü B olduğunu tümevarım ile kanıtlayabilirsiniz. Soru, kaç düzey olduğudur. En altta -- yani nokta, nokta, nokta, bu özyineleme ağacının en altında, M boyutunda bir şey elde etmemiz lazım ve M bölü B öderiz. Aslında burada M bölü B ödüyoruz.

Sonuçta bunların birbirine uyumlu olması iyi bir şey. Uyumlu olmalılar. Burada yaprak grupları var, tamamının boyutu M bölü B. Buradaki yaprakların sayısını hesaplayabilirsiniz, o da N bölü M. Eğer kesin emin olmak istiyorsanız, yaprakların düzeyini kontrol etmelisiniz. Bu iyi bir fikirdir. Böylece, N bölü M yaprağımız var, herbirinin maliyeti, M bölü B. Bu bir M. Öyleyse, bu da N bölü B. Yani buradaki her düzey N bölü B bellek transferi yapıyor. Ve düzeylerin sayısı --- N bölü B mi? Log N bölü B. Evet, doğru. Ben doğru duymamışım. Pekala, N de başlıyoruz. M ye doğru aşağı iniyoruz. Böylece, ikili ağacın tümünü log N olarak düşünebilirsiniz eksi bu alt ağaçlar log M, bu da log N bölü M ile aynı veya nasıl düşünmek istiyorsanız öyle.

Burada önemli nokta, bunun log tabanının iki olması. Yani burada çok da başarılı değiliz . Aslında bu oldukça iyi bir algoritma .Bu sebeple yanıtı buraya yazayım. Demek ki, N eleman üzerinden bellek transfer sayısı, düzeylerin sayısı kere her düzeyin maliyeti ediyor. Bu da, N bölü B çarpı log 2 tabanında (N bölü M), ki bu da bir B ağacında yinelenen araya yerleştirmeden çok daha iyi. Burada, N çarpı log N bölü log B elde ediyorduk, yani N log N bölü log B oluyordu ki böylece, hiçbir şeye yaramayan bir log B kadar tasarruf ediyorduk. Burada ise bir B faktörü kadar tasarruf elde ediyoruz. N log N bölü B. Gerçekte, bunu N bölü M ile bölerek daha da küçültmüş olduk. Bu çok fark ettirmez. Ama bu B ile bölme, önemli bir şey.

Pekala, yakında oraya varıyoruz. Bu algoritma en iyiye yakın bir algoritma. Önbelleği dikkate almıyor bile ve bu oldukça iyi. O küçük ek adıma gelince, bir log B faktörü kadar daha geliştirebilmek lazım. Ben bu iki fikri birleştirip, hem N log N’deki bu B faktörü gelişimini korumak istiyorum, hem de N log N’deki bu log B faktörü gelişimini korumak istiyorum ve bunları birleştirmek istiyorum. Bunun için bu işi önbelleği dikkate almayan biçimde yapmadan önce, önbelleği önemseyen biçimde yapacağız.

Bu önbelleği önemseyen üçüncü algoritma oluyor. Bu önbelleği dikkate almayan bir algoritma idi. Şimdi daha iyi sonuç almak için, bir birleştirme sıralamasını yani merge sort‘u nasıl değiştirmeliyim? Demek istediğim, elimde bu log iki tabanı var, benim istediğim yaklaşık bir log B tabanı. Bunu birleştirme sıralaması ile nasıl yapabilirim? Evet ? -------- B alt-dizilime bölerek, doğru. Yani, ikili birleştirme sıralaması yapmak yerine, burada ben bunu kastediyordum,-- önce iki parçaya bölüp, bu iki parça üzerinde özyineleme yapıp sonra da onları birleştirmek yerine, onları potansiyel olarak daha fazla parçaya bölebilirim. Bunu yapmak için önbelleğimi kullanacağım. Buradaki fikir, B- parçaları. Bu parçaların uygun olmalarına karşın, yapılacak en iyi şey bu değil. Daha önce bunu ima ettim, çünkü bir log B’ye ihtiyacım var diyordum . Aslında benim istediğim tam log B değil; log M bölü B. Sorun değil. Bakalım. Pekiyi o halde, en fazla kaç parçaya bölebilirim?

bunu N parçaya bölebilirim. Bu iyi olurdu, değil mi? Hem de sadece tek özyineleme düzeyinde? Ama N parçaya bölemem. Niçin? N sayıda parçaya bölersem bunun nesi yanlış olur? Çünkü bu en sonu olur. ---- Tam birleştirme yapamazsınız. Yani elimde N parça varsa bunları önbellekte birleştiremem. Demek istediğim, önbellekte birleştirme yapabilmem için, birleştireceğim her listeden oluşan blokların tamamını önbellekte depolayabilmem lazım. Eğer her liste için bloğun tamamını önbelleğe depolayabiliyorsam, o takdirde bu bir paralel taramalar demeti olur. Bu da paralel tarama teknolojisinin bir anlamda limitini test etmek gibi bir şey olur. Eğer K paralel taramanız var ise ve K sayıda bloğu önbelleğe sığdırabiliyorsanız, ancak o zaman her şey yolunda demektir, çünkü ancak o zaman hem o K dizilimlerinin her biri içinde tarama yapabilirken, hem de aynı anda K dizilimlerinin her birinden önbellekte bir blok olabilir.

İşte, buradaki fikir de bu. Şimdi önbelleğe kaç blok sığdırabilirim? M bölü B. Yapabileceğimin en iyisi bu. Bu da, bu çeşit birleştirme sıralaması algoritmaları arasında en iyi koşma süresini verecektir. Yaptığımız, bir “ M bölü B tarzı birleştirme sıralaması “. Böylece şimdi, bir dereceye kadar daha iyi bir özyineleme elde ederiz. Gerçekten de şimdi, M bölü B boyutunda alt-problemler halinde bölüyoruz ve bu parçaların her birinin boyutu, N’nin, M bölü B’ye bölündüğünde çıkan sonuç kadardır. Şimdi iddiamız, birleştirme zamanının hala doğrusal olduğu, çünkü zaten ancak yetecek kadarına sahibiz.. Belki bu algoritmayı açıklamalıyım. Özetlersem, bölüyoruz çünkü şimdiye kadar ikili olmayan birleştirme sıralamalı bir algoritmayı hiç yapmadık. Bölerek, iki tane yerine, M bölü B boyutunda, birbirine eşit alt-dizilimler oluşturuyoruz. Burada açıkça önbelleği önemseyen bir algoritma yapıyoruz; M bölü B nin ne olduğunu bildiğimizi varsayarak..

Sonra özyineleme yapıyoruz; özyinelemeli olarak her alt-dizilimi sıralıyoruz, --sonra da fethediyoruz; birleştiriyoruz. Ve birleştirme çalışıyor çünkü önbellekte bir blok ayırabiliyoruz. Buna, ”altdizilim başına bir önbellek bloğu“ diyelim. Aslında dikkat ederseniz, çıkışa göndermeden önce, birleştirilmiş dizilimin çıkışı için de bir bloğa ihtiyacınız var. Öyle ise, bu da M bölü B eksi bir olmalı. Fakat bazı toplanır sabitleri dikkate almayalım. Böylece elde ettiğimiz özyineleme bu olur. Taban şıkkı aynı.

Öyleyse, burada daha iyi olan ne? Demek istediğim, düzey başına maliyet değişmiyor, en azından ben böyle iddia ediyorum, çünkü en üstte daha önce de olduğu gibi N bölü B elde ediyoruz. Sonra, M bölü B boyutlu alt-problemleri böldük, her birinin maliyeti de bir bölü M/B faktörü çarpı N bölü B.. Tamam, bunların hepsini topladığınızda ,hala N bölü B elde ediyorsunuz, çünkü elemanların sayısını azaltmıyoruz. Onları, sadece bölüyoruz. Şimdi, M bölü B alt-problem var ve her biri bir bölü M/ B boyutunda..

Böylece, daha önce olduğu gibi, her düzeyin toplamı N bölü B olacak. Değişen sadece düzeylerin sayısı, çünkü şimdi dallanma faktörümüz daha büyük; buradaki log tabanı ikiydi, şimdi log tabanı dallanma faktörü kadar oldu. Öyleyse bu ağacın yüksekliği, sanırım log M bölü B tabanında, N bölü M oluyor. Bunu bir kontrol edeyim. –Evet.. -- tamam. Eğer dikkat ederseniz bu, düzeylerin sayısını değil, ondan bir eksiğini veriyor. Bu nedenle buraya artı biri ekleyeceğim. Sebebi, istediğim sınırın tam olarak bu olmaması.

Şimdi elimizde M bölü B tabanlı bir log var; aslında benim istediğim N bölü B. Bunların her ikisinin de eşit olduklarını iddia ediyorum çünkü burada bir eksi terim daha var. -- tamam, bu iyi. Bu sizlere biraz esrarengiz gelebilir ama ben sıralama sınırının ne olması gerektiğini biliyorum. Biraz aritmetik yapıyorum. N bölü M’nin, log M bölü B tabanındaki değerini alıyorum. Log’un tabanını değiştirmiyorum. Sadece N bölü B’nin, M bölü B’ye bölünmüş halidir diyorum; çünkü B’ler gidiyor ve M aşağıya iniyor. Öyleyse, bunu log’larda yaparsam, N bölü B’nin logu eksi M bölü B’nin logu -- eksi çünkü bölüyorum. Şimdi, M bölü B nin, log M bölü B tabanındaki değeri bir eder.

Öyleyse, bunlar birbirini götürür ve log M bölü B tabanında, N bölü B elde ederim ki hedeflediğim de buydu. Niçin? Çünkü yazılışı doğru olan sınır bu. Şimdi, önbelleği dikkate almayan yoldan bunu elde etmeye çalışacağız. Demek ki, arama ağacının yüksekliği bu ve her düzeyde N bölü B bellek transferi ödüyoruz. Öyleyse bu M bölü B tarzı birleştirme sıralaması için toplam bellek transfer sayısı, sıralama sınırıdır.

Bunu çerçeveye alacağım. Sıralama sınırı bu oldu, -- çok özeldir, çünkü N öğeyi önbelleğin farkında olan yoldan sıralamak için, en iyi bellek transfer sayısına karşılık gelir. Bu, 1983’ten beri biliniyor. Yapılacak en iyi şey bu. Gerçekten biraz acayip bir sınırdır, ancak B’ lere bölme işlemini dikkate almazsanız, N çarpı , M log M tabanında N gibi bir şey kalıyor. Bu biraz daha makul. Ancak, B’ lerle bölünmüş çok şey var. Böylece, “girdideki blokların sayısı” --- çarpı “önbellekteki blokların sayısı tabanlı” logaritma --, ve log işlemine alınacak “girişteki blokların sayısı” . Bu biraz daha sezgisel. Ama sınır da bu ..

Bizim hedeflediğimiz de bu. Yani bu algoritma sonuna kadar, bizim M bölü B nin ne olduğunu bildiğimizi var sayıyor. Şimdi işlemi, M bölü B’yi bilmediğimizi var sayarak önbelleği dikkate almayan şekilde yapacağız. Bunun sonucuna sadece birkaç yıl önce varılabildi. Hazır mısınız? Buraya kadar her şey açık mı? Çok olağan bir algoritma. Temelde onu taklit edip bir birleştirme sıralaması yapacaktık, ama bir “M bölü B tarzı birleştirme sıralaması” yapmayacağız, çünkü bunun nasıl yapıldığını bilmiyoruz.

Bir karekök N yöntemli birleştirme sıralaması yani “square root of N way merge sort” yapmaya çalışacağız. Eğer bununla biraz oynamak isterseniz doğal olanı budur. Buradaki şaşırtıcı taraf, N’nin kare kökü listelerini aynı anda önbellek verimliliği açısından etkin bir şekilde birleştirmenin güçlüğüdür. Biliyoruz ki, eğer N’nin karekökü, M bölü B den büyükse, doğrudan bir birleştirme yaparsanız, çuvallarsınız. Öyle ise daha gösterişli bir birleştirmeye ihtiyacımız var. Böl-ve-fethet-birleştirmesi yapacağız. Bu, geçen hafta gördüğümüz çok izlekli algoritmalara çok benziyor, -- böl-ve-fethet-birleştirmesini yaptığımızda, ne kadar liste birleşirse birleşsin, bunlar N’nin karekökünden küçük, hatta küp kökünden küçük olduğu sürece, önbellekte bu birleşmeyi etkin şekilde yapabilirsiniz, değil mi? Öyleyse bunu yapacağız, ancak bir kuruluma ihtiyacımız var, çünkü önbelleği dikkate almayan sıralamayı bu kurulumda yapacağız. Sıralama sınırını elde etmek istiyoruz.

Önbelleği dikkate almayan sıralama yapmak için, önbellek boyutu üzerinde bir varsayım yapmanız gerekir. Bu biraz sıkıcı, çünkü, önbelleği dikkate almayan algoritmanın, hem B’nin, hem de M’ nin tüm değerlerinde çalışması gerektiğini söylemiştik. Aslında bu sınırı önbelleği dikkate almayan yoldan elde etmek için, bir varsayıma daha ihtiyacınız olduğunu kanıtlayabilirsiniz.

Geçen yıl Garret Brodel’ın vardığı sonuç gibi. Varsayım temelde oldukça zayıf. Bu iyi haberdi. Aslında birkaç kez varsayım yapmıştık; önbellek en az üç blok yada en az dört blok depolayabilirse,-- evet önbelleğin en az dört bloğu veya en az sabit sayıda bloğu depolayabileceğini düşünmek makuldür. Bu, önbelleğinizin depo edebileceği blokların sayısının, en az B’nin Epsilon kuvvetine kadar olduğunu söylüyor.

Bu, önbelleğinizin gerçekten dar olmadığını anlatıyor. Yüksekliği ile eni yaklaşık aynı. Bu da size büyük rahatlık veriyor. Şimdi, M’nin en az olduğu varsayımının basit bir versiyonunu kullanacağız. Bu çok doğal. Bu, bloklarınızın bulunduğu önbelleğinizin geniş olduğu kadar yüksek olduğunu ifade ediyor.Oldukça makul bir varsayım ve bugünlerdeki önbelleklere bakarsanız, hepsi de belli epsilon boyutlarıyla varsayımımızı karşılıyor..

Genelde, M en az veya o civarda olur. Geçenlerde konuştuğumuz ışık hızı konusu açısından da, veya gerçekten yapılacak doğru şey oluyor. Dışarı, 3-D yani 3 boyuta çıktığınızda, , oradaki mekanın yüzey alanı olur. Demek ki bu, belli bir mesafede ne kadar mekanınız olması gerektiğini göstermesi açısından da doğal. Sabit boyutlu bir alanda yaşadığımızı varsayarsak, bu varsayım doğru çıkacak. Bu boyutların 42 ya da daha fazla olması halinde bile geçerlidir. Yani oldukça makul bir yaklaşımdır. Pekala, şimdi bu sınırı elde etmeyi başaracağız. Yapmaya çalışacağımız şey, “N üzeri epsilon-tarzı-birleştirme-sıralaması” olacak; belli bir epsilon değeri için. Bu arada, M’nin en az olduğunu varsayarsak, epsilon üçte bir çıkar.

Öyleyse, “ küpkök-N-tarzı-birleştirme” yapacağız. Belirlenmiş bir sınırlama çerçevesinde, birleştirmenin nasıl yapıldığını bildiğimiz varsayımıyla, sıralama algoritmalarını size vererek ve çözümlerini yaparak başlayacağım. Sonra birleştirmeyi yapacağız; zor olan yanı, birleştirme. Tamam, birleştirme..-- ilk önce size kara kutuyu vereyim. Her şeyden önce, birleştirme ne yapıyor? K tarzı birleştirmeye K hunisi deniyor, çünkü göreceğiniz gibi, aynı bir huni’ye benziyor. K hunisi bir veri yapısı veya veri yapısını andıran bir algoritmadır. Ve K-sıralamalı-listeleri birleştirir. Böylece, bir an için elinizde K listelerinin bulunduğunu, bunların sıralanmış ve nispeten uzun olduklarını düşünürsek, bu karakutu ile çalışmak ve sıralama yaptığımızda o listeleri elde edebilmek için de belli ek varsayımlara ihtiyacımız vardır. Ve sıraladıkça bunları elde edebileceğiz.

O listelerin toplam boyutunu istiyoruz. Tüm elemanları topluyorsunuz; bu listelerin en az boyutunda olmaları gerek; varsayım bu. Sonra bu listeleri, temelde sıralama sınırını kullanarak, birleştiriyor. Aslında, theta demeliyim. Bu boyuttan çok daha büyük olmasını da istemiyorum. Bunun için özür dilerim. Böylece, bu birleştirici huni’nin kullandığı bellek transferlerinin sayısı: -- üzerindeki sıralama sınırı, yani bölü B, -- bölü B nin, M/B tabanındaki logaritması, -- artı başka bir K bellek transferidir.

K sayıda bellek transferi oldukça makuldür. Bu durumda en azından her listeyi okumaya başlamalı ve liste başına bir bellek transferi ödemelisiniz. Tamam, ama amacımız bir anlamda bu artı K’dan kurtulmak olacak. Birleştirmeyi bu kadar süratli yapabiliriz; bunu sonra yapacağız. Şimdi elimizde bunun olduğunu varsayarak, sıralamayı nasıl yapacağımızı anlatalım. Bu “Huni sıralaması” denen sıralama, sonuç olarak, yeterli. Fakat, bir anlamda, küp kök N tarzı birleştirme sıralaması.” Pekala, bunu bu durumu kullanarak analiz edeceğiz. Yani, Huni sıralamasında, K’ yi, küpkök N olarak tanımlayıp, bu birleştirmeyi uygulayacağız. Öyleyse ne yapıyoruz? Tıpkı burada olduğu gibi, dizilimimizi küpkök N boyutlu parçalara böleceğiz.

Bu parçaların ardı ardına alt-dizilimler halinde olmaları gerektiğini söylüyorum. Bunlara dizilimin bölütleri yani “segments of the array” diyeceğim. Önbelleği dikkate almayan durumlarda, dizilimlerin ne şekilde düzenlenmiş oldukları gerçekten çok önemlidir. Dizilimleri kesecek ve birbirini takip eden küpkök N sayıda dizilim parçaları elde edeceğiz. Sonra onları, özyineleme yolu ile sıralayacağım, sonra da, birleştireceğim. Birleştirirken, K Hunisi’ni, küpkök N hunisini kullanacağım çünkü.-- Şimdi neden 1/ 3 kullanıyorum? Bu üç nedeniyle. Küpkök N hunisini kullanabilmek için, birleştirmeyi yaptığım elemanların toplam sayısının en az ’ün olmasını garanti etmem lazım. Bu sayının küpü de N dir. Bu da elimdeki elemanların kesin sayısı.

Bu huniyi kullanabileceğim koşulu tanımlar.. Küpkök N Hunisini kullanabilmem için elimde en az elemanın olması gerekir. Eğer böyle bir gereklilik olmasaydı, her biri bir boyutunda N listem var diyebilirdim. Bu durum ise bu birleşimde kesinlikle iyi çalışmaz. Sezgisel bakınca bu, artı K sizi öldürecektir. Bu Artı M ye dönüşecek ve çok büyüyecektir.

Ancak, bir küpkök N hunisi kullanabilir ve bu yoldan sıralama yapabiliriz. Öyleyse bu algoritmayı çözümleyelim. Umarım her şeyi doğru yaparsam sıralama sınırlarını verecektir. Bu oldukça kolaydır. Sıralama sınırını tekrar tekrar yazdığım için burası bayağı karışmış. Pekala, bu birleştirmenin maliyeti. Bu kökteki durum. Fakat bu durumda N’dir. Öyleyse, özyinelemenin kökünde-- ama önce özyinelemeyi yazayım. Afedersiniz.. N eleman üzerinde, küpkök N sayıda bellek transferimiz var. Bunu doğru yazayım. Evet, küpkök N sayıda özyineleme, her biri N’nin 2/3 boyutunda, --tamam – artı bu zaman, ama K^3 N’ye eşit.

Böylece bu, artı N bölü B çarpı,-- N bölü B’nin M/B tabanındaki logaritması,-- artı M nin küpkökü… Bu da toplanır artı K’ lerim.. Öyleyse bu benim özyinelemem. Taban durumum her zamanki gibi.. MT belirli bir sabit çarpı M, yani M bölü B düzeyinde. Böylece burada neyi elde etmek istediğimizi biliyoruz. Yoo.. Hiç de değil. Bundan önceki bütün yinelemelerde her düzeyde aynı maliyeti bulmuş ve log faktörümüzü bundan elde etmiştik. Şimdi bir log faktörümüz var bile, öyleyse, bir ikincisini çıkarmamalıyım.. Doğru mu?. Kanıtlamak istediğimiz sınır bu. Şimdi burada bir saniye kopya çekmeme izin verin.

Evet, eminim-- bu küpkök N’nin oldukça büyük olmasına siz de şaşıyorsunuzdur. Eğer bundan daha büyük ise, özyinelemenin en üst düzeyinde başımız zaten dertte demektir. Şimdi ben bunun kabul edilebilir olduğunu iddia ediyorum. Küpkök N’ye, bir bakalım. Burada bir taban şıkkı var ve N’nin tüm değerlerini, en çok belli bir sabitle çarpımı durumda tanımlıyor.. Eğer bu durumdaysam, N’ nin en az, önbelleğin bir sabitle çarpımı sonucunda olduğu kadar büyük olduğunu biliyorum.

Şimdi önbelleğin en az olduğunu varsaymıştık. Eğer daha dikkatli olmak isterseniz, bunu B’nin bir artı epsilonuncu kuvveti ile de yapabilirsiniz. Böylece N en az dir, tamam mı? Bundan sonra bunlarla başım hep derde girer. Böylece bu, N bölü B, yani karekök N’nin omegasıdır. Burada pek çok şey söyleyebilirsiniz ama içlerinden sadece bir tanesi doğrudur. Öyleyse, neden? Bu, N’nin karekökünün, en az B olduğunu söylüyor; öyleyse B ile bölünmüş N, en çok N’nin karekökü ile bölünmüş N’ dir. O da en az N’nin karekökü eder. Tabii, tüm bunları kontrol etmelisiniz. Burada aritmetiği oldukça hızlı geçeceğim çünkü sıkıcı, ama gerekli. Pekala, N’nin karekökü, N’nin küp kökünden kesin olarak daha büyüktür, bu tamam. Öyle ise, N bölü B de N’nin küp kökünden kesinlikle daha büyüktür.

Burada, N bölü B çarpı bir’den daha büyük bir şey var. Yani bu örnekte bu terim, kesinlikle şu terime hükmediyor. Taban durumu içinde olmadığım sürece, N’nin en az M düzeyinde olduğunu biliyorum. Bu terim benim özyinelememde kaybolur. Bu iyiydi. Şimdi elde etmek istediğimiz, bu toplam koşma zamanı. Özyineleme maliyeti küçük olsa iyi olacak; sabit faktörün buna göre artışından daha küçük olmalı..

Şimdi özyinelemeyi yazalım.,N / B N/B ‘yi kökte elde ediyoruz. Sonra bir sürü alt-probleme bölüyoruz, burada küp kök N sayıda alt-probleme ayırıyoruz. Ve her biri aslında buna mal oluyor,ancak ,N, N’nin 2/3’üncü kuvvetiyle yer değiştiriyor. Öyleyse, —log_M/B tabanında --,pardon burada B ile bölmeyi unutmuşum--, , bölü B: Bu düğümlerden birinin maliyeti—ve bunlardan küp kök N adet oluyor. Toplam olarak ne oluyorlar? Küpkök N var, var, bunlar çarpımda N olur. Böylece N bölü B elde ediyoruz. Bu fena, bu aynı görünüyor ve biz başka log faktörü kaybetmek istemiyoruz. Ama iyi haber, burada bir adet üçte ikimiz var.

Sonuçta bu düzeyde toplam olarak bunu elde ediyoruz. “Sorting bound” yani Sıralama sınırına benziyor ama, logda hala bir üçteiki var. Şimdi, bir log’da üçteikinin kuvveti üçte iki çarpanı olarak dışarı çıkar. Öyleyse bu aslında:2/3 çarpı, N / B, -- (N/B) yani sıralama sınırı olur. Bu ise, sıralama sınırının üçte ikisine karşılık geliyor. Ve bu da sıralama sınırı, yani bir çarpı sıralama sınırı oluyor.

Demek ki, geometrik olarak küçülüyor.. Eveeet. Bunu ispatlamayacağım ama doğrudur. Bu, 2/3 faktörü oranında azaldı, bir sonrakinin de 2/3 faktörü kadar azalacağı tümevarım ile anlaşılıyor. Yani bir düzeyde doğru olduğunu ispatladığınız şeyin, her düzeyde doğru olması gerekir. Buradaki ayrıntıları atlıyorum. Ama emin olmak için yaprak düzeyini kontrol edebiliriz. Bu daima iyi bir kontroldür. Yapraklarda, maliyetimizin M bölü B olduğunu biliyoruz.

Pekiyi kaç yaprak var? Tıpkı daha önceki gibi N/M yaprağımız var. Tamam öyleyse, en altta toplam maliyet N / B’dir. Ve bu da, elde edeceğinizle eşit olur. Esas itibariyle, sezgi yolu ile bunun bundan küçük olacağını düşündüğünüz için, garip gibi geliyor.Aslında değil. Gerçekte olan şey şu, elinizde N / B kere bu loglu şey var. Fazla aldırmadığımız için buna sadece ‘log’ diyelim.

Bir sonraki düzeyde ele aldığınız, o log’un üçte ikisi. Ve bir sonraki düzeyde, dokuzda dört kere o log ve bu böyle devam ediyor. Böylece, düzeylerin yükselmesine karşılık, log bire ininceye kadar, maliyeti geometrik olarak küçülüyor. Bundan sonra siz, özyinelemeyi durduruyorsunuz ve N / B’ yi en sonunda log’ suz olarak elde ediyorsunuz. Başka bir deyişle, yaptığınız şey N / B’yi değil, log’u küçültmek. Üçte ikinin de, buralarda artık bitmiş olması gerekir. Gerçekte buradaki düzeylerin sayısı log log N.

Bu da sonunda bir elde edene kadar, ilk başta üş eşit parçaya böldüğünüz log’u, kaç kere bölmeniz gerektiğinin sayısıdır. Aslında ihtiyacımız olan bu değil. Geometrik küçülmede kaç düzey olduğuyla ilgilenmeyiz. Sonsuza kadar pek çok düzey olabilir. Geometrik olarak azalıyor ve bunu koşma süresi olarak elde ederiz. MT(N), huni-sıralamasının sıralama sınırı oluyor. İşte bu mükemmel. Bu kadar hızlı birleştirme yapan bir huni elde edebildiğimiz sürece, yapabileceği kadar hızlı sıralama yapan bir sıralama algoritması elde ederiz. Bunu tahtaya yazmadım ama, bu asimptotik açıdan en iyi yani optimaldir. B ve M’nin ne olduklarını bilseniz bile, yapmayı ümit edebileceğiniz en iyi şey budur. Ve burada bunu B ve M ne olurlarsa olsun uyguluyoruz.

İyi. Şimdi huni için hazır olun. Huni bir başka özyineleme olacak. Bu bir özyinelemeli algoritma içindeki özyineleme algoritmasıdır. Bir başka böl-ve-fethet, bu derslerin başında gördüğümüz statik arama ağaçları benzeri. Yani bunların hepsi birbiriyle bağlantılı.. Pekala K hunisi,-- ona K hunisi diyorum çünkü bu onu, sadece küpkök N’de değil, belli bir özyinelemeli düzeyinde düşünmek istiyorum. Aslında, K hunisinin karekökünü özyinelemeli yoldan kullanacağız. İşte o sınırı elde etmem gerekiyor. Özyineleme, statik arama ağacı gibi ve tek bir tahta üzerine çizimi biraz zor, ama işte başlıyoruz.

Elimizde bir karekök K hunisi var; bu özyinelemeli.. Burada yukarıda bir tampon” buffer” yani arabellek var. Bunun adı çıkış tamponu yada arabelleği ve boyutunda.. Ve sadece keyfine birazının dolu olduğunu varsayalım. Ve, başka arabelleklerin de olduğunu varsayalım. Ve bunların da farklı miktarla dolu olduklarını kabul edelim. Bunların her birinin boyutu, şüphesiz K üzeri 3/2. Bu parçaların adı arabellek yada ara tampondur. Ve sonra onlardan sarkan başka huniler var. Karekök K-hunisi burada, bir karekök K-hunisi de burada, her arabellek için bir tane, bu huninin her çocuğu yani ardılı için bir tane.

Pekala, sonra bu hunilerden sarkan giriş dizilimleri var. Tamam, onların K adedini burada çizecek değilim ama, çizmediğim K sayıda giriş dizilimi var, bunlara giriş listeleri diyelim ve onları en aşağıda gösterelim. Buradaki fikir, bunları aşağıdan yukarıya birleştirmek... Önce, enaz toplam boyutlu olan K-giriş-dizilimlerimizle başlayacağız. Burada yukarda bu kadar olduklarını varsayıyoruz. Onları, K’nın karekökü boyutundaki gruplar halinde gruplaştırıyor ve grupların her birini, yani K’ nın karekökü boyutundaki gruplardan oluşan bu K-listelerini, özyineleme yoluyla birleştirecek olan bir karekök-K hunisinin içine atıyoruz. Bu hunilerin çıktısını, yanıtın ne olacağını belirlemek amacıyla bir arabellekte bir şekilde biriktiriyoruz. Diğer taraftan bu tamponlar, tam K üzeri 3/2 boyutunda olmalarına karşın, bu kusursuz bir depolama hacmi olmayabilir çünkü bunların içindeki eleman sayısı ortalama K üzeri 3/2 – çünkü elde toplam var ve karekök K sayıda grup var.

Özetle K^3 bölü K nın karekökü, bu da ortalamada K’nin 3/2’inci kuvvetini verir. Ama, bunların bazıları daha büyük bazıları daha küçük olacaklar. Buraya çizdim. Birleştirme şeklinize bağlı olarak bazıları daha fazla yer boşaltırlar. Ancak ortalamada bunların hepsi aynı zamanda dolacaklar. Sonra onları bir karekök K hunisinin içine sokacağız ve çıktısını elde edeceğiz. Yani bu burada göreceğimiz olayların kabaca oluşma şekli.

Tamam ama, bunların bazıları önce de dolabilir ve o tamponu boşaltmak için belli miktar birleştirme yapmamız ve gelmekte olan başka parçalara yer açmamız gerekir. Tablo işte bu. Şimdi, algoritmanın ne olduğunu söylemeden ve analizine geçmeden önce sadece alan üzerinde düşünün; Çok basit, ısınma amaçlı bir çözümleme olsun.. Haydi “Alan”a giriş, çıkış arabellekleri olmaksızın bakmaya çalışalım. Pekala, neden giriş ve çıkış arabelleklerini hariç tutmak istiyorum? Çünkü , her arabelleği sadece bir defa saymak istiyorum.. Ve bu arabellek bunun için giriş, bunun için de çıkış. Yani bütün arabellekleri özyineleme yoluyla ve sadece bir defa saymak için, yalnızca bu ortadaki arabellekleri sayacağım. Ve giriş ve çıkış arabelleklerinin genelini ayrıca düşünmem gerekecek. Ama bu değerler zaten verilmiş gibi. Yani çıkış için, ‘e ihtiyacım var, Giriş için de K^3. Öyleyse, bütünü düşünmeyi unutun. Böylece ortadaki arabellekleri özyinelemeli yoldan sayarsam, bütün arabellekleri elde etmiş olacağım.

Böylece alan için çok basit bir özyineleme elde ederiz. S(K) yaklaşık olarak, karekök K + bir, çarpı S( karekök K) + O().. Düzey , çünkü elimizde, her biri K üzeri 3/2 boyutunda karekök-K sayıda arabellek var. İnceleyin, sizce de doğru mu? Bu bayağı gibi görünüyor ama, sanırım doğru.Hayır, hayır doğru.Bu K üzeri 3/2 çarpı karekök K,-- o da K üzeri 3/2 artı yarım,-- bu da K üzeri 4/2 dır ve o da eder .Üfff…tamam, iyi. Sadece aritmetiğimde iyi değilim. Buradaki toplam tamponlama K^2. Her düzeydeki özyineleme için bunları topluyorsunuz ve buradaki artı bir tepedeki elemanı, karekök K’ler alttaki elemanları hesaba katmak için yapılıyor ve karekök K artı bir çıkıyor.

Eğer bunlar, -- bir dakika şuraya yineleme ağacını çizeyim. Bu yinelemeyi çözebilmeniz için pek çok yol var. En doğalı K’ye bakacağınız yerde log K’ye bakmanız, çünkü burada log K ikiye bölünüyor. Yineleme ağaçlarını hemen çizeyim ki sezgiyi görebilin. Ama eğer bunu çözecekseniz logları kullanın. Böylece, karekök K artı bir, dallanma faktörü var.

Bundan sonra problem, karekök K boyutlu, öyleyse bu K olacak, hepsinin böyle olacağına inanıyorum. Bu karekök K’nin karesi alınıyor ve bu düzeylerin maliyeti oluyor. Ve böylece devam ediyorsunuz. -- En altın neye benzediğine özellikle aldırmıyorum, çünkü en üstte elimizde var. Bu bize bir sonraki düzeyde maliyetin “K çarpı kök K artı bir” olarak veriyor. Sonraki düzeyin maliyeti K üzeri 3/2 artı K. Yani böylece, ‘den, K üzeri 3/2 artı K’ ya gidiyoruz. Bu bir süper-geometrik, üstel geometrik bir azalım gibi. Bu gerçekten çok hızlı azalıyor. Öyleyse, K^2 düzeyinde.. Bu benim “işim bittiği için el sallama” beyanım. Tamam mı? Öyleyse maliyet, temelde en üst düzeydeki önbelleklerin boyutu olur, yani toplam alan. Buna ihtiyacımız olacak. Bu aslında theta , çünkü burada bir artı theta ‘m var.

Zamanı hesaplayabilmemiz için böyle olması gerekiyor. O nedenle bunu söyledim. Alanın çok büyük olmaması iyi bir duygu değil. Aslında Huni, toplam giriş boyutundan çok daha küçük. Giriş boyutu, . Fakat bu, o kadar hayati değil. Önemli olan, olması ve bunu çözümlemede kullanmamız.Tamam. Normal olarak bu şey özyinelemeli olarak yerleştirilir. En üstteki huniyi özyinelemeli olarak depolarsınız.Sonra, bu örnekte her arabelleği ardı ardına gelen bir dizilim şeklinde yazarsınız. .

Burada bir özyineleme yok. Böylece hepsini teker teker yazın..Sakın kendi aralarında serpiştirmeyin. Düzenli şekilde depolayın. Sonra, bu alttaki hunilerini de özyinelemeli şekilde yazın. Her huni, ardı ardına gelen bir bellek parçasıysa, her arabellek ardı ardına gelen bellek parçaları olarak kalmaya devam ettiği sürece, bu işlemi her zaman özyinelemeli şekilde yapmalısınız. O zaman birazdan yapacağımız süre çözümlemesi çalışacaktır.

Pekala, çözümleyeceğimiz algoritmayı size vereyim. Huninin çalışması için, -- en başta bütün arabellekler boş olduğunu belirtiriz. Her şey en alttadır. Yapacağımız şey, “kök arabelleğini doldur”, demek. Bunu doldur. Bu özyinelemeli algoritma ve bir arabelleğin nasıl doldurulacağının tanımını birazdan vereceğim. Bir kere dolduğunda, her şey yukarı çekilmiş ve birleştirilmiş demektir. Tamam, demek ki bu şekilde başlıyoruz. Özetle, birleştirme demek;, “algoritmayı birleştir, en üstteki arabelleği, en üstteki çıkış tamponunu doldur,” demektir.

Tamam, bir arabelleği şöyle doldurursunuz. Genel olarak, bu özyinelemeyi yol boyunca genişletirseniz,-- taban şıkkında bahsetmemiştim, orada küçük bir düğüm elde edersiniz. Öyleyse, bu şekilde doldurmak istediğiniz rastgele bir tampona bakarsanız, -- mesela bu boş ve siz onu doldurmak istiyorsunuz, -- hemen altta, iki tane çocuğu, iki arabelleği olan bir köşe olacaktır. Belki buna benziyor. Eşit boyutta olmaları dışında, ne kadar büyük olduklarını bilmiyorsunuz. Bundan çok daha küçük veya büyük olabilirler, bilmiyoruz. Ama, ilk derslerimizde, ikili arama ağacı örneğinde yapmış olduğumuz gibi, siz de sonunda bundan bir ikili yapı elde edeceksiniz. Pekala, bu arabelleği nasıl dolduracağız? Sadece bu iki ardıl arabelleği mümkün olan en uzun süre birleştirerek...

Demek ki, bu iki ardıl arabelleği, boşalana kadar birleştiriyoruz. Böylece, genel değişmez, bu arabelleğin,-- bunu bir cümle olarak yazayım. Bir tampon boş olmadığı sürece veya içinde olanlar daha kullanılmamışsa, altındaki alt-ağacın tamamının birleştirilmiş çıkışının bir ön-eki’dir. Böylece bu, aşağıdaki her şeyin kısmen birleştirilmiş alt-dizisi oluyor. Bu, buradaki her şeyin kısmen birleştirilmiş alt-dizisi.

Üstünden elemanları bir bir alarak birleştirme yapabilirim ve bu bana, bir tanesi boşalıncaya kadar oraya koymak üzere çıktılar verecektir. Ancak, önce hangisinin boşalacağı, düzenine bağlı olduğundan bu konuda önceden bir fikrimiz olamaz. Ne zaman biri boşalırsa, onu özyinelemeli olarak doldururuz. Hepsi bu kadar. Algoritma, bundan ibaret..

Ne zaman biri boşalırsa, özyineleme yoluyla onu dolduruyoruz. Taban durumu ve yapraklar bağlamında ise yapacak hiçbir şey yok gibi. Sanırım bir girdi listesinden doğrudan okursunuz. Böylece, en altta, eğer burada bu ikisi arasında birleştirme yapmaya çalışan bir köşeniz varsa, bu iki listenin doğrudan birleştirilmesidir. İki paralel tarama ile bunun nasıl yapıldığını biliyorsunuz. Gerçekte buradaki şeyin tamamını birleştirebilir ve arabelleğe atabiliriz.Tabii bu arabelleğin ne büyüklükte olduğuna bağlı. Bunu sadece arabellek doluncaya kadar yapabiliriz.

Bir arabellek dolduğu anda dururuz ve özyineleme katmanlarını yukarı atarız.. Yani, doldurmak istediğimiz tampon arabellek doluncaya kadar bu birleştirmeyi yapıyoruz, sonra duruyoruz ve yukarı alıyoruz. Birleştirme ile ilgili algoritma bu. Şimdi, algoritmayı analiz etmemiz gerekiyor. Aslında çok zor değil, oldukça akıllı bir çözümlemesi var. Ve üstün yönü, bu bir amortizasyon, yani sizin tercih ettiğiniz yöntem. Böylece, önbelleği dikkate almayan algoritmalar bağlamında, amortize çözümlemede son bir pratik daha yapıyoruz. Ama bu biraz karmaşık olacak. Şimdiye kadar gördüğümüz tüm fikirleri bir araya getireceğiz. Gördüğümüz ana çözümleme fikri, bu özyinelemeyi yapı içinde yapıyoruz,-- eğer gözümüzün önüne getirirsek, K hunimizi alıyoruz, ortadan bölüyoruz, bir sürü karekök K hunisi oluşturuyoruz ve bu böyle devam ediyor; sonra, orta düzeyde olanları da kesiyoruz, dördüncü kökten K hunileri elde ediyoruz ve bu böyle sürüyor, -- belli bir noktada baktığımız huni, önbelleğe sığıyor.

Daha önce bir bloğa sığarsa demiştik. Şimdi, belli bir noktada “bu hunilerden biri önbelleğe sığacak”, diyeceğiz. O özyinelemenin detayı düzeyindeki hunilerin her biri önbelleğe sığacak. O düzeyi çözümleyeceğiz. O düzeye J diyoruz. Şimdi, o özyinelemenin ilk detay düzeyini düşünün ve bu düzeye J diyorum. -- Bu düzeyde sahip olduğumuz her J hunisi -- ve sadece bir tanesi değil, dört tanesi önbelleğe sığar.

Yani bir tanesi önbelleğin dörtte birine sığar. Ama önbelleğin bir kısmını yapılacak diğer işler için de ayırmamız lazım. Ayrıca, J hunisinin sığdığından emin olmak istiyorum. Şimdi bu ne demek oluyor? Alan’ı çözümlemiştik. J hunisinin alanının kadar, belli bir sabit çarpı olduğunu, biliyoruz. Buna C çarpı , diyebiliriz. Öyle ise, bu C çarpı , en çok M bölü 4, yani önbelleğin bir çeyreği eder demektir.

Yani bu boyuttaki bir J hunisi önbelleğin dörtte birini işgal eder, demektir. Özyinelemenin bir noktasında, bu büyük J hunileri ağacımız olacak ve aralarında bir sürü önbellek olmasına karşın, her J hunisinin sığacağını göreceğiz. Şimdi, J hunilerinden sadece bir tanesini düşünün. J karekök K gibi bir şey olsun. Bu şekli kullanalım, aksi halde daha büyük bir şekil çizmem gerekecek. , J hunisinin bu olduğunu düşünün, giriş arabellekleri var ve bir çıkış arabelleği var.

Bu durumda J hunisinin nasıl görev yaptığını düşünmeye çalışalım. Uzun süre, bu tamponlar dolu kaldıkça, bu bir birleşmedir. Bu özyinelemeyle yapılıyor ama biz aslında buna aldırmıyoruz.Bu şeyin tümü değişir değişmez,-- aslında bunu çizmem lazım, huninin ,çıkış tamponu, giriş tamponu devreye girdiğinde, başka bir deyimle o blokların hepsini içeri getiriyorsunuz,-- sadece birleştirme yapar ve bir şey boşalıncaya veya çıkışı dolduruncaya kadar, mutlu birleştirme işlemine devam edebilirsiniz.

Öyleyse, bunu da çözümleyelim. Her şeyin bellekte olduğunu farz edin çünkü sığdığını biliyoruz. Pekala, biraz daha dikkatli olmam lazım. Giriş arabelleklerinin toplam boyutları aslında oldukça büyük, çünkü buradaki toplam boyut,K’nın 3/2’nci kuvveti iken-- burada karekök K. Bu aslında K boyutunda. Genel bir şekil çizeyim. Bir J hunimiz var, -- aksi halde aritmetik bayağı karışacak.

Bir J hunimiz var. Boyutunun C çarpı olduğunu sanıyoruz. Girişlerin sayısı J ve -- boyutları oldukça büyük. Nerede böyle tanımlamıştık? Bir K hunimiz var. Toplam giriş boyutu . Öyle ise J için , bu olacak. Önbelleğin tamamını, bunu depolamaya, ayıramayız. O J’nin ekstra bir faktörüdür. Ama her giriş için bir blok yer ayırabiliriz. Birleştirme için tüm ihtiyacımız bu. Ben bu giriş dizilimlerinin her ilk bloğunu, J hunisi ile aynı zamanda, önbelleğe sığdırabileceğimi iddia ediyorum. Ve böylece o süre içinde her şey önbellekte kaldığı sürece, paralel taramalarda yaptığımız gibi, tam hızla birleşebilecektir. Burada aşağıda bulunan tüm bu blokları yukarda kullanınca, bir tanesi boşalıyor ve giriş arabelleğinde bir sonraki bloğa gidiyorsunuz ve bu böyle devam ediyor; tıpkı paralel dizilimlerin normal birleştirme çözümlerinde olduğu gibi, bu evrede buradaki her şeyin önbelleğe sığdığını varsayıyoruz.

Aynen önceki gibi. Elbette, aslında bu da özyinelemeli ama, bu düzeyde analiz ediyoruz. Şimdi, giriş başına bir bloğu sığdırabileceğimizi ispatlamam lazım. Zor değil. sadece hesaplama. Ve temelde bu hunilerin düzenleme şekilleri sayesinde, her giriş arabelleği başına bir blok sığdırabiliyorsunuz. İşte tartışma konumuz. Öyleyse iddia, “önbelleğe her giriş arabelleği başına, bir bellek bloğu da sığdırabilirsiniz” şeklinde. Bu bir J hunisindekine ek olarak yapılıyor. J hunisinde de her giriş arabelleği başına da bir blok sığdırabilirsiniz. Tamam, bu J hunisiyle ilgili olan kısım.

Aslında herhangi bir huni değil çünkü daha büyük huniler, bazen gerçekten çok büyüktür. Nasıl ispatlayacağımıza geçersek, en çok dörtte bir M ediyor. Burada varsaydığımız buydu; aslında C idi. Burada C ile ilgilenmeyeceğim çünkü sadece hayatımı daha güçleştirir. Kanımca bu daha zayıf bir sınırlama. Hunimizin boyutu ’dir. Bu önbelleğin en fazla bir çeyreği olur. Her iki tarafın karekökünü alırsak, J en çok, ½ karekök M eder. Beri yandan B’nin en çok karekök M olduğunu, çünkü M’ nin en az B kare olduğunu biliyoruz. Böylece yan yana koyduğumuzda J çarpı B, en fazla yarım M ediyor.

Şimdi, istediğimizin J kere B olduğunu, çünkü bir J hunisinde, J sayıda giriş diziliminin bulunduğunu iddia ediyorum. Öyleyse her biri için bir blok isterseniz bu, her biri için B alanı kadar bir maliyet eder. Yani, her arabellek girişi için, B boyutunda bir bloğumuz var, ve iddia da, her şeyin önbelleğin yarısına sığacağı idi. Oysa, önbelleğin sadece dörtte birini kullandık. Öyleyse, toplam olarak önbelleğin üç çeyreğini kullanmış oluyoruz.Bu da kullanacağımızın tamamı olur.Öyleyse bu iyi haber. Kalanla çıkışa bir blok daha sığdırabiliriz. Bu da çok büyük bir iş değil.

Netice olarak, bu J hunisi çalıştığı sürece her şey önbellekte ise, her şey yolunda demektir. Bunun anlamı nedir? Önce bu hunide değişimin ne kadar süre aldığını çözümleyeyim. Soru, bir J hunisindeki herşeyi ve arabellek başına bir bloktaki herşeyi okumak ne kadar zaman alıyor? Başlamak için gerekli olan bu. Bu J hunisi içindeki değişim oluyor, yani J hunisinin tamamını okumak ve her giriş başına bir blok okumak. Değişimin maliyeti oldukça normal,--.arabelleğin boyutunun B’ye bölünmesi, çünkü okumak için sadece doğrusal tarama gerekir ve -- arabellek başına bir blok okumamız gerekiyor.

Bu tamponlar çok büyük oldukları için, her yere dağılmış durumda olabilirler. Öyleyse, başlangıçta ilk bloğu okumak için, giriş başına bir bellek transferi ödüyoruz diyelim. İddia, -- burada biraz daha aritmetik yapmamız gerekiyor. Bu en çok bölü B dir. Neden en fazla bölü B? Bu önbelleğe sığan şeylerin bulunduğu ve önbelleğe sığdığı birinci düzeydi. Bu ikinci düzey daha büyük demektir ki, o ’dir. Bunun boyutu tür ve bu önbellekten daha büyük olmalıdır. Aksi takdirde durmanız gerekecekti. Bu sadece biraz daha aritmetik. Ya bana inanır ya da aritmetiği takip edersiniz. ’ün en az M -- ve M’nin de en az olduğunu biliyoruz. Bundan dolayı, yerine ’yi koyup, iki tarafın karekökünü aldığımızda, J^2 en az B olur.

Böylece elbette, bölü B, en çok bölü B olur. Fakat J de en çok bölü B dir, çünkü en az B’dir. Umarım bunların hepsi açık çünkü sadece cebir. Bu sınırlamayı biraz karışık olduğu için kullanmayacağız. Sadece bölü B’nin değişiminin maliyeti olduğunu söyleyeceğiz. Niçin bölü B iyi bir şeydir? Çünkü J hunisine girişlerin toplam boyutunun olduğunu biliyoruz. Öyleyse, J hunisinde ki tüm girdileri okumak J^3 bölü B süre alır. Aslında bu her şeyin değiştirilmesi için doğrusal ve ek bir maliyet oluyor. Kulağa iyi geliyor. Birleşmeyi yapmak da bölü B’ye mal olur. Yani tüm bu J^3 elemanı birleştirmek için, değişim bölü M ye mal oluyor. Eğer hepsi orada girişlerde olsaydı, bölü B zaman alacaktı çünkü, bir kere her şey orada olduğunda ve tam sürat birleştirme yaptığınızda, bunu ortalamada, bellek başına B öğesi olarak yapıyorsunuz.

Ama sorun tahmin ettiğiniz gibi, değişimi yaparken bulunduğunuz yerden de çıkmanızın gerektiği. Giriş arabelleklerinizden biri boşalır boşalmaz, -- bu boşalmak üzere diyelim, boşalır boşalmaz o huniyi tamamen yok edecek ve içindeki bütün parçaları birleştirmek ve bu arabelleği ağzına kadar doldurmak için, bunun içine değişim yapacaksınız. Amortizasyon bu noktada işin içine girer. Şimdiye kadar esas itibariyle doğrusal maliyet ödemiş olduğumuz için, log faktörü de işin içine girer.

Neredeyse bitirdik. Böylece uyguladığımız bedel, -- af edersiniz, kendimin önümde koşuyorum. -- Bir giriş arabelleği boşaldığında -- biz de dışarı çıkıyor ve o arabelleği özyinelemeli olarak dolduruyoruz. Tüm bu işlemler sırasında, tekrar-kullanımın hiçbir şekilde olmadığını varsayıyorum, yani bu özyinelemeli doldurma her şeyi dışarı çıkardı ve bu huni için her şeye sıfırdan başlamam gerekiyor. Böylece bu olduğunda, bu tamponu dolduruyorum ve sonra-- geri geliyorum ve “bunun içini yeniden doldurup değiştireyim”, diyorum. Özyineleme çağrısı biter bitmez yeniden içinde değiş tokuş yapıyorum. Yani, özyinelemeli olarak önce dolduruyorum, sonra da içindekileri değiştiriyorum.

Tekrar içini yeniden doldurup değiştirmek, bölü B ye mal oluyor. Bu maliyeti henüz dolmuş olan elemanlara uygulayacağım. İşte bu bir “amortised charging argument”, yani amortize edilmiş fiyatlama argümanı’dır. --- Bunlardan kaç tane var? Tek soru bu. Herşey çok yolunda görünüyor, buradaki karekök K hunisi için her arabellek K^ 3/2 boyutunda; aslında bu biraz karmaşık. Ama ben arabelleği dolduran buradaki elemanların sayısının olduğunu iddia ediyorum. Yani “eğer bir J huniniz varsa, her giriş arabelleğinin boyutu ’dür. Eğer hesaplarsanız doğru olması lazım. Böylece, bölü B maliyetini, sayıda elemana yüklüyoruz. Bu da eleman başına, bir bölü B gibi bir şey oluyor.

Mükemmel görünüyor. Bu, problemi bütünüyle düşündüğümüzü gösteriyor, yani N sayıda eleman var ve bunların her birine, bir bölü B fiyatı uyguluyorsunuz. Bu, toplam koşma zamanının N bölü B gibi bir değer olduğunu ifade eder. Sıralama için biraz fazla hızlı. log faktörünü kaybettik. Böylece olan şey, aslında bir elemana birden fazla kez maliyet yüklüyoruz. Normalde bu yapmadığımız bir şey. Bu sınıfta hiç yapmadık. Ancak bunu, maliyet yükleme sayısını sınırladığınız takdirde yapabiliyorsunuz. Bir maliyet yükleme işlemi yaptığınızda, “Bu her yerde çok sayıda tekrarlamıyor, çünkü bu olduğunda şu oluyor.” diyebilirsiniz. Ama asıl yapmanız gereken, maliyeti elemanlara yüklediğinizde, bunu belli elemanlara çok da fazla uygulamadığınızı ispat etmek olmalıdır. Benim burada üzerine maliyet yükleyebileceğim ölçeklenebilir şeylerim var: elemanlar. Öyleyse, “bu arabelleğin içine girmiş her eleman için, eleman başına bir bölü B maliyeti uygulayacağım’’ diyorum.

Bu elemanlara kaç kere maliyet yüklenir? Her maliyet yüklendiğinde, yeni bir arabelleğe taşınıyor. Pekiyi, kaç arabellek değiştirebilir? Her zaman sadece yukarı doğru çıkıyor. Birleştirme daima yukarıya çıkar. Yani buradan başlarız, bir sonraki arabelleğe gidersiniz, sonra da bir sonrakine.. Ziyaret ettiğiniz arabelleklerin sayısı, log..-- doğru log’dur. Hangi log olduğunu bilmiyorum. Bir bölü B maliyetinin eleman başına yüklenme sayısı, o elemanın arabelleği ziyaret sayısıdır ve bu bir log faktördür. Koşma zamanı içindeki ek log faktörünü bu noktada elde ederiz. Ziyaret edebileceğiniz J hunilerinin düzeylerinin sayısı budur. Yani, log K bölü log J dir, eğer doğru yaptıysam.

Pekala, bitirdik gibi. Biraz toparlayalım . Sadece biraz daha aritmetik, maalesef. Son olarak log K bölü log J demiştik. Şimdi, kabaca M gibidir; M’nin karekökü olabilir. Ama log J temelde log M’dir. Orada bazı sabitler var. Öyle ise, burada elemanlara maliyet yükleme sayısı, teta logK bölü log M’dir. Bu, amortizasyonda pek görmediğimiz bir şey ama, toplam bedel yükleme sayısını bulmak için toplamak zorundasınız. Tüm işin maliyeti birilerine yükleniyor, sadece başlangıçtaki değişimleri hiç kimseye yüklemedik. Ama, her değiş tokuşta bunu birine yüklüyoruz. Öyleyse her şey kaç kere ücretlendiriliyor? N elemanı var. Herbiri bir bölü B maliyetinde; ücretlendirme sayısı da bu log K bölü log M kadar.

O nedenle toplam maliyet -- elemanların sayısı çarpı bir bölü B çarpı bu log’lu şeydir. Bu da aslında artı K dir. Bir artı K’ yi unuttuk ama bu en başta tüm giriş listelerinde işe başlamakla ilgiliydi. Bu, bu sınırı ispatlamak için yapılan bir amortizasyon çözümlemesidir.. Af edersiniz, buradaki N de ne? En altta, K^3 sayıda elemanla başladığımı varsaymıştım. En alttaki elemanların sayısı K^3 theta idi. N değil K^3 yazmalıydım . Bu, bununla aşağı yukarı aynı olmalı-- ama tamamen aynı değil.. Bu log_M/K tabanında, -- biraz aritmetik yaparsanız, bunun : K^3 bölü B, çarpı log_M/B tabanında K bölü B, artı K olması gerekiyor.

İspatlamak istediğim şey bu. Aslında burada bir K yerine K^3 var. Fakat bu, sadece üçün bir faktörü. Ve bu takip ediyor çünkü taban durumunda olmadığımızı varsayıyoruz. Böylece K en az M oluyor, bu da en az demek ve bu sebepten, K bölü B, omega karekök K oluyor. Öyleyse, K bölü B, esas itibariyle bir log’a yerleştirdiğinizde K ile aynı gibidir. Şimdi burada log M tabanı var. Ben onu log M bölü B tabanına çevirdim. Bu daha da kötü oldu. Zarar yok. Ve K’nin log’u var. Onu da K bölü B ile değiştirdim ama K bölü B, aslında K nın karekökü. Yani, bir log içinde sadece yarımın bir faktörü olur.

Böylece, bu huninin çözümlemesi tamamlanıyor. Bu delice koşma zamanını elde ediyoruz, ve bu aslında sıralama sınırı artı küçük bir değer. Onu huni sıralamasına uyguladığımızda, sihirli bir şekilde önbelleği dikkate almayan en iyi sıralamayı elde ediyoruz; tam zamanında.

Salı günü final var. Sınav daha ziyade birinci Quiz stilinde, yani çok fazla yaratıcılığı yok, genellikle işlenen konulara yönelik. Her şeyi kapsıyor. Huni sıralaması konusunda endişelenmenize gerek yok ama geri kalan her şeyi kapsıyor. Birinci Quiz gibi ama bütün yarıyıl için.

Üç saat sürecek ve iyi şanslar. Sizinle olmak bir zevkti, tüm öğrenciler. Eminim Charles da öyle düşünüyordur, bu nedenle herkese teşekkürler.

Çok eğlenceli idi.