Progressive Overflow (Linear Probing)

Herkese tekrar merhaba,

Çarpışmayı engelleyen(collusion resolution) yöntemlerimize devam ediyoruz. En son EISCH algoritmasından bahsetmiştik. Tıpkı LISCH-LICH gibi, EISCH'in de EICH adında farklı bir versiyonu var. Ama benzer mantık olduğu için onu anlatmadan geçtim. BLISCH gibi konulara değineceğim bir ara da. Şimdiye kadar hep bağlantı yoluyla çarpışma engelleme algoritmalarından bahsettik(with links). Şu anda ise bağlantı olmadan, without links, çarpışmayı engelleme algoritmasına geçiyoruz.

Link'ler ile olan yöntemde, hatırlarsınız, bir anahtar değerini tutan alanımız, bir de bağlantıyı koparmamak için Link değerini tutan alanımız vardı. Without Links kategorisinde, adından da anlaşılacağı üzere, Link değerini tutan bir alanımız yok. Bu anlamda, Link ile çalışan algoritmalara göre daha avantajlı.

Progressive Overflow, bağlantısız (without links) çalışan algoritmalar içerisinde en basit olanı. Mantık şu: herhangi bir anda collision(çarpışma) olursa, takip eden ilk boş/müsait yere yerleştirilir.(Tablonun sonuna kadar gittiniz ve boş yer bulamadıysanız, tablonun en başından itibaren yerleştirmeye çalışınız). Basit olduğu için tercih edilebilse de, başarısız aramalarda performansı oldukça düşüktür.

Her zaman olduğu gibi Alan Tharp amcamızın kitabındaki soruyu çözelim.

SORU: 27-18-29-28-39-13-16-42-17       mod 11


ÇÖZÜM: Her zaman olduğu gibi hash'ini alarak home address'lerini buluruz.
hash(27)=5 mod11
Hash bulmayı unutanlar için bir kez daha hatırlatayım. 27 değeri verilmiş bize. mod da 11 imiş. 27'yi 11'e bölüyoruz. Kalan değer bizim hash değerimiz veya bir başka deyişle home address'imiz oluyor. 27 için home address'i 5 çıktı. O halde 27 değerini tablomuzun 5 numaralı gözüne yazıyoruz.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6
7
8
9
10

Şimdi de 18'i yerleştirelim.
hash(18)=7 mod 11
7 numaralı göz de boş olduğundan sorunsuzca yerleştiririz.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6
7	18
8
9
10

29'a geldi sıra. Şimdi bu yöntemi anlamaya başlayacaksınız.
hash(29)=7 mod 11
7 numaralı göz dolu, az önce oraya 18 yerleşmişti. Link kullandığımız önceki algoritmalarda R değeri tutuyor, bu değerin gösterdiği gözlere sayımızı yerleştiriyorduk. Progressive Overflow'da ise bir sonraki göze yazıyoruz, gayet basit. :) 7 numaralı göz dolu olduğundan, bir sonraki göze bakıyoruz. 8 numaralı göz dolu mu boş mu diye kontrol ediyoruz. Boş olduğunu görüyoruz(yukarıdaki tabloya bakın). Bu yüzden kaydımızı 8 numaralı göze yazıyoruz. Eğer 8 numaralı göz de dolu olsaydı, bu sefer 9 numaralı göze bakardık. Tablonun son hali şöyledir:

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6
7	18
8	29
9
10

28'i yerleştirelim.
hash(28)=6 mod 11
6 numaralı göz boş olduğundan, 28'i sorunsuzca yerleştiriyoruz.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6	28
7	18
8	29
9
10

39'a geldi sıra.
hash(39)=6 mod11
6 numaralı göz dolu. Oraya az önce 28'i yerleştirmiştik. O yüzden bir sonraki göze bakıyoruz:7 numaralı göz. Ancak 7 nuaralı göz de dolu, orda da 18 var. Yine bir sonraki göze bakıyoruz:8 numaralı göz. Maalesef orası da dolu, orda da 29 var. Yine bir sonrasına bakarız:9 numaralı göz. Nihayet boş bir göze denk geldik. :) 39 değerini 9 numaralı göze yerleştiriyoruz. Tablo şu hale gelir:

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6	28
7	18
8	29
9	39
10

