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