13'ü yerleştiriyoruz şimdi.
hash(13)=2 mod11
2 numaralı göz boş olduğundan, 13 değerini sorunsuzca yerleştiririz.

Sıra	Anahtar Değeri
0
1
2	13
3
4
5	27
6	28
7	18
8	29
9	39
10

16'da sıra.
hash(16)=5 mod11
5 numaralı göz dolu. 6, 7, 8 ve 9 numaralı gözlere de sırayla bakacak olursak, onların da dolu olduğunu göreceğiz. O yüzden yine bir sonraki göze bakıyoruz:10 numaralı göz. Orası boş!! :) 16 değerini de 10 numaralı göze yerleştiriyoruz o halde. Tablo şu hale gelir:

Sıra	Anahtar Değeri
0
1
2	13
3
4
5	27
6	28
7	18
8	29
9	39
10	16

42'ye geldi sıra.
hash(42)=9 mod11
9 numaralı göz dolu olduğundan, oraya yerleştiremiyoruz. Bir sonraki göze bakarız:10 numaralı göz. Ancak orası da dolu. Yazının en başında, böyle bir durumla karşılaşırsak, ne yapacağımızı belirtmiştim. Tablonun sonuna ulaştık. O yüzden tablonun en başından başlayarak, boş yer aramaya devam ederiz. 10 numaralı göz doluydu. Bir sonraki göze bakalım:0(sıfır) numaralı göz. Orası boş. Bu yüzden 42 değerini 0 numaralı göze yerleştiririz. Tablo şu hale gelir.

Sıra	Anahtar Değeri
0	42
1
2	13
3
4
5	27
6	28
7	18
8	29
9	39
10	16

Son olarak 17'yi de yerleştirelim.
hash(17)=6 mod 11
6 numaralı göz dolu. Ondan sonra gelen, sırasıyla 7, 8, 9, 10 ve 0 numaralı gözler de dolu. 1 numaralı göz ise boş. 17 değerini de buraya yerleştiririz. Tablonun nihai hali şöyledir:

Sıra	Anahtar Değeri
0	42
1	17
2	13
3
4
5	27
6	28
7	18
8	29
9	39
10	16

Bu algoritma için de average probe'u(bir değere ortalama kaç adımda ulaşabildiğimiz) hesaplarsanız(daha önce yapmıştık), oldukça yüksek bir değer elde edeceksiniz. Bunun sebebi secondary clustering(ikincil kümeler)'dir. Bu da farklı home address'ine sahip kayıtlardan kaynaklanmaktadır. Daha farklı açıklamak gerekirse, artış sayısının 1 olmasından ötürü, ikincil kümeler ortaya çıkmaktadır. Pratikte pek de kullanılmaz bu algoritma.
Son bir not, bu algoritmada da kayıt direkt silinmez. Aksi takdirde arama işlemi sırasında boşluklar oluşabilir. Arama işlemi de boşluğu gördüğünde, aramayı durdurur; aranan kayıt tabloda bile olsa ulaşılamaz olur. Bu yüzden silinecek kaydın başına tombstone konur(işaretleme yapıyorsunuz yani). Bu göze yeni bir kayıt ekleyince de o tombstone'u kaldırırsınız.

Bu algoritma da bu kadar. Sonra görüşürüz..

Lütfen Evinizde Denemeyin..

Idaho State'ten Kamil Gawrzydek serbest atış kullanıyor. İlk atışında topun denge noktasıyla buluşmasına tanık olacaksınız. :)



Not: Videonun kaynağı youtubedur. Videoyu izleyemeyen varsa, bağlantı adresi: http://www.youtube.com/watch?v=lF8w3zN0xiA&feature=player_embedded

Hayward Kovulmuş!

İnsan bir haber verir değil mi ama.. İşten atılacaksın, bir mesaj bile atmayacaksın. Efendim, Tony Hayward'ın BP'deki görevine son verilmiş. Ve bu olay aylar öncesinde olmuş. Ben bunu South Park sayesinde öğrenebildim. -14ncü sezonda 10 veya 11nci bölüm olması lazım-

Meksida'ki sızıntı olayı aslında, bildiğim kadarıyla, BP'nin ilk vukuatı değil. Tony Hayward da günah keçisi olmuş sanki.Burada eleştirilmesi gereken bir şahıs değil, şirket politikası olmalıydı zannımca. Şimdi bazı arkadaşlar, "şirketi de o yönetiyor ya zaten, salak mısın nesin" diyebilirler ama böyle kişiler şirketin genel politikasına sadece yön verebilirler. Kaldı ki Hayward onca hamleyi danışmadan yapabilir mi, orası muamma. Para basan bir petrol firmam olacak ve onu bir tek adamın ellerine bırakacağım... Nefes aldırmam adama. :)

Ne oldu şimdi peki? BP aklandı, günah keçisi bulundu ve kellesi vuruldu. Şimdiye kadar yazdıklarımdan Hayward taraftarı olduğum anlamı çıkmasın, zaten banane elin İngilizinden. Kendisini en çok "I am sorry" kampanyalarından hatırlayacağım. :) Hemen örneğini verelim: http://www.youtube.com/watch?v=KKcrDaiGE2s&feature=player_embedded    :)

Yöneticilik de hüner ister Tony'can, sıkma kendini, yat yarışına devam. :)
Ben Cem Adrian konserine bilet almaya çalışadurayım, siz kendinizi pazartesiye hazırlayın. Sonra görüşürüz.

Das Boot(1981)

1981 yılında gösterime giren Das Boot, son zamanlarda izlediğim en iyi filmdi diyebilirim. Yaklaşık 3-3,5 saatlik süresinde hiç sıkıldığım bir an olmadı ve bu özelliğiyle bana Godfather serisini anımsattı.

İkinci Dünya Savaşı yıllarında 12 denizaltıyla beraber denize açılan U-96 tip bir denizaltının ve mürettebatının öyküsü ele alınmış. Yıllarca savaşın hep karadaki halini izlemiş biri olarak, ilk kez denizdeki mücadeleyi görmek de farklı bir duyguydu. :) Hidrofon Taraması ise en çok ilgimi çeken kısımdı. "Hava kötü olduğunda, suyun altında görebildiğinden daha fazlasını duyabilirsin" şeklinde, hidrofon, en mükemmel şekilde açıklandı filmde. Keza su basıncının etkisiyle civataların birer birer patlama sahnesi de güzeldi gerçekten. Genel manada neler oldu derseniz: Alman denizaltıları, İngiliz gemilerine saldırdılar, Destroyer'lar da onları vurdular. Bu şekilde bir kovalamaca şeklinde geçti. Ardından Alman denizaltına Cebelitarık Boğazını geçme emri gelince, vurulmaları ve suyun altında verdikleri yaşam mücadelesi... Asıl önemli yeri de, uzunca bir süre suyun altında ölümü bekledikten sonra, denizaltının son bir ümitle çalıştırılması ve Cebelitarık'ı geçmeleri; ardından La Rochelle'de, yani kendi evlerinde, İngiliz Hava Taarruz Uçakları tarafından vurulmaları. Filmin sonundaki Kaptan'ın gemisinin batışını izleme sahnesi oldukça iyiydi.

Wolfgang Petersen'a ve Lothar Buchheim'a kocaman bir alkış. İzlemediyseniz, hiç vakit kaybetmeyin derim. Sonra görüşürüz..

Dilini Eşek Arısı Sevsin..

Oğuz Haksever, CHP Kurultayından aktarıyor:"(..)Yeni listeye tepkiler var. Olumlu tepkiler bunlar..."

Tepki kelimesi, "tep"mek kökünden türemiştir ve olumsuz anlamdadır. Tepmenin olumlusu olmuyor yani. Detaylı bilgi için bkz. TDK

Yorum Sizin..

Facebook Profilinize Kimler Bakmış? :)

Yeniden merhaba arkadaşlar,

Az önce okuduğum bir haber üzerine kısa bir yazı yazmak istedim. :) Facebook'ta profilinize kimin baktığını gösteren bir uygulama YOK. Bunu sağlayan bir grup da YOK. Bunu sağlayacak API yazılımcılar tarafından yazılabilir belki ama facebook da buna karşı her gün kendini geliştiriyor.

Yani lütfen kendinizi komik duruma düşürmeyin. Maalesef arkadaşlarımın sayfalarında da böyle şeyler görüyorum ki bu beni daha çok üzüyor. Galiba bu durum teşhir edilmekten hoşlanma ile ilgili. :) Kim girecek kardeşim sayfana: ben sen o biz siz onlar.. Girmesini istediğin biri varsa, git iletişim kur. :) Ama lütfen dikkat edin ve facebook fırsatçılarının tuzaklarına düşmeyin. ;)

Görüşmek üzere..

EISCH (Early Insertion Standart Coalesced Hashing)

Merhaba arkadaşlar,

Daha önce başlamış olduğumuz "collusion resolution" yöntemlerinden "bağlantı yöntemi ile çarpışma önleme" tekniğinin bir diğer konusundan devam ediyoruz. Şimdiki konumuz EISCH. Diğer anlattığım konuları okuduysanız şayet, bu isimden yanlışbir anlam çıkarmayın sakın. EISCH, collision olduğunda, kaydı başa ATMAZ!! Daha farklı bir durum söz konusu. Örnek üzerinde anlatayım.

Yine Alan Tharp'ın North Carolina State Üniversitesi için hazırladığı kitabındaki örneği yapalım:

SORU: 27-18-29-28-39-13-16-42-17
hash(key)=key mod11

ÇÖZÜM: Mod 11 dediği için tablomuzu yine 0-10 arasında çiziyoruz.

Sıra	Anahtar Değeri	Link
0
1
2
3
4
5
6
7
8
9
10

Ardından ilk elemanımızı yerleştirmeye başlıyoruz.
hash(27)=5 mod11
Artık bu işlemleri biliyorsunuz farz ediyorum çünkü diğer başlıklarımda bayağı anlatmıştım. O yüzden 27'yi direkt 5 numaralı göze yerleştirdim. 5 numaralı göz boş olduğundan sorunsuzca yerleştiririz.

Sıra	Anahtar Değeri	Link
0
1
2
3
4
5	27
6
7
8
9
10

Şimdi ikinci elemanımızı yerleştirelim.
hash(18)=7 mod 11
7 numaralı göz de boş olduğundan, 18'i de oraya sorunsuzca yerleştiririz.

Sıra	Anahtar Değeri	Link
0
1
2
3
4
5	27
6
7	18
8
9
10

Sıra geldi 29'u yerleştirmeye.
hash(29)=7 mod 11
7 numaralı göz dolu! Orada 18 var. Bu yöntemde tıpkı LISCH yönteminde gösterdiğim gibi kaydı en sondaki müsait alana atıyoruz. Yani 10 numaralı göze... Yine R diye bir değer tutalım isterseniz, diğer tekniklerde yaptığımız gibi... R bize en alttaki müsait değeri versin. 10 numaralı göze 29'u koyuyoruz, artık 9 numaralı göz müsait. O yüzden R=9 oldu. 7 numaralı gözden de, 10 numaralı göze bir link attık. Sebebini bir kez daha açıklamış olayım: 29'u aramak isteyenler, doğal olarak 7 numaralı göze bakacaklar. Ancak orada 29 yok, 18 var. Dolayısıyla 29'un izini kaybetmememiz lazım. O yüzden de 7 numaralı gözden, bir link atmak zorundayız.

Sıra	Anahtar Değeri	Link
0
1
2
3
4
5	27
6
7	18	10
8
9
10	29

Şimdi de 28 var sırada.
hash(28)=6 mod11
6 numaralı göz boş olduğundan, 28'i sorunsuzca yerleştiririz. R=9 hala...

Sıra	Anahtar Değeri	Link
0
1
2
3
4
5	27
6	28
7	18	10
8
9
10	29

39'a geldi sıra.
hash(39)=6 mod11
6 numaralı göze az önce 28'i yerleştirmiştik; yani orası dolu. O halde R değerinin işaret ettiği göze yerleştireceğiz. R=9 idi. Dolayısıyla 39'u 9 numaralı göze yerleştiriyoruz. R=8 oldu. 6 numaralı gözden, 9 numaralı göze link atarız. Çünkü 39 değerini aradıklarında önce 6 numaralı göze bakarlar... Tablo şu hale gelir:

Sıra	Anahtar Değeri	Link
0
1
2
3
4
5	27
6	28	9
7	18	10
8
9	39
10	29

Şimdi bunun LISCH'ten farkı ne, diye soranlar vardır mutlaka. :) Az sabredin, farkı fark etmeye ramak kaldı. :)

13'ü yerleştiriyoruz şimdi de.
hash(13)=2 mod11
13 numaralı göz boş olduğundan, sorunsuzca yerleştiriyoruz. R=8 hala...

Sıra	Anahtar Değeri	Link
0
1
2	13
3
4
5	27
6	28	9
7	18	10
8
9	39
10	29

16'yı yerleştirelim hemen.
hash(16)=5 mod11
5 numaralı gözde 27 var. Dolayısıyla R değerinin işaret ettiği göze koyacağız 16'yı. R=8 olduğundan, 16'yı 8 numaralı göze yerleştiririz. 5 numaralı gözden de link atarız.. R=4 oldu artık. 7-6 ve 5 numaralı gözler dolu çünkü. En alttaki boş olan göz 4 olduğundan, R değeri de 4 oldu. :) Doğru dürüst anlatayım diye saçma sapan cümleler kuracağım yakında. :D Neyse. :)

Sıra	Anahtar Değeri	Link
0
1
2	13
3
4
5	27	8
6	28	9
7	18	10
8	16
9	39
10	29

42 değeri var sırada.
hash(42)=9 mod11
9 numaralı gözde39 var. (Eski bilgileri tazelemek isterseniz, şunu da belirtelim. 9 numaralı gözde home address'i[hashten dönen değeri] 6 olan 39 değeri var. Yani 39'un home addressi değil zaten orası. Dolayısıyla burada bir coalescing var)
R=4 idi en son. Dolayısıyla 42'yi 4 numaralı göze yerleştiriyoruz. R=3 oldu... 9 numaralı gözden de, 4 numaralı göze bir link atarız yine..

Sıra	Anahtar Değeri	Link
0
1
2	13
3
4	42
5	27	8
6	28	9
7	18	10
8	16
9	39	4
10	29

Veee.. :) Gelelim EISCH'in ne olduğunu anlayacağınız, 17'nin yerleştirilmesine. Aynı home address'ten en az 3 kere gelmesi lazımdı ki konuyu anlatabileyim. :) Benim suçum yok yani. :)

hash(17)=6 mod 11
6 numaralı gözde 28 var. Dolayısyla 17'yi R değerinin gösterdiği 3 numaralı göze yerleştireceğiz. Ancaaak.. Ancak 6 numaralı gözden zaten 9 numaralı göze link atılmış. LISCH olsaydı sorumuz, 6 numaralı göze giderdik. Ordan 9 numaralı göze link atılmış, 9'a giderdik; ordan da 4 numaralı göze link atılmış. 4 numaralı göze giderdik ve ordan da 17'nin bulunduğu 3 numaralı göze link atardık. Fakat EISCH böyle değil.. :)

EISCH yönteminde, yeni eklediğiniz elemanı, home address'inizdeki, yani hashten dönen değerdeki gözde bulunan elemandan sonraki ilk göze atarsınız. Örnekten devam edecek olursak: 17'nin home address'i 6 çıkmıştı. 6 numaralı gözde 28 var. İşte 17'yi hemen 28'ten sonraki eleman yapıyoruz. Bu EISCH yöntemindeki E(Early) harfinin esprisi de burada zaten. :) Yani 28'ten link direkt 17'nin bulunduğu göze atılır. Ordan da linkler eskisi gibi devam eder. Tablonun son hali şöyle olur:

Sıra	Anahtar Değeri	Link
0
1
2	13
3	17	9
4	42
5	27	8
6	28	3
7	18	10
8	16
9	39	4
10	29

Şimdi elemanlara kaçar adımda ulaştığımıza bakalım ve daha önceki yöntemlerde yaptığımız gibi average probe'u(ortalama olarak hedefe ulaşmadaki adım sayısı) hesaplayalım.
27 değerine 1 adımda ulaşıyoruz.
18 değerine 1 adımda ulaşıyoruz.
29 değerine 2 adımda ulaşıyoruz.
28 değerine 1 adımda ulaşıyoruz.
39 değerine 3 adımda ulaşıyoruz.
13 değerine 1 adımda ulaşıyoruz.
16 değerine 2 adımda ulaşıyoruz.
42 değerine 2 adımda ulaşıyoruz.
17 değerine 2 adımda ulaşıyoruz.
Toplamda 15 adımda 9 değere de ulaşabiliyoruz. 15/9=1.67 çıkıyor. LISCH'te bu değer 1.78 idi. Daha etkili bir yöntem imiş demek ki. :)


Bu yöntemin esprisi coalescing'i daha sonraki sıralara ötelemesidir. Yeni gelen değeri, home address'inden sonraki eleman yaptığınızda, bu yöntemi uygulamış oluyorsunuz.


Sonra görüşürüz..

Éphémère

Merhabalar,

Yeni yaşa girmenin verdiği ağırlıkla yazıyorum bu yazıyı. :) Bu sefer doğum günü kısmını pasifleştirdim feysbukta. Ama siteden kaldırmadım. Böylece kaç tane duyarlı arkadaşım varmış göreyim istedim. :) Görmez olaydım. :D

Bu hafta nispeten daha rahat geçti ama donmaya başladık diyebilirim. Artık Aralık'ta olduğumuzu hissetmeye başladık. İyi tarafı, yaya trafiği rahatladı.. Kötü tarafı ise, araç trafiği zirve yaptı.

Haftaya dair ilk bahsedeceğim şey, en kısa zamanda Sıla'nın son albümünü edinmeniz. Yine yapmış yapacağını. Süper olmuş. En sevdiğim şarkı şu diyemiyorum bile..

Diğer bir konu yumurtalı protesto için öğrencilere edilen laflar. Ayıptır yahu. Söylüyorlar dinleyen yok, yürüyorlar dayak yiyorlar.. Bunca şeyin patlamasıydı muhtemelen o. Yumurta Saldırısı için önlem almadığı için üniversite rektör ve dekanlarına ateş püskürüyormuş meşhur zat. Rektörler veya dekanlar bağımsız kurumların başındaki kişilerdir ve eğitim işlerinden sorumludur. El pençe divan durmak zorunda değillerdir. Özel muamele beklemesi çok komik. Bugün otobüsü ateşe verip gencecik Serap'ı vahşice öldüren katili "taş atan çocuklar" yasasından yararlandırıp, sürekli dayak yiyen ve susturulmaya çalışılan gençliği dava edip tutuklatmaya çalışırsanız, ortada ciddi bir sorun var demektir. Ya algılarım bozuldu ya ülkemin olaylara baktığı yer değişiyor.
Yorum sizin.

Yarın Algoritma konusu anlatacağım bir aksilik olmazsa. Bu arada Aylin Aslım'dan Bir Çocuk Sevdim'i dinleyin derim. :) O da sağlam bir sestir.

Görüşürüz sonra.

Özür & Düzeltme & Kınama

Geçenlerde ODATV'de okuduğum ve haliyle tepki gösterdiğim Bartın Üniversitesi ile ilgili haber hakkında, üniversite öğrencisi arkadaşın yaptığı sağduyulu ve bilgilendirici mesajla işin ayrıntılarını öğrendim. Dolayısıyla şüphelerim için şahıslardan özür dilemeyi görev bilirim.

Ayrıca konu ile ilgili açıklama yapmak yerine, saçma sapan mesajlarla hakarette bulunan zavallı iki arkadaşı da şiddetle kınıyorum.

Sonra görüşürüz..